链表数据结构：C语言中实现链表的基本操作

# 1. 简介

## 1.1 什么是链表数据结构

链表是一种常用的线性数据结构，它由一系列结点组成，每个结点包含数据元素和指向下一个结点的指针。链表中的结点可以在内存中分散存储，不像数组需要连续的内存空间。链表可以根据需要动态地增加或删除结点，因此在存储空间不确定或频繁插入和删除操作的场景中很有用。

## 1.2 链表与数组的比较

链表和数组都是常见的数据结构，但在某些方面有着不同的特性。与数组相比，链表的优势在于可以动态分配内存并支持高效的插入和删除操作，而数组更适用于随机访问。此外，链表可以灵活地扩展大小，而数组的大小是固定的。因此，根据特定的需求，我们可以选择使用链表或数组。

## 1.3 链表的应用场景

链表的灵活性使得它在许多场景中得到广泛应用。以下是一些常见的应用场景：

- 实现堆栈和队列数据结构
- 处理大量数据的流式传输
- 在图 algorithms 中存储顶点和边
- 实现哈希表的解决冲突链表
- 实现LRU (Least Recently Used)缓存算法

链表的应用不止于此，它在许多其他领域都起着重要作用。

## 链表的基本概念

链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表中的数据元素可以随时动态添加或删除，相比之下，数组在插入和删除操作上有一定的局限性。

### 2.1 单向链表和双向链表

在单向链表中，每个节点包含数据和指向下一个节点的指针；而在双向链表中，每个节点同时包含指向前一个节点和后一个节点的指针。双向链表相比单向链表在某些操作上更为方便，但在内存消耗上相对更大。

### 2.2 结点的定义

链表中的节点是由数据域和指针域组成，数据域用于存储数据，指针域用于指向下一个节点。

### 2.3 头结点与尾结点

在链表中，头结点是第一个节点，用于指向链表的起始位置；尾结点是最后一个节点，用于标志链表的结束。有些链表会使用哨兵节点作为头结点或尾结点，来简化边界条件的处理。

### 3. 链表的创建与初始化

在链表的操作中，首先需要创建并初始化一个链表。链表的创建与初始化包括以下几个步骤：

#### 3.1 动态内存分配

在C语言中，链表的创建通常需要使用动态内存分配函数`malloc`。`malloc`函数用于在运行时从堆中分配内存空间，返回的是指向新分配的内存块的指针。链表的每个结点都需要分配一块内存空间来存储数据和指向下一个结点的指针。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

以上是一个链表结点的定义，其中`data`用于存储结点的数据，`next`用于指向下一个结点。

#### 3.2 头插法和尾插法

创建链表时，可以使用头插法或尾插法，这取决于结点的插入顺序。头插法是将新结点插入到链表的头部，而尾插法是将新结点插入到链表的尾部。

##### 3.2.1 头插法

头插法适用于频繁在链表头部插入结点的场景。下面是使用头插法创建链表的代码示例：

Node* createLinkedListByHeadInsert(int *arr, int len) {
    Node *head = NULL;
    for (int i = 0; i < len; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = head;
        head = newNode;
    }
    return head;
}

以上代码中，`arr`是一个整型数组，`len`是数组的长度。通过遍历数组，创建新结点，并将新结点的`next`指针指向头结点，最后将头结点指向新结点。

##### 3.2.2 尾插法

尾插法适用于频繁在链表尾部插入结点的场景。下面是使用尾插法创建链表的代码示例：

Node* createLinkedListByTailInsert(int *arr, int len) {
    Node *head = NULL;
    Node *tail = NULL;
    for (int i = 0; i < len; i++) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

以上代码中，`arr`是一个整型数组，`len`是数组的长度。通过遍历数组，创建新结点，并将新结点插入到链表尾部。

#### 3.3 初始化链表

创建链表后，需要对链表进行初始化，确保各个指针正确指向。下面是链表的初始化函数示例：

void initLinkedList(Node *head) {
    if (head == NULL) {
        return;
    }
    Node *cur = head;
    while (cur != NULL) {
        cur->next = NULL;
        cur = cur->next;
    }
}

以上代码中，`head`是链表的头指针。通过遍历链表的每个结点，将其`next`指针置为`NULL`，达到链表初始化的目的。

## 4. 链表的插入与删除

链表的插入和删除是链表操作中的重要部分。它们允许我们在链表中添加和删除元素。在本章中，我们将讨论如何在C语言中实现链表的插入和删除操作。

### 4.1 在链表头部插入结点

在链表头部插入一个结点是一种常见的操作。这个操作可以在O(1)的时间复杂度内完成，非常高效。

首先，我们需要创建一个新的结点，并将新结点的next指针指向原链表的头结点。然后，将新结点赋值给头指针，使其成为链表的新的头结点。

以下是在C语言中实现在链表头部插入结点的代码示例：

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

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

int main() {
    Node* head = NULL;
    
    // 插入结点
    insertAt