1、前言

链表示例图

数据结构大致有两种类型：线性和非线性。线性数据结构是指除了第一个元素和最后一个元素外，中间的每个元素都连接到前一个元素并且元素存在于单个级别的数据结构。

数据结构分类

线性数据结构的一些示例是数组、链表、堆栈和队列。因此，链表是一种线性数据结构，其中元素不连续存储在内存中。

2、什么是链表链表是内存中随机存储的元素的集合。这些元素称为节点(Node)。使用指针来连接和维护这些随机数据点之间的线性顺序。链表的每个节点至少由两部分组成数据域下一个节点的地址（指针）

链表举例

上图显示，在链表中，元素不是连续存储的，但它们似乎是连续存储的。

链表中最重要的是指针。我们需要一个起始指针 （HEAD） 来访问链表。链表中的最后一个节点具有指向 NULL 的指针。

3、链表特点链表的元素可能连续存在，也可能不连续存在。不需要提前申内存大小。每当需要添加更多节点或在列表中执行任何其他操作时，可以动态分配内存。链表不能包含空节点。链表中的节点是两种数据类型的组合——指针和原始数据类型，例如 int 或 float。因此，使用结构体来实现链表。4、链表在数据结构中的应用可以使用链表实现堆栈和队列数据结构。用于图数据结构的实现。邻接列表表示使用链表。编译器设计中的符号表管理使用链表。用于防止哈希中的冲突，java8 HashMap 经典八股文。链表用于 DMA（动态内存分配）。可以使用链表对长整数进行算术运算。稀疏树矩阵的表示也需要链表。5、链表 VS 数组(顺序表)

链表 VS 数组

6、链表类型

数据结构中有三种类型的列表：

1. 单链表

2. 双链表

3. 循环链表

本节使用单链表进行讲解

7、单链表的基本操作

链表数据结构支持以下基本操作：

遍历：这意味着从头到尾访问每个节点。

插入：此操作在列表中的任何给定位置插入元素。

删除：删除操作有助于从链表中删除节点。

显示：此操作用于打印/显示链表的所有数据元素。

搜索：搜索操作有助于通过遍历元素来搜索元素。

8、链表中节点的声明和初始化

节点是一种复合数据类型。因此，使用结构体来创建它。

