03链表+栈+队列（D1_链表（D1_基础学习））

目录

一、什么是链表

二、基本操作

三、为什么要使用链表

四、为什么能够在常数时间访问数组元素

数组优点

数组缺点

五、动态数组诞生

链表优点

链表缺点

六、链表、数组和动态数组的对比

七、 链表种类

1. 单向链表

2. 双向链表

3. 循环链表

八、链表衍生

......

---

一、什么是链表

链表是一种用于存储数据集合的数据结构。

链表有以下属性：

1. 相邻元素之间通过指针连接
2. 最后一个元素的后继指针值为 NULL
3. 在程序执行过程中，链表的长度可以增加或缩小
4. 链表的空间能够按需分配(直到系统内存耗尽)
5. 没有内存空间的浪费(但是链表中的指针需要一些额外的内存开销)

二、基本操作

增删改查、计数等操作

三、为什么要使用链表

如果使用数组，整个数组所有的元素都存储在操作系统分配的一个内存块中。

通过使用特定元素的索引作为数组下标，可以在常数时间内访问数组元素。

四、为什么能够在常数时间访问数组元素

为了访问一个数组元素，该元素的内存地址需要计算其距离数组基地址的偏移量。

需用一个乘法计算偏移量，再加上基地址，就可获得某个元素的内存地址。

数组优点

简单且易用。

访问元素快(常数时间)

数组缺点

1. 大小固定：数组的大小是静态的(在使用前指定数组的大小)。
2. 分配一个连续空间块：数组初始分配空间时，有时无法分配能存储整个数组的内存空间(当数组规模太大时)。
3. 基于位置的插入或删除操作实现复杂：

比如说：

如果要在数组中的给定位置插人元素，可能需要移动存储在数组中的其他元素，

这样才能腾出指定的位置来放插入的新元素，如果在数组的开始位置插人元素，那么移动操作的开销将更大。

五、动态数组诞生

动态数组是一种可随机存取且可自动调整大小的线性数据结构，能够添加或删除元素。

也称为可增数组、可变长数组、动态表、数组列表，在Java语言，就是ArrayList。

实现动态数组的一个简单方法是，首先初始化固定大小的数组。

一旦数组存储满了，创建一个两倍于原始数组大小的新数组。

同样，若数组中存储的元素个数小于数组大小的一半，则把数组大小减少一半。

链表优点

可以在常数时间内扩展。

当创建数组时必须分配能存储一定数量元素的内存。

如果向数组中添加更多的元素，那么必须创建一个新的数组，然后把原数组中的元素复制到新数组中，这将花费

大量的时间。而我们的链表是动态分配存储空间，采取的是随机分配存储。

链表缺点

链表有许多不足，链表的主要缺点在于访问单个元素的时间开销问题。

数组是随机存取的，即存取数组中任一元素的时间开销为O(1)。而链表在最差情况下访问一个元素的开销为

O(n)。

数组在存取时间方面的另外一个优点是内存的空间局部性。

由于数组被定义为连续的内存块，所以任何数组元素与其邻居是物理相邻的。

这极大得益于现代CPU的缓存模式。

尽管链表的动态分配存储空间有很大的优势，但在存储和检索数据的开销方面却有很大的不足。

有时很难对链表操作。

如果要删除最后一项，倒数第二项必须更改后继指针值为NULL。

这需要从头遍历链表，找到倒数第二个结点的链接，并设置其后继指针为 NULL。

最后，链表中的额外指针引用需要浪费内存。

六、链表、数组和动态数组的对比

七、 链表种类

1. 单向链表

链表通常是指单向链表，它包含多个结点，每个结点有一个指向后继元素的next(下一个)指针。

表中最后一个结点的next指针值为 NULL，表示该链表的结束。

2. 双向链表

双向链表的优点是：对于链表中一个给定的结点，可以从两个方向进行操作。

在单向链表中，只有获得结点的前驱结点的指针，才能删除该结点。

然而，在双向链表中，即使没有一个结点的前驱结点的地址，也能删除该结点，

因为每个结点有都一个指向前驱结点的指针，可以直接后退到前驱结点。

双向链表缺点：

每个结点需再添加一个额外的指针，因此需要更多的空间开销。

结点的插人或删除更加费时，因为它需要更多的指针操作。

3. 循环链表

在单向链表和双向链表中，都采用 NULI 值表示链表的结束，然而，循环链表没有结束标志。

当遍历循环链表时需要特别小心，否则将会无限地遍历链表，因为在循环链表中每个结点都有一个后继结点。

与单向链表不同，循环链表中没有next 指针为 NULI 的结点。

循环链表在某些情况下是非常有用的。

例如，当多个进程需要在相同的时间内使用同一个计算机资源（CPU）时，

必须确保在所有其他进程使用这些资源完前，没有进程访问该资源（轮询算法）

在循环链表中，使用表头结点访问元素（与单向链表和双向链表中的表头结点相似）

上图，指的是单向循环链表，当然还有我们的双向循环链表，工作原理类似。

八、链表衍生

......