数据结构 --- JAVA版链表

​

​ 链表

活动地址：CSDN21天学习挑战赛

一、链式存储结构

一、由来

因为顺序表在创建的时候必须占用一整块事先分配好大小的存储空间，这样在很多时候都会使存储空间的利用率过低，为此人们为解决该问题提出了可以实现空间动态管理的链式存储结构；

二、概念

• 线性表的链式存储结构称为 — 链表；
• 链式存储结构的地址不是连续的，链式存储结构是通过引用来建立数据之间的联系；（ C / C++ 是通过指针实现，JAVA 是通过调用类实现 ）
• 链式存储结构可以有多个引用来指定关系，而在链表里面只有两个跟自身同级的引用：一个前驱、一个后继；（ 可能存在数据本身就有为类的情况 ）

图 2.1

三、链表的分类

链表的分类主要有两类，单链表和双链表，以及它们的扩展循环单/双链表；

3.1 单链表

单链表是由一组具有两个域的结点组成的，其中一个域用来存储数据，另外一个域存储指向关系；

图 3.1.1

3.1.1 单链表的操作

1. 对链表的操作离不开定位，因为一旦没有了定位将无法确定元素位置；
2. 为此我们就需要一个定位器，且此定位器的位置一直保持在表头；
3. 方法可以通过建立一个不存储元素的头节点也可以建立一个永远保持指向表首的引用；

查询:

• 链表跟顺序表相比最大的缺点就是查询速度了，因为链表的查询只能够通过定位器开始一个个遍历，不能和顺序表一样可以通过元素下标定位；
• 单链表通过表头的定位器一个个向后遍历实现查询元素；

插入:

• 单链表的插入操作首先要将其插入位置找到，然后再将插入元素的指向指至插入位置的下一个元素，而插入位置前一个元素则需要将指向指至所插入的元素；

删除:

• 单链表的删除操作只需要通过遍历找到所要删除的元素的前一个元素，将其前一个元素的指向指至所删除元素的后一个元素；

修改:

• 单链表的修改操作是通过遍历找到需要修改的元素，然后直接修改数据域的数值；

3.2 双链表

双链表跟单链表大致相同，唯一的区别就是多了一个对前一个元素的指向；

图 3.2.1

3.2.1 双链表的操作

1. 双链表的操作相比于单链表更加的灵活，因为双链表多了一个对前驱元素的指向使得双链表既可以向前操作也可以向后操作；
2. 因为有两个指向，对双链表进行操作的时候最好设有两个定位器，一个对表首的定位、一个对表尾的定位；

查询：

• 双链表通过定位器可以由表首向后遍历也可以由表尾向前遍历；

插入：

• 双链表的插入操作首先要将其插入位置找到，然后再将插入元素的前后两个元素进行连接；
• 值得注意的是进行断开引用的过程中要注意先后，避免因为断开而丢失元素；（ 比如在 q 跟 q 的后继之间插入元素，要先将 q 的后继的前驱连接所插入的元素才能断开，否则 q 的后继因为已经被断开而不能找到 ）

删除：

• 双链表的删除是通过遍历找到需要删除的元素，将所需删除的元素的前驱和后继相连接；

修改：

• 双链表的修改操作跟单链表无异，是通过遍历找到需要修改的元素，然后直接修改数据域的数值；

3.3 循环链表

1. 循环链表分为单循环链表和双循环链表；
2. 循环链表跟普通链表的区别就是首尾相连；
3. 循环链表的操作跟普通链表的操作几乎没有区别；（一般建议使用头结点或尾结点，避免遍历时陷入死循环）

图 3.3.1

四、JAVA 实现建立链表

这里建立的是双链表

4.1 结点建立

• 建立一个类表示链表结点，类内部存有一个变量存储数据值，两个引用指向，一个指向前驱一个指向后继；
• 建立两个构造函数一个无参构造函数，一个赋数据初值的构造函数；

图 4.1

4.2 链表初始化

• 建立一个永远处于表头的引用对象、一个永远处于表尾的引用对象；
• 将表头的后继指针指向表尾，将表尾的前驱指针指向表头；

图 4.2

4.3 查询

通过表首和表尾进行循环遍历输出数据；

图 4.3

4.4 插入

插入我写了两个方法，一个左插入一个右插入，我这边讲一下左插入的思路，右插入原理和左插入一致；

1. 在左插入的情况有两种情况，一种是在表首元素左插入，一种是在其它位置左插入；
2. 如果是在表首结点左插入，如果直接插入会使表首定位器无效化，所以我们要将插入结点对表首拷贝数据进行右插入（将所定位结点的后继的前驱指向指至所插入结点，再将所插入结点的后继指向定位结点的后继，将所插入结点的前驱指向定位结点，将定位结点的后继指向所插入结点），将要插入的结点数值赋值给表首元素，即相当于做了左插入；
3. 其它情况就正常插入即可；（将所定位结点的前驱的后继指向插入结点，将插入结点的前驱指向定位结点的前驱，插入结点的后继指向定位结点，定位结点的前驱指向插入结点）

图 4.4

检测：

由下图可见该插入方法有效；

图 4.5

4.5 删除

• 删除元素之前要先判断是不是删除表首和表尾元素两种特殊情况；
• 如果是删除中间的元素那么直接将所删除元素的前驱和后继相连接即可；
• 如果是表首元素，则需要将表首结点的数值拷贝到表首，再将表首结点的后继删除，表尾的原理相同；

图 4.6

检测：

由下图可见该删除方法有效；

图 4.7

4.6 修改

修改就十分的简单了，直接定位到要修改的结点，对其数据域进行修改即可；

图 4.8