您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
链表是一种常见的数据结构，它通过节点之间的指针连接来存储数据。与数组不同，链表的大小可以动态调整，插入和删除操作也更加高效。双向链表和双向循环链表是链表的两种常见变体，它们在许多应用中都有广泛的使用。本文将详细介绍如何使用C语言实现这两种链表。
双向链表（Doubly Linked List）是一种链表，其中每个节点包含两个指针：一个指向下一个节点，另一个指向前一个节点。这种结构使得双向链表可以从两个方向遍历。
在C语言中，双向链表的节点可以定义如下：
struct Node {
int data; // 数据域
struct Node* prev; // 指向前一个节点的指针
struct Node* next; // 指向下一个节点的指针
};
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
在双向链表中插入节点有多种方式，例如在头部插入、在尾部插入或在某个节点后插入。
void insertAtHead(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
newNode->next = *head;
(*head)->prev = newNode;
*head = newNode;
}
}
void insertAtTail(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
}
void insertAfter(struct Node* prevNode, int data) {
if (prevNode == NULL) {
printf("Previous node cannot be NULL\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
if (prevNode->next != NULL) {
prevNode->next->prev = newNode;
}
prevNode->next = newNode;
newNode->prev = prevNode;
}
删除节点也有多种方式，例如删除头部节点、删除尾部节点或删除某个特定节点。
void deleteAtHead(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
*head = (*head)->next;
if (*head != NULL) {
(*head)->prev = NULL;
}
free(temp);
}
void deleteAtTail(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
if (temp->prev != NULL) {
temp->prev->next = NULL;
} else {
*head = NULL;
}
free(temp);
}
void deleteNode(struct Node** head, struct Node* delNode) {
if (*head == NULL || delNode == NULL) {
printf("List or node is empty\n");
return;
}
if (*head == delNode) {
*head = delNode->next;
}
if (delNode->next != NULL) {
delNode->next->prev = delNode->prev;
}
if (delNode->prev != NULL) {
delNode->prev->next = delNode->next;
}
free(delNode);
}
双向链表可以从两个方向遍历：从头到尾或从尾到头。
void traverseForward(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
void traverseBackward(struct Node* tail) {
struct Node* temp = tail;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->prev;
}
printf("NULL\n");
}
双向循环链表（Doubly Circular Linked List）是双向链表的一种变体，其中最后一个节点的next指针指向第一个节点，第一个节点的prev指针指向最后一个节点，形成一个循环。
双向循环链表的节点结构与双向链表相同：
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
与双向链表相同。
在双向循环链表中插入节点时，需要注意循环的特性。
void insertAtHeadCircular(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
*head = newNode;
}
}
void insertAtTailCircular(struct Node** head, int data) {
struct Node* newNode = createNode(data);
if (*head == NULL) {
newNode->next = newNode;
newNode->prev = newNode;
*head = newNode;
} else {
newNode->next = *head;
newNode->prev = (*head)->prev;
(*head)->prev->next = newNode;
(*head)->prev = newNode;
}
}
void insertAfterCircular(struct Node* prevNode, int data) {
if (prevNode == NULL) {
printf("Previous node cannot be NULL\n");
return;
}
struct Node* newNode = createNode(data);
newNode->next = prevNode->next;
newNode->prev = prevNode;
prevNode->next->prev = newNode;
prevNode->next = newNode;
}
在双向循环链表中删除节点时，同样需要注意循环的特性。
void deleteAtHeadCircular(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
} else {
struct Node* temp = *head;
(*head)->prev->next = (*head)->next;
(*head)->next->prev = (*head)->prev;
*head = (*head)->next;
free(temp);
}
}
void deleteAtTailCircular(struct Node** head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
if ((*head)->next == *head) {
free(*head);
*head = NULL;
} else {
struct Node* temp = (*head)->prev;
temp->prev->next = *head;
(*head)->prev = temp->prev;
free(temp);
}
}
void deleteNodeCircular(struct Node** head, struct Node* delNode) {
if (*head == NULL || delNode == NULL) {
printf("List or node is empty\n");
return;
}
if (*head == delNode) {
deleteAtHeadCircular(head);
} else {
delNode->prev->next = delNode->next;
delNode->next->prev = delNode->prev;
free(delNode);
}
}
双向循环链表的遍历与双向链表类似，但由于是循环的，遍历时需要特别注意终止条件。
void traverseForwardCircular(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("HEAD\n");
}
void traverseBackwardCircular(struct Node* head) {
if (head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = head->prev;
do {
printf("%d -> ", temp->data);
temp = temp->prev;
} while (temp != head->prev);
printf("TL\n");
}
本文详细介绍了如何使用C语言实现双向链表和双向循环链表。通过定义节点结构、实现插入、删除和遍历等基本操作，我们可以灵活地使用这两种链表来解决实际问题。双向链表和双向循环链表在许多应用中都有广泛的使用，例如实现LRU缓存、浏览器历史记录等。希望本文能帮助你更好地理解和应用这两种数据结构。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。