【Java数据结构】详解LinkedList与链表（一）

🔒文章目录：

1.❤️❤️前言~🥳🎉🎉🎉

2.ArrayList的缺陷

3.链表的概念及结构

4.无头单向非循环链表的实现 

4.1成员属性

4.2成员方法

         createList 

display——打印链表 

addFirst——头插

 addLast——尾插

 size——获取单链表长度

addIndex——在任意位置插入 

 contains——判定是否包含某个元素

remove——删除第一次出现关键字为key的结点

 removeAll——删除所有值为key的结点 

clear——清空单链表 

 4.3完整代码及使用

  完整代码 

  完整代码的使用

5.总结

---

 1.❤️❤️前言~🥳🎉🎉🎉

Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。

如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。

当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！

加油，一起CHIN UP！💪💪

🔗个人主页：E绵绵的博客
📚所属专栏：

1. JAVA知识点专栏

        深入探索JAVA的核心概念与技术细节

2.JAVA题目练习

        实战演练，巩固JAVA编程技能

3.c语言知识点专栏

        揭示c语言的底层逻辑与高级特性

4.c语言题目练习

        挑战自我，提升c语言编程能力

📘 持续更新中，敬请期待❤️❤️

借鉴文章：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.总结

所以，我们在本文中详细讲述了链表的概念和结构，并成功模拟了无头非循环单链表的实现。在下篇文章中，我们将带来一些关于单链表的面试题。在此，我们诚挚地邀请各位大佬们为我们点赞、关注，并在评论区留下您宝贵的意见与建议。让我们共同学习，共同进步，为知识的海洋增添更多宝贵的财富！🎉🎉🎉❤️❤️💕💕🥳👏👏👏