C语言编程数据结构带头双向循环链表全面详解

什么是带头双向循环链表

• 带头链表：链表的第一个节点不存放数据，称为头节点，起到标识链表的作用。
• 双向链表：一个节点有两个指针，一个指向前一个节点，一个指向后一个节点。
• 循环链表：最后一个节点的指针指向第一个节点，形成循环。

因此，带头双向循环链表就是在普通的双向循环链表的基础上，增加了头节点。

定义带头双向循环链表

typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LinkedList {
    Node* head;
    int length;
} LinkedList;

其中，LinkedList表示链表本身，它包括一个头结点head和链表长度length；Node表示链表中的节点，包括数据data和前后指针prev、next。

创建带头双向循环链表

下面的代码展示了如何创建一个带头双向循环链表，这个链表包含5个节点，分别存储了数据1到5：

LinkedList* createLinkedList() {
    LinkedList* linkedList = (LinkedList*) malloc(sizeof(LinkedList));
    linkedList->head = (Node*) malloc(sizeof(Node));
    linkedList->head->prev = linkedList->head->next = linkedList->head;
    linkedList->length = 0;

    for(int i=1; i<=5; i++) {
        Node* node = (Node*) malloc(sizeof(Node));
        node->data = i;
        node->prev = linkedList->head->prev;
        node->next = linkedList->head;
        linkedList->head->prev->next = node;
        linkedList->head->prev = node;
        linkedList->length ++;
    }
    return linkedList;
}

首先创建LinkedList和head节点，并将head节点的prev和next指针都指向自己，表示这个链表为空链表。

然后循环5次，每次创建新节点并插入链表末尾。要注意的是，新节点的prev指针需要指向最后一个节点（即head->prev），next指针需要指向头节点（即head），同时还需要更新链表最后一个节点（即head->prev）和链表长度。

遍历带头双向循环链表

遍历带头双向循环链表可以借助头节点来实现，具体代码如下：

void traverseLinkedList(LinkedList* linkedList) {
    Node* pNode = linkedList->head->next;
    while(pNode != linkedList->head) {
        printf("%d ", pNode->data);
        pNode = pNode->next;
    }
    printf("\n");
}

首先定义一个指针pNode指向头节点的后一个节点，然后通过循环遍历整个链表，遇到头节点的时候退出。每次输出节点的数据即可。

带头双向循环链表的插入和删除节点

带头双向循环链表的节点插入和删除分别有四种情况需要考虑，即在链表首尾插入和删除：

• 在链表头部插入节点。具体代码如下：

void insertNodeAtHead(LinkedList* linkedList, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prev = linkedList->head;
    node->next = linkedList->head->next;
    linkedList->head->next->prev = node;
    linkedList->head->next = node;
    linkedList->length ++;
}

首先创建新节点，并将新节点的prev指针指向头节点，next指针指向头节点的后一个节点。然后需要更新头节点和新节点的前后指针，最后更新链表长度即可。

• 在链表尾部插入节点。具体代码如下：

void insertNodeAtTail(LinkedList* linkedList, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prev = linkedList->head->prev;
    node->next = linkedList->head;
    linkedList->head->prev->next = node;
    linkedList->head->prev = node;
    linkedList->length ++;
}

创建新节点，将新节点的prev指针指向链表最后一个节点（即head->prev），next指针指向头节点。然后需要更新链表最后一个节点和新节点的前后指针，最后更新链表长度即可。

• 删除链表头部节点。具体代码如下：

void deleteNodeAtHead(LinkedList* linkedList) {
    if(linkedList->length == 0) {
        return;
    }
    Node* node = linkedList->head->next;
    linkedList->head->next = node->next;
    node->next->prev = linkedList->head;
    free(node);
    linkedList->length --;
}

首先需要判断链表是否为空，如果为空就直接返回。然后定义一个指针node指向第一个节点，更新头节点的指针，释放节点所占的内存，最后更新链表长度。

• 删除链表尾部节点。具体代码如下：

