Doubly and Circular Linked List

A circular doubly linked list is a doubly linked list with the first node linked to the last node and vice-versa. A circular doubly linked list is shown in the following figure.

In case of the circular list with header node, the ‘prev’ link of the node and the ‘next’ link of the last node points to the header node. And, the ‘prev’ and ‘next’ link of the header node points to the last node and first node respectively.

In case of the circular list without header node, the ‘next’ link of the last node point to the first node and ‘prev’ link of the first node points to the last node.

The main advantage of a circular doubly linked list is that a node can be inserted into a list without searching the complete list for finding the address of the previous node.

Doubly and Circular Linked List Advantage

• Every node is accessible from every other node.
• If we want to delete a node X, the predecessor can be found from X itself without the need of address of the first node.

Doubly and Circular Linked List Disadvantages

• Less care in processing will lead to an infinite loop.
• We cannot distinguish between first node last nodes. So a header node or tail node must be added to overcome this problem.

Operations on Circular Doubly Linked List

The basic operations that can be performed on a circular doubly linked list are,

• Traversal
• Insertion and
• Deletion

Circular Doubly Linked List Traversal

A circular doubly linked list can be traversed in both directions i.e., from the first node to the last node and vice-versa (with the help of ‘next’ and ‘prev’ points respectively).

Algorithm: CDL-traverse (head)

• Step 1: check, if ((head -> prev==head) and (head -> next==head)) then print “list is empty” return.
• Step 2: else, ptr=head -> next [ptr is a temporary pointer for traversing list]
• Step 3: while ptr!=head, go through step 4
• Ptr=ptr -> next
• Step 5: return

Circular Doubly Linked List Insertion

The insertion of a node into the circular doubly linked list can be at different locations, i.e., at the beginning of the list, at a specified location in the list, at the end of the list.

Algorithm: CDL-insert (head,ptr)

• Step 1: Declare pointer ptr, n and initialize control variable i=0 [ ‘n’ contains the address of new node to be inserted]
• Step 2: check, if((head -> prev==head)and (head -> next==head)) then  head -> prev=n
  • head -> next=n
  • n -> prev=head
  • n -> next=head
  • return [inserting the first node into the list]
• Step 3:Check, if pos==1 then
  • n -> prev=head
  • n -> next=head -> next
  • head -> next ->prev=n
  • head -> next=n
  • return [insering node at beginning]
• Step 4: [inserting at specified position] Initialize ptr=head -> next,p=ptr increment ‘i’ (i++) and check, if (i==pos), if true then n -> prev=p
  • n -> next=ptr
  • p -> next=n
  • ptr -> prev=n
• Step 5: else, go through step6 while (ptr!=head)
• Step 6: p=ptr  ptr=ptr -> next
• Step 7: return

Circular Doubly Linked List Deletion

A node can be deleted from the circular doubly linked list at any position in the list

Algorithm: CDL-delete (head,pos)

• Step 1: declare p, ptr as a pointer to nodes, i=0
• Step 2: check, if ((head -> prev==head)&&(head -> next==head)),then print “list is empty deletion not possible” return.
• Step 3: check, if((head -> next) -> next==head) then
  • head -> prev=head
  • head -> next=head [deleting a single node in the list]
• Step 4: check, if pos==1 then
  • ptr=head -> next
  • head -> next=(head – >next) -> next [ logically deleting node at first position]
• Step 5: else, if pos>1, then
  • ptr=head -> next
  • p=ptr
• Step 6: increment I by 1 check, if i==pos, then
  • p -> next=ptrnext
  • (ptr -> next) -> prev=p
  • else, p=ptr
  • ptr=ptr -> next
• Step 7: go through step6 while ptr -> next!=head
• Step 8: return