CIRCULAR DOUBLY LINKED LISTs

 CIRCULAR DOUBLY LINKED LIST

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.Circular doubly linked list doesn't contain NULL in any of the node. The last node of the list contains the address of the first node of the list. The first node of the list also contain address of the last node in its previous pointer.

Memory Management of Circular Doubly linked list

Operations on circular doubly linked list :

There are various operations which can be performed on circular doubly linked list. The node structure of a circular doubly linked list is similar to doubly linked list.

1. Insertion in circular doubly linked list at beginning
2. Insertion in circular doubly linked list at end
3. Deletion in Circular doubly linked list at beginning
4. Deletion in circular doubly linked list at end

1.Inserting a Node at the Beginning of a Circular Doubly Linked List

Suppose we want to add a new node with data 9 as the first node of the list.

• In Step 1, we first check whether memory is available for the new node. If the free memory has exhausted, then an OVERFLOW message is printed. Otherwise, we allocate space for the new node. 
• Set its data part with the given VAL and its next part is initialized with the address of the first node of the list, which is stored in START.
• Now since the new node is added as the first node of the list, it will now be known as the START node, that is, the START pointer variable will now hold the address of NEW_NODE. 
• Since it is a circular doubly linked list, the PREV field of the NEW_NODE is set to contain the address of the last node.

struct node *insert_beg(struct node *start)

{

struct node *new_node, *ptr;

int num;

printf("\n Enter the data : ");

scanf("%d", &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node-> data = num;

ptr = start;

while(ptr -> next != start)

ptr = ptr -> next;

new_node -> prev = ptr;

ptr -> next = new_node;

new_node -> next = start;

start -> prev = new_node;

start = new_node;

return start;

}

2.Inserting a Node at the End of a Circular Doubly Linked List:

Suppose we want to add a new node with data 9 as the last node of the list.

• In Step 6, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 
• In the while loop, we traverse through the linked list to reach the last node. 
• Once we reach the last node, in Step 9, we change the NEXT pointer of the last node to store the address of the new node. 
• The PREV field of the NEW_NODE will be set so that it points to the node pointed by PTR (now the second last node of the list).

struct node *insert_end(struct node *start)

{

struct node *ptr, *new_node;

int num;

printf("\n Enter the data : ");

scanf("%d", &num);

new_node = (struct node *)malloc(sizeof(struct node));

new_node -> data = num;

ptr = start;

while(ptr -> next != start)

ptr = ptr -> next;

ptr -> next = new_node;

new_node -> prev = ptr;

new_node -> next = start;

start-> prev = new_node;

return start;

}

 3.Deleting the First Node from a Circular Doubly Linked List

 

• 
  
• 
  
• 
  
• 
  

• In Step 1 of the algorithm, we check if the linked list exists or not. If START = NULL, then it signifies that there are no nodes in the list and the control is transferred to the last statement of the algorithm.
• However, if there are nodes in the linked list, then we use a pointer variable PTR that is set to point to the first node of the list. 
• For this, we initialize PTR with START that stores the address of the first node of the list. 
• The while loop traverses through the list to reach the last node. Once we reach the last node, the NEXT pointer of PTR is set to contain the address of the node that succeeds START. 
• Finally, START is made to point to the next node in the sequence and the memory occupied by the first node of the list is freed and returned to the free pool.

 

struct node *delete_beg(struct node *start)

{

struct node *ptr;

ptr = start;

while(ptr -> next != start)

ptr = ptr -> next;

ptr -> next = start -> next;

temp = start;

start=start–>next;

start–>prev=ptr;

free(temp);

return start;

}

 

 4.Deleting the Last Node from a Circular Doubly Linked List:

Suppose we want to delete the last node from the linked list, then the following changes will be done in the linked list. 

• In Step 2, we take a pointer variable PTR and initialize it with START. That is, PTR now points to the first node of the linked list. 
• The while loop traverses through the list to reach the last node. Once we reach the last node, we can also access the second last node by taking its address from the PREV field of the last node. 
• To delete the last node, we simply have to set the next field of the second last node to contain the address of START, so that it now becomes the (new) last node of the linked list. 
• The memory of the previous last node is freed and returned to the free pool.

 struct node *delete_end(struct node *start)

{

struct node *ptr;

ptr=start;

while(ptr -> next != start)

ptr = ptr -> next;

ptr -> prev -> next = start;

start -> prev = ptr -> prev;

free(ptr);

return start;

}