Doubly linked list is a list in which each node consists of three fields. They are data field, pointer to previous node and pointer to successor node.
Structure of a node:
struct node {
struct node *prev;
int data;
struct node *next;
};
+---------------------------------+
| prev | data | next |
+---------------------------------+
prev - pointer to the previous node
next - pointer to the successor node
How to create a node in doubly linked list?
Dynamically allocate memory for the newnode and load the given data in it.
struct node * nodeCreation(int data) {
struct node *newnode;
newnode = (struct node *)malloc(sizeof (struct node));
newnode->data = data;
newnode->next = NULL;
newnode->prev = NULL;
return (newnode);
}
Trick to simplify doubly linked list implementation:
Create two sentinels (head and tail - dummy nodes) and establish a connection between them. This simplifies insertion and deletion operation in doubly linked list.
+------------------------+ +------------------------+
| NULL | 0 | next -|<--->|- prev | 0 | NULL |
+------------------------+ +------------------------+
head tail
In this case, we don't need to do any additional operation with head and tail. All we need to do is to insert or delete nodes that are present between dummy sentinels. This ensures safety and avoids additional overhead(operation with head and tail modification).
Insertion In Doubly Linked List:
+------------------------+ +----------------------+ +--------------------+
| NULL | 0 | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL |
+------------------------+ +----------------------+ +--------------------+
head(1100) node1(1200) tail(1300)
Here, head and tail are dummy nodes. Insert a new node(node2) between node1 and tail.
+----------------------+
| NULL | 20 | NULL |
+----------------------+
newnode(1400)
newnode->prev = node1;
newnode->next = node1->next;
node1->next->prev = newnode;
node1->next = newnode;
+-----------------+ +-----------------+ +------------------+ +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+ +-----------------+ +------------------+ +-------------------+
head(1100) node1(1200) newnode(1400) tail(1300)
Deletion In Doubly Linked List:
+-----------------+ +-----------------+ +-----------------+ +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+ +-----------------+ +-----------------+ +-------------------+
head(1100) node1(1200) newnode(1400) tail(1300)
Delete newnode from the linked list.
node2->prev->next = node2->next;
node2->next->prev = node2->prev;
free(node2);
+------------------------+ +----------------------+ +-------------------+
| NULL | 0 | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL|
+------------------------+ +----------------------+ +-------------------+
head(1100) node1(1200) tail(1300)
Structure of a node:
struct node {
struct node *prev;
int data;
struct node *next;
};
+---------------------------------+
| prev | data | next |
+---------------------------------+
prev - pointer to the previous node
next - pointer to the successor node
How to create a node in doubly linked list?
Dynamically allocate memory for the newnode and load the given data in it.
struct node * nodeCreation(int data) {
struct node *newnode;
newnode = (struct node *)malloc(sizeof (struct node));
newnode->data = data;
newnode->next = NULL;
newnode->prev = NULL;
return (newnode);
}
Trick to simplify doubly linked list implementation:
Create two sentinels (head and tail - dummy nodes) and establish a connection between them. This simplifies insertion and deletion operation in doubly linked list.
+------------------------+ +------------------------+
| NULL | 0 | next -|<--->|- prev | 0 | NULL |
+------------------------+ +------------------------+
head tail
In this case, we don't need to do any additional operation with head and tail. All we need to do is to insert or delete nodes that are present between dummy sentinels. This ensures safety and avoids additional overhead(operation with head and tail modification).
Insertion In Doubly Linked List:
+------------------------+ +----------------------+ +--------------------+
| NULL | 0 | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL |
+------------------------+ +----------------------+ +--------------------+
head(1100) node1(1200) tail(1300)
Here, head and tail are dummy nodes. Insert a new node(node2) between node1 and tail.
+----------------------+
| NULL | 20 | NULL |
+----------------------+
newnode(1400)
newnode->prev = node1;
newnode->next = node1->next;
node1->next->prev = newnode;
node1->next = newnode;
+-----------------+ +-----------------+ +------------------+ +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+ +-----------------+ +------------------+ +-------------------+
head(1100) node1(1200) newnode(1400) tail(1300)
Deletion In Doubly Linked List:
+-----------------+ +-----------------+ +-----------------+ +-------------------+
|NULL| 0 |1200|<-->|1100| 10 |1400|<-->|1200| 20 |1300|<-->|1400 | 0 | NULL|
+-----------------+ +-----------------+ +-----------------+ +-------------------+
head(1100) node1(1200) newnode(1400) tail(1300)
Delete newnode from the linked list.
node2->prev->next = node2->next;
node2->next->prev = node2->prev;
free(node2);
+------------------------+ +----------------------+ +-------------------+
| NULL | 0 | 1200 -|<---->|- 1100 | 10 | 1300-|<--->|-1200 | 0 | NULL|
+------------------------+ +----------------------+ +-------------------+
head(1100) node1(1200) tail(1300)
See Also:
C Program To Merge Two Arrays
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)
C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)
C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List
C Program To Implement Doubly Linked List - Insert, Delete, Traverse & Search:
#include <stdlib.h>
struct node {
int data;
struct node *next, *prev;
};
struct node *head = NULL, *tail = NULL;
int nodeCount = 0;
struct node * createNode(int data) {
struct node *newnode;
newnode = (struct node *)malloc(sizeof (struct node));
newnode->data = data;
newnode->next = NULL;
newnode->prev = NULL;
return (newnode);
}
void createDummies() {
head = (struct node *)malloc(sizeof (struct node));
tail = (struct node *)malloc(sizeof (struct node));
head->data = tail->data = 0;
head->next = tail;
tail->prev = head;
head->prev = tail->next = NULL;
}
void insert(int data, int pos) {
struct node *newnode, *temp1;
int count = 1;
newnode = createNode(data);
temp1 = head;
while (temp1) {
if (count == pos) {
newnode->next = temp1->next;
newnode->prev = temp1;
temp1->next->prev = newnode;
temp1->next = newnode;
nodeCount++;
break;
}
temp1 = temp1->next;
count++;
}
return;
}
void insertAtStart(int data) {
struct node *newnode = createNode(data);
newnode->next = head->next;
newnode->prev = head;
head->next->prev = newnode;
head->next = newnode;
nodeCount++;
}
void insertAtEnd(int data) {
struct node *newnode = createNode(data);
newnode->next = tail;
newnode->prev = tail->prev;
tail->prev->next = newnode;
tail->prev = newnode;
nodeCount++;
}
void delete(int data) {
struct node *temp1, *temp2;
temp1 = head->next;
while (temp1 != tail) {
if (temp1->data == data) {
temp2 = temp1;
temp1->prev->next = temp1->next;
temp1->next->prev = temp1->prev;
free(temp2);
nodeCount--;
return;
}
temp1 = temp1->next;
}
printf("Given node is not present in the List\n");
return;
}
void deleteList() {
struct node *temp2, *temp1 = head->next;
while (temp1 != tail) {
temp1->prev->next = temp1->next;
temp1->next->prev = temp1->prev;
temp2 = temp1;
free(temp1);
temp1 = temp2->next;
}
nodeCount = 0;
return;
}
void searchNode(int data) {
struct node *temp = head->next;
while (temp != tail) {
if (temp->data == data) {
printf("Given node is present\n");
return;
}
temp = temp->next;
}
printf("Given node is not present in the list\n");
return;
}
void walkList() {
struct node *ptr = head->next;
int flag = 1, i = 1;
if (head->next == tail) {
printf("List is Empty\n");
return;
}
printf("Data in List:\n");
while (ptr != tail) {
if (ptr->prev != head) {
printf(" /\\ \n");
printf(" ||\n");
flag = 0;
}
printf("+------------------------+\n");
printf("|node%2d addr:0x%08x |\n", i, (unsigned int)ptr);
printf("+------------------------+\n");
printf("|data: %4d |\n", ptr->data);
printf("-------------------------+\n");
printf("|prev: 0x%08x |\n",
ptr->prev == head ? 0 : (unsigned int)ptr->prev);
printf("+------------------------+\n");
printf("|next: 0x%08x |\n",
ptr->next == tail ? 0 : (unsigned int)ptr->next);
printf("+------------------------+\n");
ptr = ptr->next;
if (ptr != tail) {
printf(" || \n");
printf(" \\/ \n");
}
i++;
}
}
int main() {
int data, ch, pos;
createDummies();
while (1) {
printf("1. Insert\n2. Delete\n");
printf("3. Walk List\n4. Search Node\n");
printf("5. Delete List\n6. Insert At start\n");
printf("7. Insert at End\n8. Exit\n");
printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the node position(1 - %d)", nodeCount+1);
scanf("%d", &pos);
if (pos <= 0 || pos > nodeCount+1) {
printf("Please enter correct position\n");
} else {
printf("Enter ur data to insert:");
scanf("%d", &data);
insert(data, pos);
}
break;
case 2:
printf("Enter the data to delete:");
scanf("%d", &data);
delete(data);
break;
case 3:
walkList();
break;
case 4:
printf("Enter the data to be searched:");
scanf("%d", &data);
searchNode(data);
break;
case 5:
deleteList();
break;
case 6:
printf("Enter ur data to insert at start:");
scanf("%d", &data);
insertAtStart(data);
break;
case 7:
printf("Enter ur data to insert:");
scanf("%d", &data);
insertAtEnd(data);
break;
case 8:
exit(0);
default:
printf("U have entered wrong option\n");
break;
}
}
return 0;
}
Output: (Doubly Linked List Example)
jp@jp-VirtualBox:$ ./a.out
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:1
Enter the node position(1 - 1)1
Enter ur data to insert:10
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:6
Enter ur data to insert at start:20
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:7
Enter ur data to insert:30
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
Data in List:
+------------------------------+
|node 1 addr:0x09af8038 |
+------------------------------+
|data: 20 |
+------------------------------+
|prev: 0x00000000 |
+------------------------------+
|next: 0x09af8028 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 2 addr:0x09af8028 |
+------------------------------+
|data: 10 |
+------------------------------+
|prev: 0x09af8038 |
+------------------------------+
|next: 0x09af8048 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 3 addr:0x09af8048 |
+------------------------------+
|data: 30 |
+------------------------------+
|prev: 0x09af8028 |
+------------------------------+
|next: 0x00000000 |
+------------------------------+
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:2
Enter the data to delete:10
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
Data in List:
+------------------------------+
|node 1 addr:0x09af8038 |
+------------------------------+
|data: 20 |
+------------------------------+
|prev: 0x00000000 |
+------------------------------+
|next: 0x09af8048 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 2 addr:0x09af8048 |
+------------------------------+
|data: 30 |
+------------------------------+
|prev: 0x09af8038 |
+------------------------------+
|next: 0x00000000 |
+------------------------------+
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:4
Enter the data to be searched:30
Given node is present
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:5
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
List is Empty
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:8
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:1
Enter the node position(1 - 1)1
Enter ur data to insert:10
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:6
Enter ur data to insert at start:20
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:7
Enter ur data to insert:30
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
Data in List:
+------------------------------+
|node 1 addr:0x09af8038 |
+------------------------------+
|data: 20 |
+------------------------------+
|prev: 0x00000000 |
+------------------------------+
|next: 0x09af8028 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 2 addr:0x09af8028 |
+------------------------------+
|data: 10 |
+------------------------------+
|prev: 0x09af8038 |
+------------------------------+
|next: 0x09af8048 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 3 addr:0x09af8048 |
+------------------------------+
|data: 30 |
+------------------------------+
|prev: 0x09af8028 |
+------------------------------+
|next: 0x00000000 |
+------------------------------+
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:2
Enter the data to delete:10
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
Data in List:
+------------------------------+
|node 1 addr:0x09af8038 |
+------------------------------+
|data: 20 |
+------------------------------+
|prev: 0x00000000 |
+------------------------------+
|next: 0x09af8048 |
+------------------------------+
||
\/
/\
||
+------------------------------+
|node 2 addr:0x09af8048 |
+------------------------------+
|data: 30 |
+------------------------------+
|prev: 0x09af8038 |
+------------------------------+
|next: 0x00000000 |
+------------------------------+
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:4
Enter the data to be searched:30
Given node is present
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:5
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:3
List is Empty
1. Insert
2. Delete
3. Walk List
4. Search Node
5. Delete List
6. Insert At start
7. Insert at End
8. Exit
Enter your choice:8
ReplyDeleteVery informative article.Thank you author for posting this kind of article .
http://www.wikitechy.com/view-article/explain-in-details-about-array-implementation-of-linked-list-in-c
Both are really good,.
Cheers,
Venkat
nice one example for understanding doubly linklist.
ReplyDeletebut in program how exactly it works.