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

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

• 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).

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

• Step 1: Declare pointer ptr, n and initialize control variable i=0 [ ‘n’ contains the address of new node to be inserted]
• return [inserting the first node into the list]
• Step 3:Check, if pos==1 then
• n -> next=head -> next
• 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

• Step 1: declare p, ptr as a pointer to nodes, i=0
• Step 4: check, if pos==1 then
• head -> next=(head – >next) -> next [ logically deleting node at first position]
• Step 5: else, if pos>1, then 