[数据结构]---链表

一、定义

链表：是一种常见的线性数据结构，它通过一组节点（Node）来存储数据，每个节点包含两部分：数据域和指针域。

1.1 链表的基本概念

节点（Node）：链表的最小单元，包含数据域（Data）与指针域（Pointer）两部分。

数据域：用于存储数据，可以是任意类型（如整数、字符串、对象灯）。

指针域：用于存储指向下一个节点的地址（或引用）。在某些链表（如双向链表）中，还可能包含指向前一个节点的地址。

头节点（Head）：链表的第一个节点，通常用一个指针（如head）来标识链表的起始位置。

尾节点（Tail）：链表的最后一个节点，其指针域通常指向null，表示链表的结束。

二、类型

链表可以分为以下几种类型：单链表、双向链表、循环链表、双向循环链表等。

2.1 单链表（Singly Linked List）

单链表是链表的一种最基本形式，它由一系列节点组成，每个节点包含两部分：数据域和指针域。单链表的特点是每个节点的指针域只指向下一个节点，形成一个线性的结构。

示例结构：

特点：

只能从头节点开始向后遍历，不能反向遍历。 // 定义单链表的节点结构体 typedef struct Node { int data; // 数据域 struct Node* next; // 指向下一个节点的指针 } Node; 2.2 双向链表（Doubly Linked List）

双向链表（Doubly Linked List）是一种更灵活的链表结构，与单链表相比，它在每个节点中增加了指向前一个节点的指针。

示例结构：

特点：

1、双向遍历：可以从任意节点向前或向后遍历，操作更加灵活。

2、插入和删除操作高效：

插入和删除节点时，只需要修改相邻节点的指针，时间复杂度为O(1)。

由于有前驱指针，插入和删除操作更加直观。

3、存储开销较大：每个节点需要存储两个指针（prev和next），增加了存储空间的开销。

4、实现复杂：操作需要同时处理两个指针，代码实现相对复杂。

// 定义双向链表的节点结构体 typedef struct Node { int data; // 数据域 struct Node* prev; // 指向前一个节点的指针 struct Node* next; // 指向后一个节点的指针 } Node; 2.3 循环链表（Circular Linked Lis）

循环链表是一种特殊的链表结构，其特点是尾节点的指针指向头节点，形成一个环形结构。

示例结构：

特点：

1、环形结构：

尾节点的next指针指向头节点，而不是NULL。

没有明显的“尾节点”，链表形成一个闭环。

2、遍历特性：

从任意节点出发，可以遍历整个链表。

需要特别注意循环条件，避免无限循环。

3、操作效率：

插入和删除操作的时间复杂度为O(1)，但需要特别处理循环特性。

适合需要频繁遍历或操作的场景

// 定义单向循环链表的节点结构体 typedef struct Node { int data; // 数据域 struct Node* next; // 指向下一个节点的指针 } Node; 2.4 循环双向链表

循环双向链表是一种更复杂的链表结构，它结合了双向链表和循环链表的特点。每个节点不仅包含指向下一个节点的指针，还包含指向前一个节点的指针，同时链表的尾节点的next指针指向头节点，头节点的prev指针指向尾节点，形成一个闭环。

示例结构：

特点：

1、双向遍历：可以从任意节点向前或向后遍历。

2、循环结构：尾节点的next指针指向头节点，头节点的prev指针指向尾节点。

3、操作高效：插入和删除操作的时间复杂度为O(1)，且操作更直观。

4、灵活性高：适合需要频繁插入、删除以及双向遍历的场景。

5、实现复杂：需要同时处理两个指针，并且在操作时需要特别注意循环条件。

// 定义循环双向链表的节点结构体 typedef struct Node { int data; // 数据域 struct Node* prev; // 指向前一个节点的指针 struct Node* next; // 指向后一个节点的指针 } Node; 三、存储方式

链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

四、操作

链表的操作主要包括插入、删除、查找、遍历等。

以单链表为例，以下是单链表操作的C语言实现。

4.1 定义单链表的节点结构 #include <stdio.h> #include <stdlib.h> // 定义单链表的节点结构体 typedef struct Node { int data; // 数据域 struct Node* next; // 指向下一个节点的指针 } Nod 4.2 初始化单链表 void initList(Node** head) { *head = NULL; // 初始化头指针为NULL } 4.3 创建新节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); // 动态分配内存 if (newNode == NULL) { printf("内存分配失败!\n"); exit(1); } newNode->data = data; // 初始化数据 newNode->next = NULL; // 初始化指针 return newNode; } 4.4 插入节点

