Doubly Linked List in C and C++

In this tutorial you will learn about doubly linked list in C and C++.

In singly linked list, we can move/traverse only in one single direction because each node has the address of the next node only. Suppose we are in the middle of the linked list and we want the address of previous node then we don’t have any option other than repeating the traversing from the beginning node.

To overcome this drawback, a doubly linked list can be used. In this, there are two pointers. One of these pointers points to the next node and the other points to the previous node.

 

Doubly Linked List in C and C++

Image Source

 

The structure for a doubly linked list node can be declared as:

 

prev_node would contain a pointer to the address of the previous node and next_node would point the next node in the list. Hence, we can move in both the directions.

 

Traversing

Traversal of a doubly linked list is similar to that of a singly linked list. We have to first check for a condition: whether the linked list is empty or not. This helps to set the start pointer at a proper location. After that we access each node till end.

 

Insertion

A new node can be inserted very easily in a doubly linked list. We just need to set the pointers prev_node and next_node carefully interlinking the prev_node and the next_node node with the appropriate pointers.

If you’re inserting a Node n2 between Node n1 and n3, you should set the pointer prev_node of n2 to n1 and pointer next_node of n2 to n3.

Insertion in a doubly linked list can be done in multiple ways:

1. Insertion in between the nodes.
2. Insertion at the beginning.
3. Insertion in an empty list.
4. Insertion at the end of the list.

 

Deletion

A node can be deleted very easily in a doubly linked list. We just need to set the pointers prev_node and next_node logically to the nodes.

Deletion of the nodes can be done in the following ways:
1. Delete at the end.
2. Delete the first node.
3. Delete in between the nodes.

 

Reverse a Doubly Linked List

Assume we have four nodes n1, n2, n3 and n4

Steps to reverse

1. Pointer begin points to the last node n4.
2. Since, the n4 is the first node now, its prev_node pointer must be NULL.
3. Node n1 is the last node, hence its next_node must be NULL.
4. Pointer next_node of n4 points to n3, next_node of n3 points to n2 and next_node of n2 points to n1.
5. Pointer prev_node of n1 points to n2, prev_node of n2 points to n3 and prev_node of n3 points to n4.

 

Program for Doubly Linked List in C

 

Program for Doubly Linked List in C++

 

Output

Doubly Linked List

 

If you have any doubts regarding above doubly linked list in C and C++ tutorial then comment below.

Category: DSA

One thought on “Doubly Linked List in C and C++

  1. Jeff

    ugghhhh the flashbacks to freshman year of college are real!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *