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

数据结构：链表

news 2025/7/8 0:16:06

链表是一种常见的数据结构，它由一系列节点（Node）组成，每个节点包含两个部分：数据域和指针域。数据域用于存储数据元素的值，而指针域则用于指向链表中的下一个节点。这种结构使得链表能够动态地进行插入和删除操作，具有较高的灵活性。

链表的主要特点包括：

动态分配：链表的大小可以在运行时动态地增长或缩小，不需要预先分配固定大小的空间。
插入和删除效率高：在已知某一节点位置的情况下，链表的插入和删除操作可以在常数时间内完成，无需像数组那样移动大量元素。
元素访问顺序性：链表中的元素是顺序访问的，从头节点开始，依次访问到尾节点。这种顺序性使得链表在处理需要按序处理的数据时非常有用。

链表的类型主要有以下几种：

单向链表：每个节点只有一个指针，指向下一个节点。单向链表只能从头节点开始，顺序访问到尾节点。
双向链表：每个节点有两个指针，一个指向前一个节点，另一个指向后一个节点。双向链表可以从任意节点开始，向前或向后访问其他节点。
循环链表：在单向链表或双向链表的基础上，尾节点的指针指向头节点，形成一个环状结构。循环链表可以从任意节点开始，遍历整个链表。

在实际应用中，链表被广泛用于实现各种数据结构和算法，如栈、队列、哈希表等。同时，由于链表在插入和删除操作上的高效性，它也常被用于需要频繁进行这些操作的场景，如文本编辑器中的撤销/重做功能、操作系统的任务调度等。

然而，链表也有一些缺点，如需要额外的空间来存储指针、不能直接访问特定位置的元素（需要从头节点开始遍历）等。因此，在选择使用链表还是其他数据结构时，需要根据具体的应用场景和需求进行权衡。

1. 单向链表（Singly Linked List）

单向链表中的每个节点包含数据和指向下一个节点的指针。链表的头指针指向第一个节点，最后一个节点的指针指向NULL，表示链表的结束。

示例代码：

#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在链表末尾插入节点
void append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;
}// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d -> ", temp->data);temp = temp->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}

输出：

10 -> 20 -> 30 -> NULL

2. 双向链表（Doubly Linked List）

双向链表中的每个节点包含数据、指向下一个节点的指针和指向前一个节点的指针。这样可以方便地从任意节点向前或向后遍历链表。

示例代码：

#include <stdio.h>
#include <stdlib.h>// 定义双向链表节点结构
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 append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;return;}struct Node* temp = *head;while (temp->next != NULL) {temp = temp->next;}temp->next = newNode;newNode->prev = temp;
}// 打印链表
void printList(struct Node* head) {struct Node* temp = head;while (temp != NULL) {printf("%d <-> ", temp->data);temp = temp->next;}printf("NULL\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}

输出：

10 <-> 20 <-> 30 <-> NULL

3. 循环链表（Circular Linked List）

循环链表可以是单向的也可以是双向的。在循环链表中，最后一个节点的指针指向链表的头节点，形成一个环。

示例代码：

#include <stdio.h>
#include <stdlib.h>// 定义循环链表节点结构
struct Node {int data;struct Node* next;
};// 创建新节点
struct Node* createNode(int data) {struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));newNode->data = data;newNode->next = NULL;return newNode;
}// 在循环链表末尾插入节点
void append(struct Node** head, int data) {struct Node* newNode = createNode(data);if (*head == NULL) {*head = newNode;newNode->next = *head;  // 指向自身形成环return;}struct Node* temp = *head;while (temp->next != *head) {temp = temp->next;}temp->next = newNode;newNode->next = *head;  // 新节点指向头节点
}// 打印循环链表
void printList(struct Node* head) {if (head == NULL) return;struct Node* temp = head;do {printf("%d -> ", temp->data);temp = temp->next;} while (temp != head);printf("(回到起点)\n");
}int main() {struct Node* head = NULL;append(&head, 10);append(&head, 20);append(&head, 30);printList(head);return 0;
}