4.4.1 在链表头部插入节点 void insertAtHead(Node** head, int data) { Node* newNode = createNode(data); // 创建新节点 newNode->next = *head; *head = newNode; } 4.4.2 在链表尾部插入节点

在链表尾部插入节点时，需要遍历到链表的最后一个节点，并将新节点连接到尾部。

void insertAtTail(Node** head, int data) { Node* newNode = createNode(data); // 创建新节点 if (*head == NULL) { // 如果链表为空 *head = newNode; // 新节点成为头节点 } else { Node* current = *head; while (current->next != NULL) { // 遍历到链表尾部 current = current->next; } current->next = newNode; // 将新节点连接到尾部 } } 4.4.3 在指定位置插入节点

在指定位置插入节点时，需要找到插入位置的前一个节点，并将新节点插入。

void insertAtPosition(Node** head, int data， int position) { if(position < 0) { printf("无效的位置\n"); return; } Node* newNode = createNode(data); // 创建新节点 if (position == 0) { // 在头部插入 newNode->next = *head; *head = newNode; } else { Node* current = *head; int count = 0; while (current != NULL && count < position - 1) { // 找到插入位置的前一个节点 current = current->next; count++; } if (current == NULL) { printf("位置超出范围!\n"); free(newNode); return; } newNode->next = current->next; current->next = newNode; } } 4.5 删除节点

要想删除C节点，只要将B节点的next指针指向D节点就可以了。

4.5.1 删除头节点 void deleteHead(Node** head) { if (*head == NULL) { printf("链表为空\n"); return; } Node* temp = *head; *head = (*head)->next; free(temp); } 4.5.2 删除尾节点 void deleteTail(Node** head) { if (*head == NULL) { printf("链表为空\n"); return; } if ((*head)->next == NULL) { free(*head); *head = NULL; return; } Node* temp = *head; while (temp->next->next != NULL) { temp = temp->next; } free(temp->next); temp->next = NULL; } 4.5.3 删除指定位置的节点 void deleteAtPosition(Node** head, int position) { if (*head == NULL) { printf("链表为空\n"); return; } if (position < 0) { printf("无效的位置\n"); return; } if (position == 0) { Node* temp = *head; *head = (*head)->next; free(temp); return; } Node* temp = *head; for (int i = 0; i < position - 1 && temp->next != NULL; i++) { temp = temp->next; } if (temp->next == NULL) { printf("位置超出范围\n"); return; } Node* nodeToDelete = temp->next; temp->next = temp->next->next; free(nodeToDelete); } 4.6 查找指定值的节点

查找指定值的节点时，需要遍历链表并返回节点的指针。

Node* searchNode(Node* head, int data) { Node* current = head; while (current != NULL) { // 遍历链表查找目标节点 if (current->data == data) { return current; // 找到节点，返回指针 } current = current->next; } return NULL; // 未找到节点，返回NULL }

查找节点，返回节点位置（位置从0开始），未找到返回-1。

int searchNode(Node* head, int key) { int position = 0; Node* temp = head; while (temp != NULL) { if (temp->data == key) { return position; } temp = temp->next; position++; } return -1; } 4.7 遍历并打印链表 void printList(Node* head) { Node* current = head; while (current != NULL) { // 遍历链表 printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } 五、性能分析

链表与数组的区别：

1、存储方式：

数组：

连续存储：数组的元素在内存中是连续存储的，每个元素的地址可以通过起始地址和偏移量直接计算。

固定大小：数组的大小在声明时通常需要固定，虽然动态数组可以动态扩展，但底层仍然需要重新分配内存并复制数据。

链表：

离散存储：链表的节点可以分散在内存的任意位置，每个节点通过指针连接。

动态大小：链表的大小可以动态变化，插入或删除节点时不需要移动其他元素，只需修改指针。

2、访问效率：

数组：随机访问：数组支持通过索引直接访问任意位置的元素，时间复杂度为O(1)。

链表：顺序访问：链表不支持随机访问，访问某个节点需要从头节点开始逐个遍历，时间复杂度为O(n)。

3、插入和删除操作

数组：插入和删除：在数组中插入或删除元素时，通常需要移动大量元素以保持连续性，时间复杂度为O(n)。例如，在数组头部插入元素时，需要将所有元素向后移动一位。

链表：插入和删除：链表的插入和删除操作只需修改相邻节点的指针，时间复杂度为O(1)（如果已知插入或删除位置的指针）。例如，在链表头部插入或删除节点时，只需修改头指针。

4、内存使用

数组：

内存分配：数组需要预先分配固定大小的内存，即使某些位置未使用，也会占用内存。

内存碎片：数组需要连续内存空间，可能导致内存碎片化问题，尤其是在频繁动态分配和释放时。

链表：

动态分配：链表的节点是动态分配的，每个节点只占用实际需要的内存，内存使用更灵活。

额外开销：链表的每个节点需要额外存储指针（单链表需要一个指针，双向链表需要两个指针），增加了内存开销。

5、扩展性和灵活性

数组：

固定大小：数组的大小在声明时固定，扩展数组需要重新分配内存并复制数据。

适用场景：适合存储大小固定且需要频繁随机访问的数据。

链表：

动态大小：链表的大小可以动态变化，适合存储大小不确定或频繁变化的数据。

适用场景：适合需要频繁插入和删除操作的场景，如实现队列、栈、动态集合等。

特性数组链表存储方式连续存储离散存储访问效率随机访问O(1)顺序访问O(n)插入/删除效率O(n)，需要移动元素O(1)，只需修改指针内存使用预分配，可能浪费内存动态分配，更灵活，但有指针开销扩展性固定大小，扩展需要复制数据动态大小，易于扩展适用场景随机访问频繁，大小固定插入/删除频繁，大小不确定