5. Doubly Linked List

5.1 Node Structure 
 struct DNode {
 int data;
 struct DNode *prev; // Pointer to previous node
 struct DNode *next; // Pointer to next node
};
 
 Visual Representation: 
 NULL ← [prev|10|next] ⇄ [prev|20|next] ⇄ [prev|30|next] → NULL
 ↑
 HEAD
 
 5.2 Advantages of Doubly Linked List 
 
 Bidirectional Traversal: Can move forward and backward 
 Easy Deletion: Don't need previous node reference 
 Easier Insertion: Can insert before a node easily 
 
 Disadvantages: 
 
 More Memory: Extra pointer per node 
 Complex Operations: Must update two pointers 
 
 5.3 Basic Operations 
 5.3.1 Insert at Beginning 
 void insertAtBeginning(struct DNode **head, int value) {
 // Create new node
 struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 newNode->prev = NULL;
 newNode->next = *head;
 
 // Update head's prev if list not empty
 if (*head != NULL) {
 (*head)->prev = newNode;
 }
 
 *head = newNode;
}
 
 Visual Steps: 
 Initial: head → [NULL|10|●] ⇄ [●|20|NULL]

Step 1: Create newNode [NULL|5|NULL]

Step 2: Connect newNode to head
newNode: [NULL|5|●] → [NULL|10|●]

Step 3: Update head's prev
[NULL|5|●] ⇄ [●|10|●]

Step 4: Update head
head → [NULL|5|●] ⇄ [●|10|●] ⇄ [●|20|NULL]
 
 5.3.2 Insert at End 
 void insertAtEnd(struct DNode **head, int value) {
 struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
 if (newNode == NULL) {
 printf("Memory allocation failed!\n");
 return;
 }
 
 newNode->data = value;
 newNode->next = NULL;
 
 // If list is empty
 if (*head == NULL) {
 newNode->prev = NULL;
 *head = newNode;
 return;
 }
 
 // Traverse to last node
 struct DNode *temp = *head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 
 // Insert at end
 temp->next = newNode;
 newNode->prev = temp;
}
 
 5.3.3 Delete Node 
 void deleteNode(struct DNode **head, struct DNode *nodeToDelete) {
 // Check if list or node is NULL
 if (*head == NULL || nodeToDelete == NULL) {
 return;
 }
 
 // If node is head
 if (*head == nodeToDelete) {
 *head = nodeToDelete->next;
 }
 
 // Update next's prev pointer
 if (nodeToDelete->next != NULL) {
 nodeToDelete->next->prev = nodeToDelete->prev;
 }
 
 // Update prev's next pointer
 if (nodeToDelete->prev != NULL) {
 nodeToDelete->prev->next = nodeToDelete->next;
 }
 
 free(nodeToDelete);
}
 
 5.3.4 Reverse Traversal 
 void displayReverse(struct DNode *head) {
 if (head == NULL) {
 printf("List is empty!\n");
 return;
 }
 
 // Go to last node
 struct DNode *temp = head;
 while (temp->next != NULL) {
 temp = temp->next;
 }
 
 // Traverse backward
 printf("List (reverse): ");
 while (temp != NULL) {
 printf("%d", temp->data);
 if (temp->prev != NULL) {
 printf(" ← ");
 }
 temp = temp->prev;
 }
 printf("\n");
}