Doubly Linked List in C

What is a Doubly Linked List in C?

A Doubly Linked List is a complex data structure and is an advanced version of a Singly Linked List data structure. A doubly linked list is a linked data structure that consists of records called nodes that are linked together sequentially using pointers in the form of a chain. Each node in a doubly linked list stores the data, the pointer to the next node in the sequence, and the pointer to the previous node in the sequence. These pointers are named next and previous respectively. This pointer stores the memory address of the next and the previous pointer in the sequence. A special node pointer head is used to denote the start of a doubly linked list. The previous pointer in the head node and the next pointer in the last node of a doubly linked list points to a sentinel value or a terminator. In the C programming language, this sentinal value is the null pointer. We can perform many operations on a doubly linked list like the insertion of a new node into the list at a specific position, deletion of a node at a specified position from the list, and displaying the list from the head node till the end.

Components in a Doubly Linked List in C

For writing the doubly linked list program in C, we need to define the following components:

• Node - It is the basic unit of a doubly linked list. Nodes are linked together using pointers to create a doubly linked list. Each node stores the data item, the next pointer, and the previous pointer.
• Next Pointer - It stores the address of the next node in the sequence in a doubly linked list.
• Previous Pointer - It stores the address of the previous node in the sequence in a doubly linked list.
• Data - It stores the data value of the node.
• Head - It represents the start of the doubly linked list.

Operations on Doubly Linked List

Many operations can be performed on a doubly linked list. We will discuss the method and the implementation of each operation below, later in the article.

Traversing

Traversing means visiting each node of the linked list starting from the head pointer till the end of the list. This is usually done to perform a certain operation like displaying data of each node or searching for a node etc.

Insertion

We can insert a new node into a doubly linked list at any position. There are four main scenarios for inserting a node into a doubly linked list:

• Insertion at beginning: In this case, a new node is inserted in front of the doubly linked list. The Head pointer is updated to point to the newly added node.
• Insertion at end: In this case, a new node is inserted at the end of the doubly linked list. No changes are required to the head pointer.
• Insertion after a given node: In this case, given a pointer to a node in the doubly linked list, we need to insert the new node after the node whose pointer is given to us.
• Insertion before a given node: In this case, given a pointer to a node, the goal is to insert the new node before the node whose pointer is given.

Deletion

Deletion means removing a node from a doubly linked list and maintaining its structure after the operation. There are three cases for deleting a node from a doubly linked list:

• Deletion at beginning: The node at the beginning of the doubly linked list is removed. The head pointer is updated to point to the next node of the removed node. The node that is removed is deleted from the memory.
• Deletion at the end: The last node of the doubly linked list is removed.
• Deletion of the node at a given position: In this case, we need to delete the node at the specified position from the doubly linked list.

Searching

Searching for a node involves comparing the data of each node in a doubly linked list with the item given to be searched. Generally, the location of the node in the linked list or the address of the node is returned as output. This address can be used to access the same node if needed. If no such node is present, then NULL is returned as output.

C Program for Inserting a Node at the Front of the Doubly Linked List

Algorithm

The new node is added in front of the doubly linked list. This new node becomes the new head pointer.

• Step 1: Create a new node with the data item. Let's call this node as $new\_node$.
• Step 2 : Assign next pointer of $new\_node$ to the head.
• Step 3: If the head pointer is not NULL, then assign the prev pointer of the head to the $new\_node$.
• Step 4: Finally update the head pointer.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 3$. Now we want to add the node with data 0 at the front.

First, we create a new node with data 0 and assign the next pointer of the new node to the head pointer.

Now, we assign the previous pointer of the head to the new node.

Finally, we update the head pointer.

Implementation

Complexity Analysis

Time Complexity -

To add a new node at the front, we are only updating a constant number of pointers, so the time complexity is $O(1)$.
Time Complexity: $O(1)$

Space Complexity -

To add a new node at the front, we only create the pointer to the new node. No additional memory is needed, so the space complexity is $O(1)$.
Space Complexity: $O(1)$

C Program for Inserting a Node at the End of the Doubly Linked List

Algorithm

To add a new node at the end of the doubly linked list, we first need to iterate to the end of the linked list and then add the new node.

• Step 1: Create a temporary pointer $ptr$. Initialize it to the head pointer.
• Step 2: While $ptr \rightarrow next$ is not NULL, move to the next node $ptr \rightarrow next$.
• Step 3: Now create a new node with the data $new\_node$.
• Step 4: Assign $ptr \rightarrow next$ to the $new\_node$ and assign $new\_node \rightarrow prev$ to $ptr$.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 3$. Now we want to add the node with data 4 at the end.

First, we go to the last node using a pointer $curr$ and assign the next pointer of $curr$ to the new node.

Now, we update the prev pointer of the new node.

Implementation

Complexity Analysis

Time Complexity -

