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



• 什么是链表？

  链表（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 练习

• 反转链表示意图：

• 合并链表示意图：

测试类：

链表实现类：

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

与单链表的主要区别：

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

• 双向链表插入示意图：

  

  

• 双向链表删除示意图：

  

  

测试类：

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

示意图：

双向链表实现类：

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

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

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

测试类：

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

实现类：

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

1. 先将链表添加分为两大类，首结点的添加 和 非首结点的添加，因为首结点的添加需要自动成环
2. 再将非首结点的添加又分为在 添加在首结点之前 和 之后，之前需要移动指针，之后不需要移动

示意图：

删除结点：

1. 先将删除分为两大类，删除头结点 和 删除普通结点
2. 删除头结点又可以分为两类，链表只有一个头结点 和 除了头结点还有其它结点
3. 删除普通结点时需要注意链表是单向的，删除操作需要依赖待删除结点的前一个结点

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

• 清空链表：链表的清空有两种方法，一种是直接让，这种清空简单省事，但是是假清空，链表仍然存在内存中！

  第二种方法是让每个结点的next指向空，然后将，这种费脑子但是省空间

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/39963.html