Doubly Linked List Program in C

Introduction

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 sentinal 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.

Need for the Doubly Linked List

A doubly linked list contains pointers to the previous node and the next node in the sequence. This is the biggest advantage of a doubly linked list over a singly linked list. Whenever the application requires navigation in both directions, we need a doubly linked list.

For example, a doubly linked list program in C can be used in a web browser for managing link navigation. Whenever the user clicks a new hyperlink, the link is inserted at the end into the doubly linked list. Now, if the user wants to go back and forth between the links, then this feature can be implemented by the forward and backward movement of the head pointer in a doubly linked list.

How Does Doubly Linked List Work in C?

A doubly linked list is a data structure that contains nodes in sequence. It contains a head pointer that points to the start of the doubly linked list. The nodes are implemented using structure in the C programming language. Each structure stores a pointer to the next node in the sequence and a pointer to the previous node in the sequence. Additionally, it also stores data in each node. In the C programming language, we store int data for easier explanation. However, any data type can be stored in each node. The sentinal value in the C programming language is NULL. It is used to point to the end of the linked list.

Memory Representation of a Doubly Linked List in C

A doubly linked list stores an additional previous pointer and hence consumes more memory than a singly linked list. Each node contains a pointer to the previous node and the next node in the sequence. Moreover, we must maintain a head pointer that points to the start of the doubly linked list. This pointer is used for operations like insertion, deletion, traversal, etc. The extra pointer being maintained at each node makes operations like insertion and deletion more expensive. Below is a memory representation of a doubly linked list. The sentinal value used in C is the null pointer NULL. It indicates the end of the linked list.

Consider the doubly linked list given in the image above. Each node in a doubly linked list is represented using a memory address and the address points to a struct Node that stores the data, next pointer, and the previous pointer.

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.

Program for Inserting a Node at the Front in a 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. Lets 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 prev pointer of the head to the new node.

Finally, we update the head pointer.

Program for Inserting a Node at the End in a 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)$

Program for Inserting a Node After a Given Node in a 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)$

Program for Inserting a Node Before a Given Node in a Doubly Linked List

Algorithm

In this case, we are given a node $node$ before 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$.
• Step 3: If $node \rightarrow prev$ is not NULL, then assign $node \rightarrow prev \rightarrow next$ to $new\_node$ and $new\_node \rightarrow prev$ to $node \rightarrow prev$.
• Step 4: If $node \rightarrow prev$ is NULL, then update the head pointer as we are inserting the node at front of the list.
• Step 5: Update $node \rightarrow prev$ to $new\_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)$

Program for Deleting a Node at the Beginning in a 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)$

Program for Deleting a Code at the End in a 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)$

Program for Deleting a Node at a Specified Position in a 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)$

Program for All the Operations (Insertion, Deletion, and Traversing) of Doubly Linked List

Output:

Advantages and Disadvantages of Doubly Linked List Over Singly Linked List

Advantages

• A doubly linked list can be traversed in both forward and backward directions.
• In case of insertion, if the node is given, after which the new node has to be inserted, then the time taken in case of a doubly linked list is O(1).
• In the case of deletion, if the node to be deleted is given, then the time taken in a doubly linked list is O(1).

Disadvantages

• A node in a doubly linked list uses more memory than a node in a singly linked list.
• Insertion and deletion take more time as it requires more pointer changes as the doubly linked list stores the previous pointer.