【Java数据结构】详解LinkedList与链表（一）
1.❤️❤️前言~🥳🎉🎉🎉
Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪
借鉴文章：Java【链表】详细图解/ 模拟实现+【LinkedList】常用方法介绍_java linkedlist方法-CSDN博客
2.ArrayList的缺陷
上篇文章已经熟悉了ArrayList的使用，并且进行了简单模拟实现。通过源码知道，ArrayList底层使用数组来存储元素 但由于其底层是一段连续空间，当在ArrayList任意位置插入或者删除元素时，就需要将后序元素整体往前或者往后 搬移，时间复杂度为O(n)，效率比较低，因此ArrayList不适合做任意位置插入和删除比较多的场景。 所以：java 集合中又引入了LinkedList，即链表结构。
3.链表的概念及结构
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
注意：
1.从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
2.其结点一般都是从堆上申请出来的
3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续
🎯🎯实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：
1. 单向或者双向
2.带头或者不带头
3. 循环或者非循环
虽然有这么多的链表的结构，但是我们重点掌握两种:
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如 哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2.无头双向非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向非循环链表。
4.无头单向非循环链表的实现
4.1成员属性
要模拟实现链表，也得自己实现一个类，首先要考虑这个类中的成员属性 已经说过，链表是由多个结点 “链接” 而成的，那么需要定义一个 静态内部类 Node：其中有两个域： 📌值域 value ：来记录这个结点的值 📌指针域 next：来记录下一个结点的地址 📌并且它还需要一个构造方法：在创建ListNode内部类的同时分配好value的值。 📌模拟的链表中还需要一个 成员变量：head 来记录当前链表的头结点。
public class SingleLinkedList {
static class ListNode{
public int value;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}
public ListNode head;
4.2成员方法
createList
该方法是我们自己为了方便独创的，实际链表方法中并不存在该方法。
public void createList(){
ListNode listNode1 = new ListNode(45);
ListNode listNode2 = new ListNode(46);
ListNode listNode3 = new ListNode(50);
ListNode listNode4 = new ListNode(56);
ListNode listNode5 = new ListNode(67);
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
listNode4.next=listNode5;
head=listNode1;
}该方法创建了一个内部节点为5个的无头单向非循环链表。（注意结尾head要指向ListNode1，否则该链表之后会自动被释放掉）
display——打印链表
注意：LinkedList 中不存在该方法，为了方便看测试结果
public void display(){
ListNode cur=head;
while(cur!=null){
System.out.print(cur.value+" ");
cur=cur.next;
}
System.out.println();
}addFirst——头插
❗️❗️和顺序表不同，链表是由一个个结点组成的，而顺序表可以理解为一个数组 顺序表插入之前必须考虑数组是否以及满了，而链表只需要关心各个结点的next即可。
因为我们还有一个成员属性：head，是用来记录头结点的 所以链表的头插操作就是： 1️⃣new 一个结点 node，类型是 Node 2️⃣链接：把头结点的地址（ head 的值）赋给 node 的指针域 next 3️⃣head 记录新的头结点
public void addFirst(int a){
ListNode listNode = new ListNode(a);
listNode.next=head;
head=listNode;
}addLast——尾插
尾插步骤： 1️⃣new 一个 node，类型是 Node 2️⃣找到尾结点 3️⃣链接：把 node 的值（也就是地址）赋给尾结点的指针域 next
🚗🚗🚗 如何找到尾结点呢❓ 需要 从头结点开始，遍历链表，找到一个结点的指针域 next 域为 null，它就是尾结点✅
head 是用来标记头结点的，所以 head 不能随意更改 我们需要再定义一个 Node 类型的 cur，让 cur 遍历链表
当 cur 找到尾结点后，需要让此时的尾结点和新结点 node 连接上 即如下图：
并且我们还需要注意一个特殊情况：
cur 这个变量中存放的值 要更改为下一个结点的地址：cur = cur.next；但当cur == null 时，这里就会发生空指针异常❌，那么在实例中是否会出现这种情况？
如果 head 一开始就是 null ，也就是链表为空时，cur 就会被 head 赋值成 null，就会发生空指针异常。所以当链表为空时，就不需要遍历链表找尾结点，直接把 node 的值赋给 head 即可。
public void addLast(int a){
ListNode listNode = new ListNode(a);
ListNode cur=head;
if(head==null){
head=listNode;
return;
}
while(cur.next!=null){
cur=cur.next;
}
cur.next=listNode;
}size——获取单链表长度
直接遍历链表即可
public int size(){
int count=0;
ListNode cur=head;
while(cur!=null){
cur=cur.next;
count++;
}
return count;
}addIndex——在任意位置插入
官方规定第一个数据的位置是0，和数组的位置（下标）规则一致
所以我们首先要判断 index 的合法性：index<0 || index >链表长度是不合法❌的
index 合法的情况下，如何在index位置插入删除呢❓ 📌index == 0就是头插 📌index = 链表长度就是尾插 ❗️主要是链表中间位置的插入和删除
要想在两个结点中间插入新结点，首先要找到这两个结点的地址 找到 index -1 结点的位置也就相当于找到了 index 结点的位置
找到其位置很简单，cur 遍历链表 index-1 次即可
具体插入步骤：
1️⃣node.next = prevIndex.next； 2️⃣prevIndex.next = node；
这两行不能交换位置❗️❗️❗️ 如果先让 prevIndex.next = node；那么就会丢失 index 位置的那个结点↪️，此时 node.next = prevIndex.next 就相当于 node.next = node；代码会发生错误❌
注意还有一个特殊点当链表中无任何节点，为null时，无论index为何值，都会直接添加一个节点。
public void addIndex(int index,int a){
if(head==null){
ListNode listNode = new ListNode(a);
head=listNode;
return;
}
if(index<0||index>size()){
System.out.println("位置不合法");
//这里就不搞抛出异常了，我们简单点
return;
}
if(index==0){
addFirst(a);
return;
}
if(index==size()){
addLast(a);
return;
}
ListNode listNode = new ListNode(a);
ListNode cur=head;
for (int i = 0; i <index-1 ; i++) {
cur=cur.next;
}
listNode.next=cur.next;
cur.next=listNode;
}contains——判定是否包含某个元素
比较简单，遍历这个数组即可
public void contain(int key){
ListNode cur=head;
while(cur!=null){
if(cur.value==key){
System.out.println(true);
return;
}
cur=cur.next;
}
System.out.println(false);
}因为这里我们存放的是 int 类型的变量，但 LinkedList 当中是存放引用数据类型的 ⚠️⚠️⚠️当表中是引用类型时，就不可以用“等号”比较，应该用 equals 方法
remove——删除第一次出现关键字为key的结点
1️⃣如果链表为空就不能再删了 2️⃣如果头结点就是要删除的 key 结点，直接 head 存放下一个结点的地址 3️⃣如果链表其他结点是要删除的 key 结点，要先找到 key 结点的前一个结点
当 key 结点的前一个结点的 next 不再存放 key 结点地址时，key 结点此后不会再被使用，会被系统自动回收🗑️
所以完整代码如下：
public void remove(int key){
ListNode cur=head;
if(head==null) {
System.out.println("为空链表，不能进行删除操作");
return;
}
if(cur.value==key) {
head=head.next;
return;
}
while(cur.next!=null){
if(cur.next.value==key){
cur.next=cur.next.next;
return;
}
cur=cur.next;
}
System.out.println("不存在该数");
}removeAll——删除所有值为key的结点
这里我们将cur从head处开始检验:
当cur的下一个节点中的值等于key时: cur.next=cur.next.next，否则cur=cur.next。
最后检测完毕后还要看一下head处的值是否等于key，如果等于则将head=head.next。
完整代码如下：
public void removeAll(int key){
if(this.head == null) {
System.out.println("为空链表，不能进行删除操作");
return;
}
ListNode cur = head;
while(cur.next != null){
if(cur.next.value == key){
cur.next=cur.next.next;
}
else {
cur = cur.next;
}}
if(head.value==key){
head = head.next;
}
}clear——清空单链表
head 这个变量一直存放着链表的头结点位置，把head置空，就找不到此链表，那么链表中的所有结点都会被系统自动回收🗑️
public void clear() {
head = null;
}4.3完整代码及使用
完整代码
public class SingleLinkedList {
static class ListNode{
public int value;
public ListNode next;
public ListNode(int value) {
this.value = value;
}
}
public ListNode head;
public void createList(){
ListNode listNode1 = new ListNode(45);
ListNode listNode2 = new ListNode(46);
ListNode listNode3 = new ListNode(50);
ListNode listNode4 = new ListNode(56);
ListNode listNode5 = new ListNode(67);
listNode1.next=listNode2;
listNode2.next=listNode3;
listNode3.next=listNode4;
listNode4.next=listNode5;
head=listNode1;
}
public void display(){
ListNode cur=head;
while(cur!=null){
System.out.print(cur.value+" ");
cur=cur.next;
}
System.out.println();
}
public int size(){
int count=0;
ListNode cur=head;
while(cur!=null){
cur=cur.next;
count++;
}
return count;
}
public void contain(int key){
ListNode cur=head;
while(cur!=null){
if(cur.value==key){
System.out.println(true);
return;
}
cur=cur.next;
}
System.out.println(false);
}
public void addFirst(int a){
ListNode listNode = new ListNode(a);
listNode.next=head;
head=listNode;
}
public void addLast(int a){
ListNode listNode = new ListNode(a);
ListNode cur=head;
if(head==null){
head=listNode;
return;
}
while(cur.next!=null){
cur=cur.next;
}
cur.next=listNode;
}
public void addIndex(int index,int a){
if(head==null){
ListNode listNode = new ListNode(a);
head=listNode;
return;
}
if(index<0||index>size()){
System.out.println("位置不合法");
//这里就不搞抛出异常了，我们简单点
return;
}
if(index==0){
addFirst(a);
return;
}
if(index==size()){
addLast(a);
return;
}
ListNode listNode = new ListNode(a);
ListNode cur=head;
for (int i = 0; i <index-1 ; i++) {
cur=cur.next;
}
listNode.next=cur.next;
cur.next=listNode;
}
public void remove(int key){
ListNode cur=head;
if(head==null) {
System.out.println("为空链表，不能进行删除操作");
return;
}
if(cur.value==key) {
head=head.next;
return;
}
while(cur.next!=null){
if(cur.next.value==key){
cur.next=cur.next.next;
return;
}
cur=cur.next;
}
System.out.println("不存在该数");
}
public void removeAll(int key){
if(this.head == null) {
System.out.println("为空链表，不能进行删除操作");
return;
}
ListNode cur = head;
while(cur.next != null){
if(cur.next.value == key){
cur.next=cur.next.next;
}
else {
cur = cur.next;
}}
if(head.value==key){
head = head.next;
}
}
public void clear(){
head=null;
}
}完整代码的使用
public class Test {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
singleLinkedList.createList();
singleLinkedList.display();
System.out.println(singleLinkedList.size());
singleLinkedList.contain(45);
singleLinkedList.addFirst(12);
singleLinkedList.addLast(67);
singleLinkedList.addIndex(3, 22);
singleLinkedList.display();
singleLinkedList.remove(22);
singleLinkedList.remove(12);
singleLinkedList.display();
singleLinkedList.removeAll(67);
singleLinkedList.display();
System.out.println("=======================");
singleLinkedList.clear();//清空该链表
singleLinkedList.display();
System.out.println("已清空该链表");
System.out.println("=======================");
}}
5.总结
所以，我们在本文中详细讲述了链表的概念和结构，并成功模拟了无头非循环单链表的实现。在下篇文章中，我们将带来一些关于单链表的面试题。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏
腾讯云开发者