When we add a new node to the end of the doubly linked list, we iterate from the head pointer to the last node, so the time complexity is $O(N)$, where $N$ is the number of nodes present in the list.
Time Complexity: $O(N)$

Space Complexity -

In the implementation, we use a constant amount of space for pointers and creating the object of the new node, so the space complexity is $O(1)$.
Space Complexity: $O(1)$

C Program for Inserting a Node in between Two Nodes of the Doubly Linked List

Algorithm

In this case, we are given a node $node$ after which we have to insert the new node.

• Step 1: Create a new node $new\_node$ with the data given.
• Step 2: Assign $new\_node \rightarrow next$ to $node \rightarrow next$.
• Step 3: Assign $node \rightarrow next$ to $new\_node$.
• Step 4: Assign $new\_node \rightarrow prev$ to $node$.
• Step 5: If $new\_node \rightarrow next$ is not NULL, then assign $new\_node \rightarrow next \rightarrow prev$ to $new\_node$.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 4$. Now we want to add the node with data 3 after the second node. We are also given the pointer to the second node.

We will first update the next pointer of the new node to the next pointer of the given node. Then, we assign the next pointer of the given node to the new node.

Finally, we update the prev pointers of the new node and the next node.

Implementation

Complexity Analysis

Time Complexity -

In the implementation, we are making a constant number of pointer changes, hence the complexity is $O(1)$.
Time Complexity: $O(1)$

Space Complexity -

In the implementation, we require a constant number of pointers and objects of the new node, so the space complexity is $O(1)$.
Space Complexity: $O(1)$

C Program for Deleting a Node at the Beginning of the Doubly Linked List

Algorithm

• Step 1: Initialize a pointer $curr$ to the $head$ pointer.
• Step 2: If $head$ pointer is not NULL, then increment the $head$ pointer.
• Step 3: Make the $curr$ pointer as NULL and free the memory.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 3$. Now we want to delete the node at the front. In this case, we simply update the head pointer to the next of the head pointer and delete the first node in the sequence.
Final Sequence: $2 \longleftrightarrow 3$

Implementation

Complexity Analysis

Time Complexity -

In the implementation, we are updating the head pointer and deleting the node at the front, hence the time complexity is $O(1)$.
Time Complexity: $O(1)$

Space Complexity -

In the implementation, we are using only a constant amount of memory for pointer $curr$, hence the space complexity is $O(1)$.
Space Complexity: $O(1)$

C Program for Deleting a Code at the End of the Doubly Linked List

Algorithm

• Step 1: Initialize a pointer $curr$ to the $head$ pointer.
• Step 2: While $curr \rightarrow next$ is not NULL, increment the $curr$ pointer.
• Step 3: Update $curr \rightarrow prev \rightarrow next$ as NULL and $curr \rightarrow prev$ as NULL.
• Step 4: Make the $curr$ pointer as NULL and free the memory.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 3$. Now we want to delete the node at the end.

First, we iterate to the last node using a pointer $curr$. Now we assign $curr \rightarrow next$ as NULL.

Finally, we delete the curr node.

Implementation

Complexity Analysis

Time Complexity -

In the implementation, we are iterating till the end of the doubly linked list, hence the time complexity is $O(N)$.
Time Complexity: $O(N)$

Space Complexity -

In the implementation, we are using a constant number of pointers, hence the space complexity is $O(1)$.
Space Complexity: $O(1)$

C Program for Deleting a Node at a Specified Position of the Doubly Linked List

Algorithm

In this case, we have to delete the node at a specified index $position$.

• Step 1: If $position$ is 1, then we delete the node at the front.
• Step 2: Iterate a pointer $curr$ until $position > 1$.
• Step 3: Now we need to remove the $curr$ node and connect $curr \rightarrow prev$ and $curr \rightarrow next$.
• Step 4: Assign $curr \rightarrow prev \rightarrow next$ to $curr \rightarrow next$ and $curr \rightarrow next \rightarrow prev$ to $curr \rightarrow prev$.
• Step 5: Make the $curr$ pointer as NULL and free the memory.

Example

Consider a linked list with 3 nodes $1 \longleftrightarrow 2 \longleftrightarrow 3$. Now we want to delete the second node in the list.

First, we go to the second node using a pointer $curr$.

Next, we connect the previous of the $curr$ node and the next node of the $curr$ node.

Finally, we delete the curr node.

Implementation

Complexity Analysis

Time Complexity -

In the implementation, we iterate until $position > 1$. In the worse case, we can end up iterating the whole list, hence the time complexity is $O(N)$ where N is the number of nodes in the linked list.
Time Complexity: $O(N)$

Space Complexity -

In the implementation, we are only using a constant amount of space for the $curr$ pointer, hence the space complexity is $O(1)$.
Space Complexity: $O(1)$

Menu Driven Program in C to Implement All the Operations of the Doubly Linked List

Output: