Data Structures and
Algorithms
Module -3
Doubly Linked List
Dr. R. Jothi, SCOPE
VIT Chennai
Outline
Types of Linked List
Circular Linked List
Doubly Linked List
Dr. R. Jothi, VIT Chennai
Types of Lists
Depending on the links to join adjacent nodes
Linear singly linked list (discussed in last class)
Circular singly linked list
Doubly linked list
Linear vs circular
Dr. R. Jothi, VIT Chennai
Linear Singly Linked List
Each node in the list has only one pointer to its
successor
Last node points to NULL
Head A B C
Circular Singly Linked List
Each node in the list has only one pointer to its
successor
Last node points to first node (head) in the list
Head
A B C
Doubly Linked List
Links exist between adjacent nodes in both directions.
The list can be traversed either forward or backward.
Usually two pointers are maintained to keep track of
the list, head and tail.
head tail
A B C
Dr. R. Jothi, VIT Chennai
A node in the Doubly Linked List
struct nd {
struct item data;
struct nd *next;
struct nd* prev;
} node;
Creating Doubly Linked List
Empty DLL
Add nodes,
first node becomes head
Dr. R. Jothi, VIT Chennai
Adding nodes in DLL
As in SLL, there are 3 cases
Insert at beginning
Insert at end
Insert at middle
Dr. R. Jothi, VIT Chennai
Adding a node in Empty List
New = (struct node *)
malloc(sizeof(struct node));
New -> data = 39; The same code works
New -> next = Head; when we want to insert
New -> prev = Head; a node at beginning
Head = New;
Dr. R. Jothi, VIT Chennai
Adding a node at end
2
1 3
New = (struct Node *)
malloc(sizeof(struct Node));
New -> data = 84;
1 New -> prev = Cur;
2 New -> next = Cur -> next;
3 Cur -> next = New; Dr. R. Jothi, VIT Chennai
Adding a node at middle
New = (struct node *)
malloc(sizeof(struct Node));
New -> data = 64; • Here Cur points to the node before/after
New -> prev = Cur; which new node to be inserted
New -> next = Cur -> next; • Use search to locate Cur
Cur -> next -> prev = New;
Cur -> next = New;
Dr. R. Jothi, VIT Chennai
Search
Search for node and return its address
struct node * search(struct node * head, int target)
{
Cur = Head;
//search until the target value is found or the end of the list is reached
while (Cur != NULL && Cur -> data != target) {
Cur = Cur -> next;
}
//determine if the target is found or ran off the end of the list
if (Cur != NULL)
return Cur;
return NULL;
} Dr. R. Jothi, VIT Chennai
Deleting a node from Doubly Linked List (1)
1. Delete a head node
Cur=Head
Head = Cur -> right;
Cur ->right -> left = NULL;
free(Cur);
Dr. R. Jothi, VIT Chennai
Deleting a node from Doubly Linked List (2)
2. Delete any other node
Cur -> left -> right = Cur -> right;
Cur -> right -> left = Cur -> left;
Dr. R. Jothi, VIT Chennai
Traversal
Sam as SLL
//traverse a linked list
struct node *p;
p= Head;
printf(“List contains:\n”);
while (p != NULL){
printf(“%d ”, p -> data);
p = p -> next;
}
Dr. R. Jothi, VIT Chennai
DLLs compared to SLLs
Advantages:
Can be traversed in either direction (may
be essential for some programs)
Some operations, such as deletion and
inserting before a node, become easier
Disadvantages:
Requires more space
List manipulations are slower (because
more links must be changed)
Dr. R. Jothi, VIT Chennai
Summary of operations in Linked List
Assume a Linked List L having n elements. Then time needed for each of the
operations
Creating
an empty list O(1)
List with one head node O(1)
Insert an element
at beginning O(1)
at end O(1)
at middle – after/before an element O(1) (assuming location is known)
Search and Traversal O(n)
Delete
at beginning O(1)
at end O(1)
at middle – after/before an element O(1) (assuming location is known)
Dr. R. Jothi, VIT Chennai
Exercise
Print elements of DLL in reverse order in single scan
Circular Doubly Linked list
Dr. R. Jothi, VIT Chennai