struct Node{      int data; 		//节点第一部分  数据域 存放我们业务逻辑的数据 比如学生信息等      struct node *Next; 			//节点第二部分 指针域 存放我们节点之间相联系的节点地址};

链表支持动态内存分配。因此，使用函数 malloc、calloc 和 realloc 进行内存分配。

struct Node *Head, *Ptr; 		//声明 头节点 和普通节点 指针变量Ptr = (struct Node *)malloc(sizeof(struct Node *)); 		// 初始化普通节点 指针变量的值

动态内存是在堆中分配的，这就是为什么我们需要像 malloc 这样的函数。在这里，malloc 将返回节点的地址。

9、单链表的遍历

遍历意味着访问链表的每个节点。可以通过以下方式进行遍历。

void display(struct Node *Head){    	struct Node *Ptr;    	Ptr = Head;    	while(Ptr != NULL)    	{      	Print (Ptr→data);    		Ptr = Ptr→Next;			}}

上述伪代码的时间复杂度为 O（n）。

10、单链表的插入

谈论在链表中插入时，需要考虑三种不同的情况：

1. 在列表开头插入

2. 在列表中间插入。

3. 在列表末尾插入

开头插入

在开头插入意味着将按以下方式在列表的前面插入一个节点：

链表开头插入 图示

上图显示有一个包含以下元素的链表：10→20→30。

一旦在开头插入一个新节点，列表将是 50→10→20→30。

伪代码如下：

void insert_at_beginning(int key){    struct Node *temp; // temp是指向要插入的节点的指针    temp = (struct Node*) malloc(sizeof(struct Node));    if(temp != NULL)    {        temp→data = key;   //key是要插入的数据值        temp→next = Head;  //此步骤将使传入节点成为第一个节点。    }}

中间插入

这里需要遍历新节点插入位置之前的所有节点。为此，需要维护一个额外的临时指针。

中间插入图示

s->Next = P->Next;P->Next = s;

末尾插入

要在列表末尾插入节点，首先需要遍历整个列表。

void insert_at_end(int key){    struct Node *temp, *Ptr;    temp = (struct Node*) malloc(sizeof(struct Node));    if(temp != NULL)    {        temp->data = key;        temp->Next = NULL;        if(Head == NULL) //如果列表最初为空，则为true        {            Head = temp;            return;        }        Ptr = Head;        while(Ptr->Next != NULL)            Ptr->Next = temp;    }}

链表插入的时间复杂度：

链表 插入 时间复杂度

11、链表删除

就像插入一样，删除也适用于三种不同的情况：

1. 开头删除

2. 中间删除

3. 末尾删除

开头删除

它涉及删除链表的第一个节点。

开头删除 示意图

假设最初将链表元素设置为 10→20→30→40。

如果在开始时删除一个节点，链表将是：20→30→40。

伪代码如下：

void delete_from_beginning(int key){    struct Node *Ptr = Head;    if(Head == NULL)   //如果链表为空    {        return;    }    Head = Head->Next;  // 将head与列表的第二个节点链接    free(Ptr);}

每当删除一个节点时，都需要使用“free”函数使该节点占用的内存区域空闲。否则，可能会导致内存泄漏问题。

末尾删除

为了删除最后一个节点，需要使倒数第二个节点的地址指向 NULL。为此，将使用一个名为“Prev”的额外指针。

末尾删除 示意图

在删除最后一个节点时，将首先释放最后一个节点，然后将倒数第二个节点的 Next 设置为 NULL。

伪代码如下：

void delete_at_end(int key){    struct Node *Ptr = Head;    struct Node *Prev = NULL;    if(Head == NULL)  //如果链表为空    {        return;    }    if(Head->Next == NULL) //如果列表只有一个元素    {        Head = NULL;        free(Ptr);    }    else    {        while(Ptr->Next != NULL)        {            Prev = Ptr;            Ptr = Ptr->Next;        }        free(Ptr);    }}

中间删除

如有特定节点的地址，理论上总是可以删除它邻接的节点。

考虑一个链表：10→20→30→40。

假设要从中删除 20，那么需要将删除包含 30 的节点，然后将 20 的值重写为 30。

链表中间删除 示意图

伪代码操作如下：

Ptr->data = Ptr->Next->data;Ptr = Ptr->Next;Ptr->Next = Ptr->Next->Next;free(Ptr);

因此，删除 20 后，新列表将为 10→30→40。

删除操作时间复杂度：

链表删除时间复杂度 总结

12、链表反转

要反转链表，我们需要反转指针。

例如，列表为 10→20→30→40，

在反转时，将有 10←20←30←40 和 10 将指向 NULL。

反转列表的递归方法如下：

int reverse_list(struct Node *Head)    {        struct Node *remaining;        if (Head == NULL || Head->Next == NULL)            return Head;        Node* remaining = Reverse_list(Head->Next);        Head->Next->Next = Head;         Head->Next = NULL;         return remaining;    }

链表反转 对应创建链表的头插法原理。

13、链表用途

1、链表的大小由于动态内存分配而受到内存大小的限制。这就是为什么不需要事先声明列表的大小，而是可以在运行时这样做。

2、链表永远不能包含空节点。

3、虽然链表是一种线性数据结构，但没有必要将其连续存储在内存中。这是因为列表是通过地址/指针连接的。这有助于有效利用内存空间。

4、单链表可以存储 int、char、float 等原始数据类型的值。在 OOP 中工作时，该列表还可以存储对象。

14、总结

计算机科学中大量使用的单链列表。它的主要应用在于其他数据结构的实现。因此，很好地理解这种数据结构非常重要。

链表就像是一列小火车，每个车厢都连接着前后的车厢，它们组成了一个长长的队列。在这个队列中，每个车厢都可以装载数据，而且可以很方便地在队列中添加或删除车厢。相比于传统的数组，链表更加灵活，它可以根据需要动态地调整长度。这就像是一场神奇的冒险，链表带你畅游数据的世界 你觉得我的总结怎么样？有没有让你对链表有了更清晰的认识呢？

喜欢我的小伙伴们可以点个关注，一键收藏哦，咱们继续淦