Doubly Linked List in C
Here you will learn and get the program code of Doubly Linked List in C programming using Data Structure.
What is doubly linked list?
A doubly linked list in C is a fundamental data structure that involves a sequence of elements known as nodes. Each node carries both data and two pointers: one pointing to the previous node and another to the next node. It allowing for easy traversal and manipulation in both directions.
A doubly linked list in C:
- Each node has data and two pointers(previous node, and next node).
- The prev pointer of the first node and the next pointer of the last node typically hold NULL.
- In the middle, node points the previous node address and next node address.
- Elements can be easily inserted or removed at the list’s beginning, end, or in the middle.
- The two pointers offer advanced capabilities like seamless reverse traversal.
Doubly linked lists provide advantages such as enhanced flexibility compared to Singly linked lists. However, they consume slightly more memory due to the additional pointer in each node.
Difference between Singly and Doubly Linked list
Feature | Singly Link List | Doubly Link List |
| Direction of Pointers | Each node points to the next node (forward only). | Each node points to both the next and previous nodes. |
| Memory Usage | Requires less memory as it stores only one pointer. | Requires more memory due to two pointers per node. |
| Traversal Efficiency | Forward traversal is efficient; backward is not. | Efficient for both forward and backward traversal. |
| Insertion/Deletion | Easier to insert/delete at the beginning. | Allows easy insertion/deletion at both ends and within. |
| Implementation Complexity | Simpler to implement and requires less code. | More complex to implement and requires more code. |
Doubly Linked List in C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 | //doubly linked list in c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* prev; struct Node* next; }; struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Memory allocation failed!\n"); exit(1); } newNode->data = data; newNode->prev = NULL; newNode->next = NULL; return newNode; } void insertAtEnd(struct Node** head, int data) { struct Node* newNode = createNode(data); if (*head == NULL) { *head = newNode; } else { struct Node* current = *head; while (current->next != NULL) { current = current->next; } current->next = newNode; newNode->prev = current; } } void insertAtBeginning(struct Node** head, int data) { struct Node* newNode = createNode(data); newNode->next = *head; if (*head != NULL) { (*head)->prev = newNode; } *head = newNode; } void insertInBetween(struct Node** head, int data, int afterData) { if (*head == NULL) { printf("The list is empty.\n"); return; } struct Node* current = *head; while (current != NULL) { if (current->data == afterData) { struct Node* newNode = createNode(data); newNode->prev = current; newNode->next = current->next; if (current->next != NULL) { current->next->prev = newNode; } current->next = newNode; printf("Node inserted successfully.\n"); return; } current = current->next; } printf("Node with data %d not found.\n", afterData); } void deleteNode(struct Node** head, int data) { if (*head == NULL) { printf("List is empty.\n"); return; } struct Node* current = *head; while (current != NULL) { if (current->data == data) { if (current->prev != NULL) { current->prev->next = current->next; } else { *head = current->next; } if (current->next != NULL) { current->next->prev = current->prev; } free(current); printf("Node deleted successfully.\n"); return; } current = current->next; } printf("Node with data %d not found.\n", data); } void reverseList(struct Node** head) { struct Node* current = *head; struct Node* temp = NULL; while (current != NULL) { temp = current->prev; current->prev = current->next; current->next = temp; current = current->prev; } if (temp != NULL) { *head = temp->prev; } } void displayList(struct Node* head) { struct Node* current = head; while (current != NULL) { printf("%d <-> ", current->data); current = current->next; } printf("NULL\n"); } void freeList(struct Node* head) { struct Node* current = head; while (current != NULL) { struct Node* temp = current; current = current->next; free(temp); } } int main() { struct Node* head = NULL; int ch, data, value, afterValue; while (1) { printf("\nDoubly Linked List Menu:\n"); printf("1. Create list\n"); printf("2. Insert at beginning\n"); printf("3. Insert at end\n"); printf("4. Insert in between\n"); printf("5. Display list\n"); printf("6. Delete a node\n"); printf("7. Reverse the list\n"); printf("8. Delete list\n"); printf("9. Exit\n"); printf("Enter your choice: "); scanf("%d", &ch); switch (ch) { case 1: head = NULL; // Clear any existing list printf("List created.\n"); break; case 2: printf("Enter data to insert: "); scanf("%d", &data); insertAtBeginning(&head, data); printf("Data inserted at the beginning.\n"); break; case 3: printf("Enter data to insert: "); scanf("%d", &data); insertAtEnd(&head, data); printf("Data inserted at the end.\n"); break; case 4: printf("Enter data to insert: "); scanf("%d", &data); printf("Enter value after which to insert: "); scanf("%d", &afterValue); insertInBetween(&head, data, afterValue); break; case 5: if (head == NULL) { printf("The list is empty.\n"); } else { printf("Doubly Linked List: "); displayList(head); } break; case 6: if (head == NULL) { printf("The list is empty.\n"); } else { printf("Enter data to delete: "); scanf("%d", &value); deleteNode(&head, value); } break; case 7: if (head == NULL) { printf("The list is empty.\n"); } else { reverseList(&head); printf("List reversed successfully.\n"); } break; case 8: if (head == NULL) { printf("The list is already empty.\n"); } else { head = NULL; printf("List deleted successfully.\n"); } break; case 9: freeList(head); printf("Exiting.....\n"); exit(0); default: printf("Wrong choice! Try again.\n"); } } return 0; } |
Output
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 1
List created.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 2
Enter data to insert: 11
Data inserted at the beginning.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 2
Enter data to insert: 22
Data inserted at the beginning.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 2
Enter data to insert: 33
Data inserted at the beginning.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 2
Enter data to insert: 44
Data inserted at the beginning.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 3
Enter data to insert: 88
Data inserted at the end.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 4
Enter data to insert: 55
Enter value after which to insert: 44
Node inserted successfully.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 5
Doubly Linked List: 44 <-> 55 <-> 33 <-> 22 <-> 11 <-> 88 <-> NULL
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 6
Enter data to delete: 55
Node deleted successfully.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 5
Doubly Linked List: 44 <-> 33 <-> 22 <-> 11 <-> 88 <-> NULL
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 7
List reversed successfully.
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 5
Doubly Linked List: 88 <-> 11 <-> 22 <-> 33 <-> 44 <-> NULL
Doubly Linked List Menu:
1. Create list
2. Insert at beginning
3. Insert at end
4. Insert in between
5. Display list
6. Delete a node
7. Reverse the list
8. Delete list
9. Exit
Enter your choice: 9
Exiting…..