数据结构 之 链表（Linked List）

数据结构 之 链表（Linked List）

1. 基础概念

1.1 链表的定义

链表是由若干节点组成的线性结构，每个节点包含数据部分和指向下一个节点的指针（或引用）。链表的特点是元素之间通过指针相连，而不是在内存中连续存储。常见的链表类型有单链表、双链表和循环链表等。

1.2 链表的特点

• 动态存储：链表不需要预先定义大小，能根据需要动态增减元素。
• 插入和删除效率高：链表在任意位置插入或删除节点时，不需要移动大量数据，时间复杂度为O(1)。
• 随机访问慢：链表不支持直接访问元素，需要从头节点遍历到目标节点，时间复杂度为O(n)。

1.3 使用场景

链表广泛应用于需要动态存储和频繁插入、删除元素的场景。例如，操作系统中的进程调度、内存管理、浏览器的历史记录和操作队列等。

2. 实现与操作

2.1 核心操作实现

以下是用C语言实现链表的基本操作，如构建、插入、删除、更新等。

#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 insertAtHead(struct Node** head, int data) { struct Node* newNode = createNode(data); newNode->next = *head; *head = newNode; } // 删除链表头部节点 void deleteAtHead(struct Node** head) { if (*head == NULL) { printf("链表为空\n"); return; } struct Node* temp = *head; *head = (*head)->next; free(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; insertAtHead(&head, 10); insertAtHead(&head, 20); insertAtHead(&head, 30); printf("链表内容：\n"); printList(head); deleteAtHead(&head); printf("删除头节点后的链表：\n"); printList(head); return 0; } </stdlib.h></stdio.h>

2.2 代码详解

代码首先定义了一个链表节点结构体Node，包含数据域data和指向下一个节点的指针next。

• createNode: 创建一个新的节点，并返回该节点的指针。
• insertAtHead: 在链表头部插入一个新节点。
• deleteAtHead: 删除链表头部的节点。
• printList: 遍历链表并打印每个节点的数据。

3. 时间与空间复杂度分析

3.1 时间复杂度

链表的不同操作的时间复杂度分析如下：

• 创建节点：O(1)，分配一个新节点并初始化。
• 插入操作：O(1)，在链表头部插入元素。
• 删除操作：O(1)，删除链表头部元素。
• 遍历操作：O(n)，需要遍历整个链表。

3.2 空间复杂度

链表的空间复杂度是O(n)，其中n是链表中节点的数量。每个节点都需要存储数据和指向下一个节点的指针，因此每个节点的空间复杂度是O(1)，总空间复杂度是O(n)。

4. 优缺点与局限性

4.1 优点

• 动态内存管理：链表大小动态变化，不需要预先分配固定的内存空间。
• 插入和删除效率高：在链表的头部或尾部插入、删除节点的时间复杂度为O(1)。

4.2 缺点与局限性

• 随机访问慢：链表不支持通过索引直接访问元素，访问一个元素需要遍历链表。
• 额外空间消耗：链表每个节点需要额外的指针空间。

5. 常见应用场景

5.1 实际应用

链表常用于实现队列和栈结构，或者需要动态内存分配和频繁插入删除操作的场景。以下是一个简单的实现优先队列的示例：

#include <stdio.h> #include <stdlib.h> // 定义链表节点 struct Node { int data; struct Node* next; }; // 插入优先队列节点（按数据大小升序） void insertPriorityQueue(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; if (*head == NULL || (*head)->data >= newNode->data) { newNode->next = *head; *head = newNode; } else { struct Node* temp = *head; while (temp->next != NULL && temp->next->data < newNode->data) { temp = temp->next; } newNode->next = temp->next; temp->next = newNode; } } // 打印优先队列 void printQueue(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } int main() { struct Node* priorityQueue = NULL; insertPriorityQueue(&priorityQueue, 20); insertPriorityQueue(&priorityQueue, 10); insertPriorityQueue(&priorityQueue, 30); printf("优先队列内容：\n"); printQueue(priorityQueue); return 0; } </stdlib.h></stdio.h>

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

        gcc linked_list.c -o linked_list
        

6.2 测试用例

测试结果应如下所示：

        链表内容：
        30 -> 20 -> 10 -> NULL
        删除头节点后的链表：
        20 -> 10 -> NULL
        
        优先队列内容：
        10 -> 20 -> 30 -> NULL