单向链表是什么（单向链表结构图）

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p>

讯享网

什么是链表？

链表（Linked List）是用链式存储结构实现的线性表。链表示意图：

讯享网
链表的组成：+（数据域和引用域合称结点或元素）
- 数据域存放数据元素自身的数据
- 引用域存放相邻结点的地址
链表的特点：
- 链表中元素的联系依靠引用域
- 具有线性结构的特点，链表所使用的逻辑结构是线性结构
- 具有链式存储结构的特点，所使用的物理存储结构是链式存储
链表的分类：
- 单向链表：单链表是一种最简的链表，只有一个引用域next
  特点：通过next可以访问到后继结点，终端结点的引用域指向null
- 双向链表：具有两个引用域prev和next，prev用来保存前驱结点的地址，next用来保存后继结点的地址
  特点：通过next可以访问后继结点，终端结点的next指向null；通过prev可以访问到前驱节点，起始结点的prev指向null
- 循环链表：循环链表本质是一种特殊的单向链表，只是它的终端结点指向了开始结点（也就是next存放了开始结点的地址）
  特点：所有结点都能具有前驱节点和后继结点
链表的使用场景：对查找速度要求不高，但对插入和删除速度要求高时，可以使用链表。常见的比如：

单向链表（简称单链表）有带头结点的单链表，也有不带头链表的单链表。

单链表的基本操作：
- 非空判断：判断链表中是否含有元素
- 求表长度：获取链表中所有元素的个数
- 插入结点：在单链表中添加一个新的结点
- 删除结点：删除单链表中的结点
- 取表元素：更具所给索引，确定该索引所在链表的结点
- 定位元素：根据所给值，确定该元素所在链表的索引号
- 修改元素：根据所给索引，修改对应的结点
- 清空链表：清空链表中所有的元素

2.1 带头节点的单向链表

带头结点就是先固定一个头节点，用来标识链表的初始位置，它的data域不存任何东西，它的next域用来第一个结点的地址，每次遍历链表或定位结点都需要借助一个辅助变量temp来实现。

插入结点示意图：

删除结点示意图：

修改结点示意图：

遍历经验总结：当我们想要进行的操作的结点依赖于前一个结点时，比如插入、删除、修改等操作操作，就必须从head结点开始遍历，否则会出现空指针异常；当我们想要进行的操作不依赖前一个结点时，就无须从head结点开始遍历，比如根据id获取结点，非空判断、获取链表长度、展示链表等操作。

测试类：

讯享网

链表实现类：

2.2 不带头节点的单向链表

略……逻辑思路都差不多，只是将头节点换成一个头指针

不带头节点和带头结点的主要区别：带头结点遍历的时候、不能将头节点进行计数；而不带结点能够直接进行遍历

本质上两者并没有什么太大区别，带头节点的链表没有指针，头结点就相当于头指针，而不带头节点的链表是由头指针的

注意：这里所谓的指针和结点其实都是结点对象，只是指针初始值为null，结点要进行初始化

2.3 练习

反转链表示意图：

合并链表示意图：

测试类：

讯享网

链表实现类：

双向链表相对单向链表就较为简单了，因为每个结点既能往后遍历，又能往前遍历，对于插入、删除、修改都无需像单链表一样依靠前一个结点。

与单链表的主要区别：

遍历不仅可以往前遍历，还可以往后遍历
插入、删除、修改不需要依赖前一个结点（在链尾插入需要依赖尾结点）
添加的时候，需要进行双向绑定！

双向链表插入示意图：
双向链表删除示意图：

测试类：

和单向链表的测试方法相同

示意图：

双向链表实现类：

其实只要理解了单向链表，再来看双向链表就会觉得so easy😄单向链表的方法双向链表都能使用，只是添加和修改的时候，需要多修改下prev的的指向。

讯享网

基本和单向链表类似，也可以分为带头节点，和不带头结点点，这里演示的是不带头结点的单向环形链表，单向环形链表和单向链表唯一的区别：尾结点的next不指向空，而是指向开始节点。

主要思想还是在单链表那一节😄只要掌握单向链表，这些双向链表还有单向循环链表就是弟弟(′д｀ )…彡…彡直接套用第一节的接口，实现所有的方法

测试类：

和2.1一样，换个对象就行了（这个测试类真渣😆）

实现类：

这里主要记录以下按顺序插入结点的思路，怕以后忘记了。其实主要思想还是和单向链表的方法的逻辑是一致的，主要是要考虑循环！思路主要如下：

先将链表添加分为两大类，首结点的添加 和 非首结点的添加，因为首结点的添加需要自动成环

再将非首结点的添加又分为在 添加在首结点之前 和之后，之前需要移动指针，之后不需要移动

示意图：

删除结点：

先将删除分为两大类，删除头结点 和 删除普通结点

删除头结点又可以分为两类，链表只有一个头结点 和 除了头结点还有其它结点

删除普通结点时需要注意链表是单向的，删除操作需要依赖待删除结点的前一个结点

修改结点的逻辑思路和删除类似，不在赘述，示意图：

清空链表：链表的清空有两种方法，一种是直接让，这种清空简单省事，但是是假清空，链表仍然存在内存中！
第二种方法是让每个结点的next指向空，然后将，这种费脑子但是省空间

单向链表是什么（单向链表结构图）

2.1 带头节点的单向链表

测试类：

链表实现类：

2.2 不带头节点的单向链表

2.3 练习

测试类：

链表实现类：

测试类：

双向链表实现类：

测试类：

实现类：

相关推荐