链表、双链表的插入和删除

素颜马尾好姑娘i 2024-03-24 08:46 68阅读 0赞

## 一、链表 ##

链表：是一种**物理存储**单元上**非连续、非顺序**的存储结构，它既可以表示线性结构，也可以用于表示非线性结构（二叉索引数） ，数据元素的逻辑顺序是通过链表中的**指针链接**次序实现的。

数据结构中，在**单链表的开始结点之前**附设一个类型相同的结点，称之为头结点。头结点的数据域可以不存储任何信息，头结点的指针域存储指向开始结点的指针（即第一个元素结点的存储位置）。

![845cb9a9f1bb4eebb48d76dc8747ea91.png][]

## 什么是头结点和头指针？ ##

### 头结点作用 ###

1、防止单链表是空的而设的，当链表为空的时候,**带头结点**的头指针就指向头结点![ea14182bfe0b419ea2683373a4bbd3c3.png][]，如果当链表为空的时候,单链表**没有带头结点**,那么它的**头指针就为NULL。**

2、是为了方便单链表的特殊操作，能有效减少代码量，在插入在表头或者删除第一个结点时不用考虑特殊情况，删除或插入用户的第一个节点的值和删除或插入中间的值用一样的代码（**头指针不为NULL，要操作的结点前总有一个结点**)，这样就保持了单链表操作的统一性!

3、单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。

4、总结来说，没有头结点对第一个结点的操作大多和中间结点不太一样，每个操作都要考虑特殊情况，有头结点的话就不必考虑那么多了，还不容易出现代码错误。

### 头指针： ###

1.头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针

2.头指针具有标识作用，单链表可以用头指针的名字来命名。

3.单链表中头指针**指向第一个结点**（不管带不带头节点,头指针始终指向第一个结点，不带头结点的空链表指向NULL）。 。

4.无论链表是否为空，头指针均不为空，头指针是链表的必要元素

![0002fd8e094e4a5d91f98b5cc1ca2015.png][]

单链表的每一个节点中有指向下一个结点的指针，**不能进行回溯**，也就是只能从头开始找，不方便查找。

双链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点。

![6968cc06a940445ab7984dbe27113b52.png][]

![a7606309640f46e980a92c335ab5c13d.png][]

### ![9d017a5cbfb242dfb9373eb22cfff5ce.png][] ###

### ![73247014af3d4f73adeff9392b5084ff.png][] ###

![8dea85afb4ed4656be4f9cf659dbac03.png][]

### 循环链表 ###

![d16c1f91ee5146db92d10cd5d4aaaec3.png][]

#### **PS：PPT图片均来自[王道考研][Link 1]** ####

[845cb9a9f1bb4eebb48d76dc8747ea91.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a4905d16a74b4238ab05f20e811b6709.png
[ea14182bfe0b419ea2683373a4bbd3c3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a2ca5fb48cd14432b6c44a89aa651c3d.png
[0002fd8e094e4a5d91f98b5cc1ca2015.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/d59fd164040244078969a8947edd9506.png
[6968cc06a940445ab7984dbe27113b52.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/9c9989baaedb49a3953dc5723af2baba.png
[a7606309640f46e980a92c335ab5c13d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/f51aa18e9a6f4a9bb8cf68d219783185.png
[9d017a5cbfb242dfb9373eb22cfff5ce.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/75323c145ec4410ca28e8bcb3642608a.png
[73247014af3d4f73adeff9392b5084ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/10f2d8117e7e4e4ca362778df017d46e.png
[8dea85afb4ed4656be4f9cf659dbac03.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2928faa273b94620843b5650123fa8d1.png
[d16c1f91ee5146db92d10cd5d4aaaec3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/3ec73b6c49694a3481bf8ebdc6bd254b.png
[Link 1]: http://home.cskaoyan.com/#/home