Circular Doubly Linked list in Data structures 

  • Doubly linked lists within NULL pointers are fairly obvious extension of the singly linked list. And the circular doubly linked lists are the variation of doubly linked lists.
  • A circular doubly linked list or a circular 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.
  • The difference between a doubly linked and a circular doubly linked list is same as that exists between a singly linked list and a circular linked list.
  • The circular doubly linked list does not contain NULL in the previous field of the first node and the next field of the last node.
  • Rather, the next field of the last node stores the address of the first node of the list, i.e., START. Similarly, the previous field of the first field stores the address of the last node.
  • A circular doubly linked list is one which has both the successor pointer and predecessor pointer in circular manner.
  • The main advantage of using a circular doubly linked list is that it makes search operation twice as efficient.

Circular doubly linked list

Inserting a New Node in a Circular Doubly Linked List

In this section, we will see how a new node is added into an already existing circular doubly linked list. We will take two cases and then see how insertion is done in each case. Rest of the cases are similar to that given for doubly linked lists.

  • The new node is inserted at the beginning.
  • The new node is inserted at the end.

Deleting a Node from a Circular Doubly Linked List

In this section, we will see how a node is deleted from an already existing circular doubly linked list. We will take two cases and then see how deletion is done in each case. Rest of the cases are same as that given for doubly linked lists.

  • The first node is deleted.
  • The last node is deleted

Algorithms