双向链表（Doubly Linked List）是一种常见的数据结构，每个节点包含两部分信息：数据域和指针域。数据域存储节点的值，而指针域包含两个指针：一个指向下一个节点（next），另一个指向前一个节点（prev）。这种结构允许链表在正向和反向都能遍历。
双向链表节点结构体
|
typedef struct DoublyLinkedListNode { |
|
int data; // 数据域 |
|
struct DoublyLinkedListNode *next; // 指向下一个节点的指针 |
|
struct DoublyLinkedListNode *prev; // 指向前一个节点的指针 |
|
} DoublyLinkedListNode, *DoublyLinkedList; |
双向链表的基本操作
初始化双向链表
|
// 初始化双向链表 |
|
DoublyLinkedList InitDoublyLinkedList() { |
|
DoublyLinkedList head = (DoublyLinkedListNode *)malloc(sizeof(DoublyLinkedListNode)); |
|
if (!head) { |
|
exit(1); // 内存分配失败 |
|
} |
|
head->next = head; // 指向自己，形成循环 |
|
head->prev = head; |
|
return head; |
|
} |
插入节点
|
// 在双向链表的尾部插入节点 |
|
void InsertAtTail(DoublyLinkedList *head, int value) { |
|
DoublyLinkedList newNode = (DoublyLinkedListNode *)malloc(sizeof(DoublyLinkedListNode)); |
|
if (!newNode) { |
|
exit(1); // 内存分配失败 |
|
} |
|
newNode->data = value; |
|
newNode->next = *head; |
|
newNode->prev = (*head)->prev; |
|
(*head)->prev->next = newNode; |
|
(*head)->prev = newNode; |
|
} |
删除节点
|
// 从双向链表中删除指定节点 |
|
void DeleteNode(DoublyLinkedList *head, int value) { |
|
DoublyLinkedList current = *head->next; // 从头节点的下一个节点开始遍历 |
|
while (current != *head && current->data != value) { |
|
current = current->next; |
|
} |
|
if (current == *head) { |
|
return; // 未找到要删除的节点 |
|
} |
|
|
|
current->prev->next = current->next; |
|
current->next->prev = current->prev; |
|
free(current); // 释放要删除节点的内存 |
|
} |
遍历链表
|
// 遍历双向链表并打印元素 |
|
void PrintList(DoublyLinkedList head) { |
|
DoublyLinkedList current = head->next; // 从头节点的下一个节点开始遍历 |
|
while (current != head) { |
|
printf("%d ", current->data); |
|
current = current->next; |
|
} |
|
printf("\n"); |
|
} |
释放双向链表内存
|
// 释放双向链表内存 |
|
void FreeList(DoublyLinkedList head) { |
|
DoublyLinkedList current = head->next; |
|
while (current != head) { |
|
DoublyLinkedList temp = current; |
|
current = current->next; |
|
free(temp); |
|
} |
|
free(head); // 释放头节点 |
|
} |
main 函数示例
在main函数中，我们可以创建一个双向链表，执行插入、删除和打印操作。
c复制代码
|
int main() { |
|
DoublyLinkedList head = InitDoublyLinkedList(); // 初始化双向链表 |
|
|
|
// 插入节点 |
|
InsertAtTail(&head, 1); |
|
InsertAtTail(&head, 2); |
|
InsertAtTail(&head, 3); |
|
|
|
// 打印链表 |
|
PrintList(head); |
|
|
|
// 删除节点 |
|
DeleteNode(&head, 2); |
|
|
|
// 打印链表 |
|
PrintList(head); |
|
|
|
// 释放链表内存 |
|
FreeList(head); |
|
|
|
return 0; |
|
} |
请注意，双向链表在插入和删除节点时，都需要维护两个方向的指针，这增加了操作的复杂性，但提供了更灵活的遍历方式。此外，双向链表的内存管理也需要更小心，确保所有节点的内存都被正确释放。