void deleteNodeAtTail(LinkedList* linkedList) {
    if(linkedList->length == 0) {
        return;
    }
    Node* node = linkedList->head->prev;
    linkedList->head->prev = node->prev;
    node->prev->next = linkedList->head;
    free(node);
    linkedList->length --;
}

同样需要判断链表是否为空，如果为空就直接返回。然后定义一个指针node指向最后一个节点，更新链表最后一个节点的指针，释放节点所占的内存，最后更新链表长度。

以下是示例代码，创建一个链表并输出，然后依次在首尾插入和删除节点，再输出链表：

#include <stdio.h>
#include <stdlib.h>

// 定义结构体
typedef struct Node {
    int data;
    struct Node* prev;
    struct Node* next;
} Node;

typedef struct LinkedList {
    Node* head;
    int length;
} LinkedList;

// 创建链表
LinkedList* createLinkedList() {
    LinkedList* linkedList = (LinkedList*) malloc(sizeof(LinkedList));
    linkedList->head = (Node*) malloc(sizeof(Node));
    linkedList->head->prev = linkedList->head->next = linkedList->head;
    linkedList->length = 0;

    for(int i=1; i<=5; i++) {
        Node* node = (Node*) malloc(sizeof(Node));
        node->data = i;
        node->prev = linkedList->head->prev;
        node->next = linkedList->head;
        linkedList->head->prev->next = node;
        linkedList->head->prev = node;
        linkedList->length ++;
    }
    return linkedList;
}

// 遍历链表
void traverseLinkedList(LinkedList* linkedList) {
    Node* pNode = linkedList->head->next;
    while(pNode != linkedList->head) {
        printf("%d ", pNode->data);
        pNode = pNode->next;
    }
    printf("\n");
}

// 在链表头部插入节点
void insertNodeAtHead(LinkedList* linkedList, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prev = linkedList->head;
    node->next = linkedList->head->next;
    linkedList->head->next->prev = node;
    linkedList->head->next = node;
    linkedList->length ++;
}

// 在链表尾部插入节点
void insertNodeAtTail(LinkedList* linkedList, int data) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->data = data;
    node->prev = linkedList->head->prev;
    node->next = linkedList->head;
    linkedList->head->prev->next = node;
    linkedList->head->prev = node;
    linkedList->length ++;
}

// 删除链表头部节点
void deleteNodeAtHead(LinkedList* linkedList) {
    if(linkedList->length == 0) {
        return;
    }
    Node* node = linkedList->head->next;
    linkedList->head->next = node->next;
    node->next->prev = linkedList->head;
    free(node);
    linkedList->length --;
}

// 删除链表尾部节点
void deleteNodeAtTail(LinkedList* linkedList) {
    if(linkedList->length == 0) {
        return;
    }
    Node* node = linkedList->head->prev;
    linkedList->head->prev = node->prev;
    node->prev->next = linkedList->head;
    free(node);
    linkedList->length --;
}

int main() {
    // 创建链表并输出
    LinkedList* linkedList = createLinkedList();
    printf("创建链表并输出：\n");
    traverseLinkedList(linkedList);

    // 在首尾插入元素
    printf("在链表头部插入元素3：\n");
    insertNodeAtHead(linkedList, 3);
    traverseLinkedList(linkedList);
    printf("在链表尾部插入元素6：\n");
    insertNodeAtTail(linkedList, 6);
    traverseLinkedList(linkedList);

    // 删除首尾元素
    printf("删除链表头部元素：\n");
    deleteNodeAtHead(linkedList);
    traverseLinkedList(linkedList);
    printf("删除链表尾部元素：\n");
    deleteNodeAtTail(linkedList);
    traverseLinkedList(linkedList);

    return 0;
}

输出结果：

创建链表并输出：
1 2 3 4 5 
在链表头部插入元素3：
3 1 2 3 4 5 
在链表尾部插入元素6：
3 1 2 3 4 5 6 
删除链表头部元素：
1 2 3 4 5 6 
删除链表尾部元素：
1 2 3 4 5 

以上是C语言编程数据结构带头双向循环链表全面详解，希望对你有所帮助。