Data Structure - Doubly Linked List
A doubly linked list (Doubly Linked List) is an extension of a singly linked list. In addition to pointing to the next node, each node also stores a pointer to the previous node, thus forming a chain structure that is reachable in both directions.
Structure and Characteristics of Doubly Linked List
struct Node { int data; struct Node* prev; struct Node* next; };
prev points to the previous node | data stores data | next points to the next node
Core advantages: you can directly delete any node (no need to save the predecessor), and it supports bidirectional traversal
As shown in the figure above, each node of a doubly linked list hasprevandnexttwo pointers.
In C language, the definition of a doubly linked list node is as follows:
Example
int data; /* Data field */
struct Node* prev; /* Predecessor pointer: points to the previous node */
struct Node* next; /* Successor pointer: points to the next node */
};
Compared with a singly linked list, the biggest advantage of a doubly linked list is that you can directly access its predecessor and successor from any node, which means that the deletion operation no longer needs to save an extra reference to the predecessor node.
In a singly linked list, to delete a specified node, you must know its predecessor node to complete the pointer adjustment. In a doubly linked list, since each node itself stores a prev pointer, the deletion operation can be done directly.
Basic Operations
Insertion Operation
Insertion into a doubly linked list requires adjusting the prev/next pointers of the new node as well as the pointers of its predecessor and successor nodes, involving a total of four pointer adjustments.
Example
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
/* Create a new node */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* Insert a node at the head Steps: the new node's next points to the original head node, and the original head node's prev points to the new node */
/* The new node becomes the new head node */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; /* Insert a new node after a specified node You need to operate 4 pointers: 1-2: the new node's prev and next 3: the successor node's prev (if it exists) 4: the predecessor node's next */
}
/* The new node's next points to the original successor */
/* The new node's prev points to the predecessor */
/* The original successor's prev points to the new node */
/* The predecessor's next points to the new node */
Deletion Operation
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) return;
struct Node* newNode = createNode(value);
newNode->next = prevNode->next; Example
newNode->prev = prevNode; /* Delete a specified node (no need to know the predecessor node; this is the biggest advantage of a doubly linked list) Steps: connect the previous and next nodes to each other, skip the current node, and then free the current node */
if (prevNode->next != NULL) {
prevNode->next->prev = newNode; /* If the head node is deleted, update the head pointer */
}
prevNode->next = newNode; /* Make the predecessor node's next point to the successor node */
}
Deletion Operation
Example
A doubly linked list supports two traversal methods: forward and reverse.
void deleteNode(struct Node** headRef, struct Node* del) {
if (*headRef == NULL || del == NULL) return;
Example
if (*headRef == del) {
*headRef = del->next;
}
/* Forward traversal: start from head, go along the next direction */
if (del->prev != NULL) {
del->prev->next = del->next;
}
"Forward traversal: "
if (del->next != NULL) {
del->next->prev = del->prev;
}
free(del); /* Reverse traversal: start from tail, go along the prev direction You need to find the tail node first */
}
Traversal Operation (Bidirectional)
/* From the tail, return to the head along the prev direction */
Example
/* Forward traversal: start from head, along next direction */
void traverseForward(struct Node* head) {
printf(Forward traversal:);
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
/* Reverse traversal: from tail, along prev direction
Need to find the tail node first */
void traverseBackward(struct Node* head) {
if (head == NULL) return;
/* First move to the last node (i.e., the tail) */
struct Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
/* Return from the tail to the head along the prev direction */
printf("Reverse traversal: ");
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->prev;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
/* Build linked list: 10 <-> 20 <-> 30 */
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverseForward(head); /* Output: forward traversal: 10 20 30 */
traverseBackward(head); /* Output: reverse traversal: 30 20 10 */
return 0;
}
Doubly Linked List vs Singly Linked List
| Comparison dimension | Singly linked list | Doubly linked list |
|---|---|---|
| Node structure | data + next | data + prev + next |
| Extra memory per node | 8 bytes (64-bit system) | 16 bytes (64-bit system) |
| Forward traversal | Supported | Supported |
| Reverse traversal | Not supported | Supported |
| Delete node | Need to know predecessor node | No predecessor needed, can delete directly |
| Insertion operation | Adjust 1~2 pointers | Adjust 4 pointers |