Doubly Linked list in Data structures

  • A doubly linked list is one in which all nodes are linked together by multiple number of links which help in accessing both the successor node and predecessor node from the given node position. It provides bi-directional traversing.
  • Each node in doubly linked list has two link fields. These are used to point to the successor node and predecessor nodes.
  • A doubly linked list or a two-way linked list is a more complex type of linked list which contains a pointer to the next as well as the previous node in the sequence.
  • Therefore, it consists of three parts—data, a pointer to the next node, and a pointer to the previous node.

Doubly linked list

In C, the structure of a doubly linked list can be given as,

 struct node
 {
   struct node *prev;
   int data;
   struct node *next;
 };

The PREV field of the first node and the NEXT field of the last node will contain NULL. The PREV field is used to store the address of the preceding node, which enables us to traverse the list in the backward direction.

Inserting a New Node in a Doubly Linked List

In this section, we will discuss how a new node is added into an already existing doubly linked list. We will take four cases and then see how insertion is done in each case.

  • The new node is inserted at the beginning.
  • The new node is inserted at the end.
  • The new node is inserted after a given node.
  • The new node is inserted before a given node.

Deleting a Node from a Doubly Linked List

In this section, we will see how a node is deleted from an already existing doubly linked list. We will take four cases and then see how deletion is done in each case.

  • The first node is deleted.
  • The last node is deleted.
  • The node after a given node is deleted.
  • The node before a given node is deleted.

Advantages

  • Insertions and deletion are simple as compared to other linked list.
  • Efficient utilization of memory.
  • Bi-directional traversal helps in efficient and easy accessibility of nodes.

Disadvantages

  • Uses two pointers, which results in more memory space requirement.

Algorithms