1. 简单介绍
链表, 即线性表的链式存储结构, 链表使用一组任意的存储单元来存储数据元素. 如果某两个数据元素在逻辑位置上相邻, 那么他们在物理位置上不一定相邻. 如图:
但是这样看着太乱了, 为了看着舒服, 表示方便, 我们把这张图改成:
2. 单向链表的结构和特点
在上图中, 我们可以看出一个链表包含了存储的数据元素 (方框中的值) 以及这些数据元素之间逻辑关系(箭头, 下一个数据元素的位置). 为了表示数据元素及逻辑关系, 我们需要一个能存储它们的 "载体", 这个载体就是结点(node). 它长这样:
一个结点有两个部分: data 是存储数据的数据域, next 是存储它的下一个数据元素 (在逻辑上) 的位置信息的指针域.
有了这两个部分, 一个具体的单向链表如下:
介绍到这里, 可以很容易地总结出单向链表的特点:
链表由若干结点组成
每个结点由数据域和指针域组成, 数据域存储数据, 指针域存储下一个结点的位置
单向链表是单向的, 数据存取必须从第一个结点开始
链表的最后一个结点没有后继结点, 所以其指针域置为 Null, 表示链表结束
2.1. 头结点与头指针
头结点: 即单链表的第 1 个存数据的结点之前的那个结点, 该结点的数据域可以不存储任何信息, 也可以存储如链表长度等附加信息, 该结点的指针域指向第 1 个存数据的结点.
下面是一个带头结点的链表:
head.next 是第 1 个存数据的结点
下面是一个不带头结点的链表:
head 是第 1 个存数据的结点
头指针(head): 不是一个单独的结点, 而是对第 1 个结点的引用. 它通过存储一个指向第 1 个结点的指针来保存整个链表
注意: 第 1 个结点不一定是第 1 个存数据的结点
在带头结点的单链表中, 头指针指向第 1 个结点(头结点)
在不带头结点的单链表中, 头指针指向第 1 个结点(第 1 个存数据的结点)
3. 单链表的操作
在介绍下面的操作时, 会分两种: 带头结点的链表和不带头结点的链表.
- /**
- * 结点类
- * @author Xing Xiaoguan
- */
- public class Node {
- int data;
- Node next;
- public Node() {
- }
- public Node(int data) {
- this.data = data;
- }
- }
3.1. 增加结点
3.1.1. 带头结点的单链表
头插法: 新增加的结点放在头结点后面. 头插法的结点顺序和插入顺序相反. 下图是头插法的过程
尾插法: 新增加的结点放在链表的最后面. 下图是尾插法的过程:
中间插法: 新增加的结点插在链表中间. 下图是中间插法的过程:
由于是单向链表, 所以我们必须先找到 prevNode 结点, 才能进行插入操作.
nextNode 不是必须的, 可以使用 prevNode.next 代替. 如果这样代替了, 插入操作的顺序不能变, 否则 prevNode 结点后的所有结点都会丢失.
3.1.2. 不带头节点的单链表
头插法: 新增加的结点被头指针引用. 下图记录了整个过程:
尾插法: 新增加的结点放在链表的最后面. 下图描述了过程:
中间插法: 不带头节点和带头结点的一样.
3.1.3. 二者比较
比较上面的动图可以看出:
不带头结点的链表在进行头插和尾插时需要考虑空链表的情况, 即插入第 1 个结点和插入其他结点的操作不同.
带头结点的链表在进行头插和尾插时不需要考虑空链表的情况, 即插入第 1 个结点和插入其他结点的操作相同.
显然带头结点的链表在进行插入操作时更方便.
3.2. 遍历链表
带头结点和不带头节点的链表在遍历时要注意遍历的起点和结束: 第一个存数据的结点~ 最后一个存数据的结点.
带头结点的链表遍历从 head.next 结点开始, 不带头结点的链表遍历从 head 开始.
- // 带头结点的遍历
- for (Node node = head.next; node != null; node = node.next)
- System.out.print(node.data + " ");
- // 不带头结点的遍历
- for (Node node = head; node != null; node = node.next)
- System.out.print(node.data + " ");
3.3. 查询结点
查询其实就是对遍历的应用, 不管是根据下标 index 查询还是根据数据 data 查询, 其实都是在遍历链表.
3.4. 删除结点
3.4.1. 带头结点的单链表
删除第一个存数据的结点:
删除最后一个结点:
删除中间结点:
3.4.2. 不带头结点的单链表
删除第一个存数据的结点:
删除中间结点和删除最后一个结点的操作与带头结点的操作相同.
3.4.3. 二者比较
删除第 1 个存数据的结点的操作不同, 删除中间结点和尾结点的操作相同.
3.5. 更新结点
更新结点是对查询的应用, 查询到要更新的结点然后更新即可.
4. 代码
完整代码获取请移步码云
https://gitee.com/xingrenguanxue/code-in-blogs/tree/master/src / 链表基础总结 / linkedlist
如有错误, 还请指正
来源: https://www.cnblogs.com/xingrenguanxue/p/13245952.html