【链表实现揭秘】：从零开始构建数据结构

# 1. 链表数据结构概述

## 简介

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。与数组不同，链表在物理内存上不需要连续存放，这使得链表在插入和删除操作中具有天然优势。

## 历史与应用

链表的历史可以追溯到计算机科学的早期，它在操作系统、数据库和各种软件应用中扮演着核心角色。例如，在文件系统的链表实现中，每个文件被表示为链表上的一个节点，用于追踪文件系统中的数据块。

## 链表的分类

链表根据指针的方向可以分为单向链表和双向链表。单向链表的节点只有指向下一个节点的指针，而双向链表的节点则包含向前和向后的指针。此外，还有循环链表，它的最后一个节点指向链表的第一个节点，形成一个环。

# 2. 链表的基本概念与操作

## 2.1 链表的定义和特性

### 2.1.1 链表的数据结构定义

链表是一种常见的基础数据结构，它通过一系列节点来存储数据。每个节点由两部分组成：存储数据的数据域和指向下一个节点的指针域。这种结构与数组不同，它不要求数据在内存中连续存放，而是通过指针将一系列分散的节点连接在一起。链表的这种性质使得它在插入和删除操作时，无需移动大量数据，从而可以高效地进行动态数据管理。

#### 链表节点的定义

在编程实现中，一个简单的链表节点可以定义如下（以C语言为例）：

typedef struct Node {
    int data;           // 数据域，存储整型数据
    struct Node* next;  // 指针域，指向下一个节点
} Node;

上面的代码定义了一个名为`Node`的结构体，它包含一个整型的`data`成员和一个指向`Node`类型的指针`next`。`next`指针用于指向下一个节点，最后一个节点的`next`指针通常设置为`NULL`，以标识链表的结束。

#### 链表的类型

根据节点指针域的不同，链表可以分为单向链表、双向链表和循环链表等类型。

- **单向链表**：每个节点只有一个指针域指向下一个节点。
- **双向链表**：每个节点有两个指针域，一个指向前一个节点，一个指向下一个节点。
- **循环链表**：链表的最后一个节点的指针指向链表的第一个节点，形成环状。

### 2.1.2 链表与数组的对比

在数据结构的选择上，链表和数组是两种经常被比较的数据结构。每种结构都有其优势和劣势，选择哪一种往往取决于具体的应用场景。

**数组**：

- **优点**：
- 随机访问：可以通过索引直接访问数组中的任意元素，时间复杂度为O(1)。
- 缓存友好：由于元素连续存放，数组在CPU缓存中容易获得更高的缓存命中率。

- **缺点**：
- 大小固定：数组一旦创建，其大小不可改变。
- 插入和删除低效：移动数组中的元素来插入或删除一个元素通常需要O(n)的时间复杂度。

**链表**：

- **优点**：
- 动态大小：链表可以根据需要动态地添加或删除节点。
- 插入和删除高效：只需要更新指针，不需要移动元素，时间复杂度为O(1)。

- **缺点**：
- 随机访问效率低：需要从头节点开始遍历链表，直到找到指定位置的节点。
- 内存开销大：链表中每个节点都需要额外存储指针信息，内存占用相对较大。
- 缓存不友好：由于节点可能分散在内存中，链表难以利用CPU缓存的优势。

## 2.2 单向链表的实现

### 2.2.1 节点结构的创建与初始化

在上一节中，我们定义了链表节点的基本结构。接下来，我们需要实现链表的基本操作，包括节点的创建、初始化、插入、删除和查找。

#### 节点的创建与初始化

在C语言中，创建一个链表节点需要使用`malloc`函数动态分配内存，并将节点初始化。以下是一个简单的函数实现：

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        exit(1); // 分配内存失败时退出程序
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

这里，`createNode`函数接受一个`int`类型的数据作为参数，并返回一个新创建的节点指针。使用`malloc`函数为新节点分配内存后，将数据域设置为传入的`data`值，并将指针域`next`初始化为`NULL`。

### 2.2.2 插入、删除与查找操作的实现

接下来，我们需要实现单向链表的核心操作：插入、删除和查找节点。

#### 插入操作

链表的插入操作可以分为在链表头部插入、在链表尾部插入和在链表中间任意位置插入三种情况。

void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data);
    newNode->next = *head;
    *head = newNode;
}

void insertAtTail(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

void insertAtPosition(Node** head, int data, int position) {
    Node* newNode = createNode(data);
    if (position == 0) {
        insertAtHead(head, data);
        return;
    }
    Node* temp = *head;
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }
    if (temp == NULL) {
        printf("Position is out of bounds\n");
        return;
    }
    newNode->next = temp->next;
    temp->next = newNode;
}

- `insertAtHead`函数将新节点插入到链表的头部。
- `insertAtTail`函数将新节点插入到链表的尾部。它首先检查链表是否为空，如果是，则将新节点设置为头节点；如果不是，则遍历到链表的末尾，然后插入新节点。
- `insertAtPosition`函数将新节点插入到链表中指定位置。函数首先检查是否是头部插入的特殊情况，然后遍历链表到指定位置，最后执行插入操作。

#### 删除操作

删除操作也需要考虑在链表头部、尾部以及中间位置删除节点的不同情况。

void deleteNode(Node** head, int key) {
    Node* temp = *head, *prev = NULL;
    // 如果头节点就是要删除的节点
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }
    // 查找要删除的节点
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    // 如果没有找到
    if (temp == NULL) return;
    // 删除节点
    prev->next = temp->next;
    free(temp);
}

`deleteNode`函数删除链表中值为`key`的节点。函数首先检查头节点是否是待删除的节点，如果是，则直接删除。否则，函数会在链表中查找值为`key`的节点，一旦找到，则更新前一个节点的`next`指针，使其指向当前节点的下一个节点，从而将当前节点从链表中移除。

#### 查找操作

查找操作相对简单，只需遍历链表直到找到目标值或到达链表末尾。

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key)
            return current;
        current = current->next;
    }
    return NULL;
}

`search`函数返回链表中值为`key`的节点指针，如果找不到则返回`NULL`。

## 2.3 双向链表的实现

### 2.3.1 双向链表节点结构的扩展

双向链表是单向链表的扩展，它允许每个节点有两个指针：一个指向前一个节点，另一个指向后一个节点。这样的结构使得双向链表在某些操作中比单向链表更加高效，比如在双向链表中，可以从任意一个节点开始向前或向后遍历。

#### 双向链