聊城医院网站建设,做网站后台搭建都用什么,百度aipage智能建站,wordpress加广告#x1f512;文章目录#xff1a;
1.❤️❤️前言~#x1f973;#x1f389;#x1f389;#x1f389;
2.ArrayList的缺陷
3.链表的概念及结构
4.无头单向非循环链表的实现
4.1成员属性
4.2成员方法 createList
display——打印链表
addFirst——头插 addLast…文章目录
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.nextlistNode2;listNode2.nextlistNode3;listNode3.nextlistNode4;listNode4.nextlistNode5;headlistNode1;} 该方法创建了一个内部节点为5个的无头单向非循环链表。注意结尾head要指向ListNode1否则该链表之后会自动被释放掉 display——打印链表 注意LinkedList 中不存在该方法为了方便看测试结果 public void display(){ListNode curhead;while(cur!null){System.out.print(cur.value );curcur.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.nexthead;headlistNode;
} 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 curhead;if(headnull){headlistNode;return;
}while(cur.next!null){curcur.next;}cur.nextlistNode;
} size——获取单链表长度 直接遍历链表即可 public int size(){int count0;ListNode curhead;while(cur!null){curcur.next;count;}return count;} addIndex——在任意位置插入 官方规定第一个数据的位置是0和数组的位置下标规则一致 所以我们首先要判断 index 的合法性index0 || 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(headnull){ListNode listNode new ListNode(a);headlistNode;return;}if(index0||indexsize()){System.out.println(位置不合法);//这里就不搞抛出异常了我们简单点return;}if(index0){addFirst(a);return;}if(indexsize()){addLast(a);return;}ListNode listNode new ListNode(a);ListNode curhead;for (int i 0; i index-1 ; i) {curcur.next;}listNode.nextcur.next;cur.nextlistNode;
}contains——判定是否包含某个元素 比较简单遍历这个数组即可 public void contain(int key){ListNode curhead;while(cur!null){if(cur.valuekey){System.out.println(true);return;}curcur.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 curhead;if(headnull) {System.out.println(为空链表不能进行删除操作);return;}if(cur.valuekey) {headhead.next;return;}while(cur.next!null){if(cur.next.valuekey){cur.nextcur.next.next;return;}curcur.next;}System.out.println(不存在该数);
}removeAll——删除所有值为key的结点 这里我们将cur从head处开始检验: 当cur的下一个节点中的值等于key时: cur.nextcur.next.next否则curcur.next。 最后检测完毕后还要看一下head处的值是否等于key如果等于则将headhead.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.nextcur.next.next;}else {cur cur.next;}}if(head.valuekey){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.nextlistNode2;listNode2.nextlistNode3;listNode3.nextlistNode4;listNode4.nextlistNode5;headlistNode1;}public void display(){ListNode curhead;while(cur!null){System.out.print(cur.value );curcur.next;}System.out.println();}public int size(){int count0;ListNode curhead;while(cur!null){curcur.next;count;}return count;}
public void contain(int key){ListNode curhead;while(cur!null){if(cur.valuekey){System.out.println(true);return;}curcur.next;}System.out.println(false);
}public void addFirst(int a){ListNode listNode new ListNode(a);listNode.nexthead;headlistNode;
}
public void addLast(int a){ListNode listNode new ListNode(a);ListNode curhead;if(headnull){headlistNode;return;
}while(cur.next!null){curcur.next;}cur.nextlistNode;
}public void addIndex(int index,int a){if(headnull){ListNode listNode new ListNode(a);headlistNode;return;}if(index0||indexsize()){System.out.println(位置不合法);//这里就不搞抛出异常了我们简单点return;}if(index0){addFirst(a);return;}if(indexsize()){addLast(a);return;}ListNode listNode new ListNode(a);ListNode curhead;for (int i 0; i index-1 ; i) {curcur.next;}listNode.nextcur.next;cur.nextlistNode;
}public void remove(int key){ListNode curhead;if(headnull) {System.out.println(为空链表不能进行删除操作);return;}if(cur.valuekey) {headhead.next;return;}while(cur.next!null){if(cur.next.valuekey){cur.nextcur.next.next;return;}curcur.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.nextcur.next.next;}else {cur cur.next;}}if(head.valuekey){head head.next;}}public void clear(){headnull;}} 完整代码的使用
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.总结 所以我们在本文中详细讲述了链表的概念和结构并成功模拟了无头非循环单链表的实现。在下篇文章中我们将带来一些关于单链表的面试题。在此我们诚挚地邀请各位大佬们为我们点赞、关注并在评论区留下您宝贵的意见与建议。让我们共同学习共同进步为知识的海洋增添更多宝贵的财富❤️❤️
