资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

数据结构之单链表详解：从原理到C语言实现

创作时间:

作者:

@小白创作中心

数据结构之单链表详解：从原理到C语言实现

引用

CSDN

https://blog.csdn.net/CHENWENFEIc/article/details/142937861

一、什么是单链表？

单链表（Singly Linked List）是一种线性数据结构，它的特点是每个节点通过指针链接到下一个节点。不同于顺序表（数组），链表的每个元素（节点）并不存储在连续的内存空间中，而是由一个节点指向下一个节点，以形成链式结构。

你可以把单链表想象成一列火车，每节车厢都装载着数据（元素），而每节车厢的尾部都连着下一节车厢，直至最后一节车厢指向空**（
NULL
）**，表示链表的结束。

二、单链表的基本结构

在C语言中，单链表由节点构成。每个节点包含两部分：

数据域：存储当前节点的数据信息。
指针域：存储指向下一个节点的地址。

单链表的节点可以通过结构体来定义，如下所示：

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;            // 数据域
    struct Node* next;   // 指针域，指向下一个节点
};

**
int data
**：存储节点中的数据，可以是任何数据类型。
**
struct Node* next
**：指向下一个节点的指针，若当前节点是链表中的最后一个节点，则
next
的值为
NULL
。

三、单链表的基本操作

创建节点

单链表的节点是通过动态内存分配创建的，在C语言中可以使用**
malloc
来分配内存**。以下是创建单链表节点的代码：

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // 动态分配内存
    newNode->data = data;     // 设置节点的数据
    newNode->next = NULL;     // 初始状态下指向NULL
    return newNode;
}

代码解释：

struct Node* createNode(int data)
：定义了一个函数，用于创建一个新节点。

malloc(sizeof(struct Node))
：动态分配内存，大小为
struct Node
的大小。

newNode->data = data
：为新节点赋值。

newNode->next = NULL
：新节点的
next
初始化为
NULL
，表示它暂时是链表的最后一个节点。

插入节点

在进入插入节点这一内容前我们有一个非常重要的知识点需要理解：

为什么传参需要二级指针？为什么有的函数只要一级指针？

我们一起来仔细品味：

在处理单链表的某些操作时，比如插入或删除节点，尤其是修改链表头节点的操作中，我们通常需要使用二级指针。这是因为C语言中的参数传递是值传递，当我们在函数中传递一个指针时，实际上传递的是该指针的一个拷贝。如果我们想在函数内部修改链表的头节点（即
head
指针指向的地址），我们需要传递指向指针本身的指针，也就是二级指针。

什么时候用一级指针？

对于不涉及修改链表头节点的操作，比如遍历链表或只修改链表中的某个节点的值时，只需要传递链表的头节点（即一级指针）即可，因为我们并不打算修改指针本身，只是通过指针访问链表的内容。

void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

这里我们只需要传递链表的头节点
head
，通过它来遍历链表。由于我们不会修改链表的结构（比如不更改头节点），因此不需要使用二级指针。

什么时候用二级指针？

当我们需要修改链表的结构，特别是修改链表的头节点时，传递二级指针是必须的。例如，插入新节点到链表头部，或者删除链表的头节点。如果我们只传递一个一级指针，函数内部对头节点的修改不会影响到外部的链表结构。

void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);  // 创建新节点
    newNode->next = *head;  // 新节点的next指向当前的头节点
    *head = newNode;        // 头节点更新为新节点
}

在这里，**
head
是二级指针**，即
struct Node** head
。
head
指向链表的头节点，通过修改
head
，我们就能改变链表的头节点，使其指向新插入的节点。这样**在函数外部，链表的头节点也会正确更新。

如果我们只传递一级指针，即
struct Node* head
，在函数内部修改
head
的值并不会影响外部的链表结构，因为函数接收到的是头节点指针的拷贝，修改的只是拷贝的内容，而不是原始指针。

理解了上面的问题我们就能继续单链表的插入操作了：

单链表中有三种常见的插入操作：

头部插入：在链表的最前面插入节点。
尾部插入：在链表的最后面插入节点。
中间插入：在指定位置插入节点。

我们先来看看头插：

头部插入节点

void insertAtHead(struct Node** head, int data) {
    struct Node* newNode = createNode(data);  // 创建新节点
    newNode->next = *head;  // 新节点的next指向当前的头节点
    *head = newNode;        // 头节点更新为新节点
}

void insertAtHead(struct Node** head, int data)
：定义了一个函数，接受链表头节点的指针和要插入的数据。
newNode->next = *head
：将新节点的
next
指向当前的头节点。
*head = newNode
：将链表的头节点更新为新节点。

尾部插入节点

void insertAtTail(struct Node** head, int data) {
    struct Node* newNode = createNode(data);  // 创建新节点
    if (*head == NULL) {
        *head = newNode;  // 如果链表为空，新节点为头节点
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;  // 找到链表的最后一个节点
        }
        temp->next = newNode;  // 最后一个节点的next指向新节点
    }
}

如果链表为空，直接将新节点作为头节点。
否则，遍历链表直到找到最后一个节点，将新节点插入到尾部。

中间插入节点

void insertAtPosition(struct Node** head, int data, int pos) {
    struct Node* newNode = createNode(data);
    if (pos == 1) {
        newNode->next = *head;  // 如果位置是1，则插入头部
        *head = newNode;
    } else {
        struct Node* temp = *head;
        for (int i = 1; i < pos - 1 && temp != NULL; i++) {
            temp = temp->next;  // 找到指定位置的前一个节点
        }
        if (temp != NULL) {
            newNode->next = temp->next;  // 插入新节点
            temp->next = newNode;
        }
    }
}

如果插入位置是1，直接头部插入。
否则，遍历链表找到指定位置，将新节点插入到链表中。

删除节点

单链表中删除节点时，需要找到要删除节点的前一个节点，将它的
next
指向被删除节点的下一个节点。

void deleteNode(struct Node** head, int key) {
    struct Node* temp = *head;
    struct Node* 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);  // 释放要删除的节点
}

首先检查要删除的是否是头节点。
如果不是，遍历链表找到要删除的节点，并调整指针，使链表重新连接。
释放被删除节点的内存。

查找节点

查找某个节点时，只需要遍历链表，找到与目标值匹配的节点即可。

int search(struct Node* head, int key) {
    struct Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return 1;  // 找到节点
        }
        current = current->next;
    }
    return 0;  // 未找到
}

遍历链表，逐个比较节点的数据域，直到找到匹配的节点。
如果找到，返回1；如果未找到，返回0。

遍历链表

遍历链表时，从头节点开始，逐个访问每个节点，直到链表结束（即
next
为
NULL
）。

void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}