当前位置：首页 > backend >正文

C 语言链表详解

backend 2025/5/1 9:37:14

一、链表的基本概念

1.1 链表的定义

链表是一种线性数据结构，与数组不同，它在内存中不是连续存储的。链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。这种链式存储方式使得链表在插入和删除操作上具有高效性，并且可以动态地分配内存，无需像数组那样预先确定大小。

1.2 链表的分类

链表主要分为单向链表、双向链表和循环链表：

单向链表：每个节点只包含一个指向下一个节点的指针，只能从表头向表尾单向遍历。

双向链表：每个节点除了存储数据外，还包含两个指针，一个指向前一个节点，一个指向后一个节点，支持双向遍历。

循环链表：又可分为单向循环链表和双向循环链表。在单向循环链表中，表尾节点的指针指向表头节点；双向循环链表中，表头节点的前驱指针指向表尾节点，表尾节点的后继指针指向表头节点，形成一个闭环。

二、单向链表的实现

2.1 节点的定义

在 C 语言中，通过结构体来定义链表节点。每个节点包含两部分：数据域和指针域。数据域用于存储实际的数据，指针域用于指向下一个节点。示例代码如下：


// 定义链表节点结构体typedef struct Node {int data; // 数据域，这里以整数为例，可根据需求修改struct Node* next; // 指针域，指向下一个节点} Node;

2.2 创建新节点

创建新节点的过程实际上是动态分配内存并初始化节点数据的过程。使用malloc函数在堆内存中分配空间，然后初始化节点的数据域和指针域。示例代码如下：


// 创建新节点Node* createNode(int data) {Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {printf("内存分配失败！\n");return NULL;}newNode->data = data;newNode->next = NULL;return newNode;}

2.3 链表的初始化

链表的初始化通常是创建一个空链表，即头指针指向NULL。示例代码如下：


// 初始化链表，返回头指针Node* initList() {return NULL;}

2.4 插入节点

插入节点是链表的重要操作之一，根据插入位置的不同，可分为头插法、尾插法和指定位置插入。

头插法：将新节点插入到链表头部，使新节点成为新的头节点。示例代码如下：


// 头插法插入节点Node* insertAtHead(Node* head, int data) {Node* newNode = createNode(data);newNode->next = head;return newNode;}

尾插法：将新节点插入到链表尾部。需要遍历链表找到尾节点，然后将尾节点的指针指向新节点。示例代码如下：


// 尾插法插入节点Node* insertAtTail(Node* head, int data) {Node* newNode = createNode(data);if (head == NULL) {return newNode;}Node* current = head;while (current->next != NULL) {current = current->next;}current->next = newNode;return head;}

指定位置插入：在链表的指定位置插入新节点。首先需要找到指定位置的前一个节点，然后修改指针关系。示例代码如下：


// 在指定位置插入节点Node* insertAtPosition(Node* head, int data, int position) {if (position < 1) {printf("位置无效！\n");return head;}if (position == 1) {return insertAtHead(head, data);}Node* newNode = createNode(data);Node* current = head;int count = 1;while (current != NULL && count < position - 1) {current = current->next;count++;}if (current == NULL) {printf("位置超出链表长度！\n");free(newNode);return head;}newNode->next = current->next;current->next = newNode;return head;}

2.5 删除节点

删除节点同样根据删除位置分为删除头节点、删除尾节点和删除指定位置节点。

删除头节点：将头指针指向下一个节点，然后释放原来头节点的内存。示例代码如下：


// 删除头节点Node* deleteHead(Node* head) {if (head == NULL) {printf("链表为空！\n");return NULL;}Node* temp = head;head = head->next;free(temp);return head;}

删除尾节点：需要遍历链表找到尾节点的前一个节点，将其指针置为NULL，然后释放尾节点的内存。示例代码如下：


// 删除尾节点Node* deleteTail(Node* head) {if (head == NULL) {printf("链表为空！\n");return NULL;}if (head->next == NULL) {free(head);return NULL;}Node* current = head;while (current->next->next != NULL) {current = current->next;}free(current->next);current->next = NULL;return head;}

删除指定位置节点：找到指定位置的前一个节点，修改指针关系，然后释放要删除节点的内存。示例代码如下：


// 删除指定位置节点Node* deleteAtPosition(Node* head, int position) {if (position < 1) {printf("位置无效！\n");return head;}if (position == 1) {return deleteHead(head);}Node* current = head;int count = 1;while (current != NULL && count < position - 1) {current = current->next;count++;}if (current == NULL || current->next == NULL) {printf("位置超出链表长度！\n");return head;}Node* temp = current->next;current->next = current->next->next;free(temp);return head;}

