Circular Doubly Linked List

CIRCULAR DOUBLY LINKED LIST
Sandeep Singh Shekhawat

Today’s Discussion
• Circular Doubly Linked List[circular DLL]
• Representation of Circular DLL
• Operations on circular DLL
• Applications
• Pros & Cons
INTRODUCTION TO CIRCULAR
DOUBLY LINKED LIST
• Before we see circular doubly linked list, let us have
quick glance of doubly linked list.
• Doubly linked list is almost similar to singly linked list
except it contains two address or reference fields,
where one of the address field contains reference of
the next node and other contains reference of the
previous node.
• Doubly linked list is sometimes also referred as bi-
directional linked list since it allows traversal of nodes
in both direction.
o Circular doubly linked list is same as doubly linked
list.
o In Circular Doubly Linked List the next field of last
node has address of first node and previous field of
first node has address of last node.
o In circular linked list the 1st and last node are
connected to each other to form a circle.
head
Representation of circular
doubly linked list
#include<stdio.h>
struct node
{
int data;
struct node *prev, *next;
};
struct node *n1, *n2;
n1 = (struct node *)malloc(sizeof(struct node));
n2 = (struct node *)malloc(sizeof(struct node));
n1data = 01;
n2data = 02;
n1next = n2;
n2prev = n1;
n2 next = n1;
Operations on circular DLL
• Insertion at beginning, at
1 end and specific location
• Deletion at beginning, at
2 end
3 • Searching & Traversing

INSERTION AT BEGINNING
void insert_begin( )
{
struct node *new;
new = (struct node *)malloc(sizeof(struct node));
newdata = 01;
newprev = tail;
newnext = tailnext;
tailnext = new;
head = new;
}
INSERTION AT END
void insert_end( )
{
struct node *new;
new = (struct node *)malloc(sizeof(struct node));
newdata = 02;
newnext = head;
headprev = new;
newprev = tail;
tailnext = new;
tail = new;
}
DELETION AT BEGINNING
void delete_begin( )
{
struct node *temp;
temp = head;
head = tempnext;
headprev = tail;
tailnext = head;
free(temp);
}
DELETION AT END
void delete_end( )
{
struct node *cur, *temp;
cur = tailnext;
if(tail == 0){
printf(“List is empty”);
}
else if(curnext == head)
free(cur);
else {
while(curnext != cur) {
temp = cur;
cur = curnext;
}
tempnext = head;
headprev = temp;
free(cur);
}
}
SEARCHING
void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr != NULL) {
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item) {
printf("item found at location %d",i+1);
flag=0;
}
else {
while (ptr->next != head)
{
if(ptr->data == item) {
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0) {
printf("Item not found\n");
}
}
}
Travsersing
Void traverse ( )
{
struct node *temp;
temp = head;
if(temp == NULL)
{
printf(“List is empty”);
}
else {
while(tempnext != head)
{
printf(“%d “,tempdata);
temp = tempnext;
}
}
}
Applications of circular doubly linked list
– Used with data where we have to navigate front and
back.
– Circular doubly linked lists are used in
multiprocessing.
– Can be used in game development to implement a
loop of game objects.
– Used to implement an LRU (Least Recently Used)
cache.
– Can be used to implement a hash table.
Real-Time Applications:
• Music Player.
• Shopping-cart on online websites.
• Browser cache.
Advantages
• List can be traversed from both directions i.e. from head to
tail or from tail to head.
• Ease of data manipulation.
• Jumping from head to tail or vice versa takes O(1) time.
• Efficient insertion and deletion.
• Ability to handle circular buffers.
Dis-Advantages
• Requires additional memory.
• More complex than singly linked list.
• If not used properly, then the problem of infinite loop can
occur.
• Difficulty in detecting the end.
• Have a slight overhead of maintaining both the next and
previous pointers at each node.
• Not efficient for large datasets
THANK YOU!!

Circular Doubly Linked List

Uploaded by

Copyright:

Available Formats

Circular Doubly Linked List

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Circular Doubly Linked List

Uploaded by

Copyright:

Available Formats

CIRCULAR DOUBLY LINKED LIST

Sandeep Singh Shekhawat

3 • Searching & Traversing

You might also like