【Java第十八期】：#用Java模拟实现一个单向不带头不循环的链表

叮咚~~
您想要的内容已送达！
欢迎来到小猪的博客，这期博客给友友们讲一下如何模拟实现一个链表╰(￣ω￣ｏ)

文章目录

• 前言
• 一，什么是链表？
• 二，模拟实现一个单链不带头非循环的链表
• • 1，构建一个链表框架
  • 2，如何打印这个链表
  • 2，头插法
  • 3，尾插法
  • 4，任意位置插入新节点
  • 5，判断包含key关键字是否在该链表中
  • 6，删除第一次出现关键字key的节点
  • 7，删除所有值为key的节点
  • 8，计算单链表的长度
  • 9，清空单链表
  • 10，全部代码

前言

该链表属于本人学习后的模拟实现，如果哪里有错误的，还请给位大佬指正！！谢谢(≧︶≦))(￣▽￣ )ゞ

下面进入正文内容—》

一，什么是链表？

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表的结构很多，一共有8中，分为3种情况：
（1）单向或者双向的、（2）带头或者不带头的、（3）循环或者不循环的
这里主要模拟实现的是单链不带头非循环的链表，如下图所示：

二，模拟实现一个单链不带头非循环的链表 1，构建一个链表框架

如果要模拟一个链表，是这个链表具备一些功能，首先就要构建一个链表，就以上图为例构建一个链表，如下：
图解：就以上面为例

代码：

（这里可以使用static构建为内部类，为了更易懂一些，我这里使用了外部类）

2，如何打印这个链表

打印链表比较简单，这里就不仔细讲解了，如下代码：

浅解：这里使用cur代替head的原因是head是头的标志，如果想要实现其他功能，使用cur代替head之后依然可以实现。

2，头插法

图解：

代码：

3，尾插法

图解：

代码：

解析：
（1）首先先找出尾巴节点
（2）将需要插入的节点的地址给尾巴节点
（3）需要插入的节点的next置为null
（4）如果head为空，直接把head给需要插入的节点

4，任意位置插入新节点

图解：

代码：

解析：
（1）在插入之前要判断index的位置是否合法
（2）注意头节点和尾巴节点的插入需要分类讨论
（3）在插入的位置需要知道该位置的前一个节点
（4）假设第一个节点的下标为0，对该位置进行表下标

5，判断包含key关键字是否在该链表中

遍历链表判断即可
代码：

6，删除第一次出现关键字key的节点

图解：

代码：

解析：
（1）需要注意链表是否为空
（2）注意判断头节点的val是否为key
（3）需要知道该节点的后一个节点地址

7，删除所有值为key的节点

图解：

代码：

解析：
（1）需要判断head是否为null
（2）需要知道cur的前一个节点prev
（3）如果cur.valkey，prev.next=cur.next,cur=cur.next(cur永远在prev前面)，如果不等于，则可以直接等，cur再走到下一个节点
（4）需要注意head.valkey的情况

8，计算单链表的长度

代码：

遍历计算即可

9，清空单链表

图解:

代码：

解析：
（1）需要知道cur.next的下一位，再对cur置为null，这样可以连续删除
（2）全部置为null之后，head依然标志着第一个节点，需要置为null

10，全部代码

以上就是模拟实现一个单向不带头不循环的单链表的全部内容，如果那里写错了，请求大佬们帮忙指出o(▽)q

好了，本期博客到此结束，很高兴能向友友们分享！！如果对你有用的话就给小博主一个小小的三连吧，小猪会很高兴的，嘻嘻！
路过的小朋友要记得关注小猪哦！不要错过小猪哦！
下期再见啦！