2.6 遍历链表

遍历链表是从表头开始，依次访问每个节点的数据。示例代码如下：


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

三、双向链表的实现

3.1 双向链表节点的定义

双向链表的节点比单向链表多一个指向前一个节点的指针。示例代码如下：


// 定义双向链表节点结构体typedef struct DoublyNode {int data;struct DoublyNode* prev;struct DoublyNode* next;} DoublyNode;

3.2 创建双向链表节点

与单向链表类似，使用malloc函数分配内存并初始化节点。示例代码如下：


// 创建双向链表新节点DoublyNode* createDoublyNode(int data) {DoublyNode* newNode = (DoublyNode*)malloc(sizeof(DoublyNode));if (newNode == NULL) {printf("内存分配失败！\n");return NULL;}newNode->data = data;newNode->prev = NULL;newNode->next = NULL;return newNode;}

3.3 双向链表的插入操作

双向链表的插入操作同样有头插法、尾插法和指定位置插入，不过需要同时处理前驱和后继指针。

头插法：示例代码如下：


// 双向链表头插法插入节点DoublyNode* insertDoublyAtHead(DoublyNode* head, int data) {DoublyNode* newNode = createDoublyNode(data);if (head == NULL) {return newNode;}newNode->next = head;head->prev = newNode;return newNode;}

尾插法：示例代码如下：


// 双向链表尾插法插入节点DoublyNode* insertDoublyAtTail(DoublyNode* head, int data) {DoublyNode* newNode = createDoublyNode(data);if (head == NULL) {return newNode;}DoublyNode* current = head;while (current->next != NULL) {current = current->next;}current->next = newNode;newNode->prev = current;return head;}

3.4 双向链表的删除操作

删除操作也需要同时更新前驱和后继节点的指针。

删除头节点：示例代码如下：


// 双向链表删除头节点DoublyNode* deleteDoublyHead(DoublyNode* head) {if (head == NULL) {printf("链表为空！\n");return NULL;}if (head->next == NULL) {free(head);return NULL;}DoublyNode* temp = head;head = head->next;head->prev = NULL;free(temp);return head;}

删除尾节点：示例代码如下：


// 双向链表删除尾节点DoublyNode* deleteDoublyTail(DoublyNode* head) {if (head == NULL) {printf("链表为空！\n");return NULL;}if (head->next == NULL) {free(head);return NULL;}DoublyNode* current = head;while (current->next->next != NULL) {current = current->next;}free(current->next);current->next = NULL;return head;}

3.5 双向链表的遍历

双向链表支持正向和反向遍历。正向遍历与单向链表类似，反向遍历则从尾节点开始，通过前驱指针向前访问。示例代码如下：


// 正向遍历双向链表void traverseDoublyListForward(DoublyNode* head) {DoublyNode* current = head;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");}// 反向遍历双向链表void traverseDoublyListBackward(DoublyNode* head) {if (head == NULL) {return;}DoublyNode* current = head;while (current->next != NULL) {current = current->next;}while (current != NULL) {printf("%d ", current->data);current = current->prev;}printf("\n");}

四、循环链表的实现

4.1 单向循环链表

节点定义：与单向链表相同，但表尾节点的指针指向表头节点。

初始化：头指针指向NULL，创建第一个节点后，使其指针指向自身。示例代码如下：


// 初始化单向循环链表Node* initCircularList() {return NULL;}Node* createFirstNode(int data) {Node* newNode = createNode(data);newNode->next = newNode;return newNode;}

插入操作：头插法和尾插法需要在插入后调整指针，使其形成闭环。示例代码如下：

// 单向循环链表头插法Node* insertCircularAtHead(Node* head, int data) {Node* newNode = createNode(data);if (head == NULL) {newNode->next = newNode;return newNode;}Node* current = head;while (current->next != head) {current = current->next;}newNode->next = head;current->next = newNode;return newNode;}// 单向循环链表尾插法Node* insertCircularAtTail(Node* head, int data) {Node* newNode = createNode(data);if (head == NULL) {newNode->next = newNode;return newNode;}Node* current = head;while (current->next != head) {current = current->next;}current->next = newNode;newNode->next = head;return head;}

删除操作：删除节点后需要重新调整指针形成闭环。示例代码如下：


// 单向循环链表删除头节点Node* deleteCircularHead(Node* head) {if (head == NULL) {printf("链表为空！\n");return NULL;}if (head->next == head) {free(head);return NULL;}Node* current = head;while (current->next != head) {current = current->next;}Node* temp = head;head = head->next;current->next = head;free(temp);return head;}