【目标】1.手写MyLinkedList体会LinkedList的底层逻辑2.掌握LinkedList中的一些方法等3.章节测试【引言】关于数据结构我们按照逻辑关系进行划分可以分为以下部分所谓数据结构就是对数据的整合与存储没有数据结构程序就没办法高效地处理复杂数据。而java相较于c的不同是其内置了部分经典、常用的数据结构我们在开发的过程中不能只会用内置数据结构的方法等还要明白底层是怎么实现的。因此我们本节的学习顺序就是从自己实现链表——MyLinkedList{MysinglyLinkdeList单向链表的实现 和 MyDoublyLinkedList双向链表的实现}在此之后认识并掌握内置链表——LinkedList双向链表的实现。提醒本章我们用基本数据类型进行演示如果要顺序表中存储的元素是引用类型还需要具体的根据需求进行操作1.ArrayList的弊端1. ArrayList底层使用连续的空间任意位置插入或删除元素时需要将该位置后序元素整体往前或者往后搬移故时间复杂度为O(N)——进行增删时时间复杂度大2. 增容需要申请新空间拷贝数据释放旧空间会有不小的消耗。——时间消耗 和 空间消耗。3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继 续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。——空间浪费为了解决上述问题我们引入了链表。2.MyLinkedList2.1 链表的类型链表的修饰是这样的 单向/双向、带头/不带头、循环/非循环我们先来解释一下分别都是什么含义2.1.1 单向/双向链表的方向分为单向和双向其中具体的示例图如下单向双向2.1.2 带头/不带头所谓头指的就是头节点。先提醒第一个数据元素所在的节点叫做首元节点首元节点是会发生变化的头节点就是数据域不存储数据元素、指针域指向首元节点的节点这个头节点是链表的一部分对于整个链表的 任何操作 都会操作到头结点是固定不变的不像首元结点可以进行变化。我们再说头指针头指针就是这个head是一个引用恒指向链表的第一个节点有头时指向头结点无头时指向首元节点不带头带头在这里提醒一句有些初学者在学到链表的时候对于这个头指针会有模糊的认识似懂非懂我们这里就进行说明白。2.1.3 循环/非循环所谓循环就是链表的尾节点指向头节点。非循环循环2.1.4 总结与介绍所以说总共有八种链表形式本章节我们主要进行实现常用的两种——单向不带头非循环链表和双向不带头非循环链表2.2 MySinglyLinkedLIst单向不带头非循环链表2.2.1 基本结构单向链表是通过一组物理地址不连续的存储单元节点来存储数据元素的线性结构。每个节点由数据域存储元素值和指针域存储下一个节点的地址组成节点之间的逻辑顺序逻辑上是连续的通过指针链接实现。整个链表通过头指针指向第一个节点来标识最后一个节点的指针指向NULL空表示链表的结束。2.2.2单向链表的增Create、删Delete、查Read、改Update——CRUD1.打印链表Override public void display() { ListNode cur this.head; while(cur ! null) { System.out.print(cur.val ); cur cur.next; } } public static void main(String[] args) { //我们进行打印 System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }2.增加/插入节点2.1 头插法//头插法 Override public void addFirst(int data) { ListNode node new ListNode(data); node.next this.head; this.head node; } public static void main(String[] args) { //1.头插 System.out.print(请输入你要添加的元素头插); int data1 scanner.nextInt(); mySinglyLinkedList.addFirst(data1); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }2.2 尾插法//尾插法 Override public void addLast(int data) { ListNode node new ListNode(data); if (this.head null) { this.head node; return; } //这里我们需要先进行遍历 ListNode cur this.head; while(cur.next ! null) { cur cur.next; } //说明这个时候走到了最后一个元素位置 cur.next node; } public static void main(String[] args) { //2.尾插 System.out.print(请输入你要添加的元素尾插); int data2 scanner.nextInt(); mySinglyLinkedList.addLast(data2); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }2.3 指定位置插入public class SizeException extends RuntimeException { public SizeException(String message) { super(message); } } //得到单链表的长度 Override public int size() { int count 0; ListNode cur this.head; while(cur ! null) { count; cur cur.next; } return count; } //指定位置插入 Override public void addIndex(int index,int data) { //由于不是数组我们这里规定第一个节点就是0号位置 int len size(); //表示指定位置有错那么我们就报错 if(index 0 || index len) { throw new SizeException(你指定位置有误); } ListNode node new ListNode(data); if (index 0) { node.next this.head; this.head node; return; } //遍历到指定位置的前一个节点 ListNode cur this.head; for (int i 0; i index - 1; i) { cur cur.next; } node.next cur.next; cur.next node; } public static void main(String[] args) { //3.任意位置插入 System.out.print(请输入你要添加的元素); int data3 scanner.nextInt(); System.out.print(请输入你要添加的元素的位置); int index scanner.nextInt(); mySinglyLinkedList.addIndex(index,data3); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }在这里有一个小的知识点就是关于 异常——throws 的小知识点。可能会有人提出疑问为什么这里不写成addIndex(int index,int data) throws SizeException反而写的是addIndex(int index,int data)实际上对于非受检异常运行期检查我们可以写throws也可以不写在工程上我们一般是不写的。而对于受检异常编译期检查我们必须要写throws。写不写都能编译是Java语言为了区分两种异常的设计建议不写是为了保持语义清晰让调用者明白这是他们的代码写错了不是运行时需要处理的外部异常即受检异常3.查找指定节点的数据元素//数据的查找 Override public boolean contains(int key) { ListNode cur head; //进行遍历 while(cur ! null) { if(cur.val key) { return true; } cur cur.next; } return false; } public static void main(String[] args) { //查找链表中是否有指定元素有的话就打印true System.out.print(请输入你要查找的元素); int data4 scanner.nextInt(); System.out.println(mySinglyLinkedList.contains(data4)); }4.删除节点4.1 删除第一次出现关键字为key的节点//节点的删除 private ListNode find(ListNode listNode, int key) { //调用这个方法的前提是已经确定了有这个元素了 ListNode cur1 listNode; ListNode cur2 listNode; //找到指定位置的前一个 int flag 0; while(cur1 ! null) { if(key cur1.val) { break;//表示到了指定位置 } flag; cur1 cur1.next; } //这时候flag所代表的数就是该指定位置的位置默认初始位置是0 //走到这里表示知道了这个指定位置的前一个的位置了那么我们进行遍历 for (int i 0; i flag - 1; i) { cur2 cur2.next; } return cur2; //这一个方法是这样的 //如果删除的元素是第一个那么返回值就是第一个节点 //如果删除的元素不是第一个那么返回值就是该节点的上一个节点 } //1.删除第一次出现关键字为key的节点 Override public void remove(int key) { ListNode cur this.head; //进行遍历 while(cur ! null) { if(cur.val key) { ListNode ret find(this.head, key); if(ret this.head) { //表示的是第一个节点 this.head this.head.next;//删除头节点 }else { //表示的是非第一个节点 ret.next cur.next; } //cur null;置空 //这一步是没有必要的因为java不同于c没有被指向的内存空间会被jvm的GC自动回收 System.out.println(删除成功); return; } cur cur.next; } System.out.println(单链表中没有你要删除的内容); } public static void main(String[] args) { //删除第一次出现为key的节点 System.out.print(请输入你要删除的元素(删除第一个)); int data5 scanner.nextInt(); mySinglyLinkedList.remove(data5); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }4.2 删除全部出现关键字为key的节点//2.删除全部出现关键字为key的节点 Override public void removeAllKey(int key) { while (this.head ! null this.head.val key) { this.head this.head.next; //连续去掉匹配的头节点保证头节点不是指定删除的节点比如 //key 13 //而链表是13、13、13、15、85 } if(this.head null){ return; } ListNode cur this.head.next; ListNode prev this.head; while(cur ! null) { if(cur.val key) { prev.next cur.next; cur cur.next; }else { prev cur; cur cur.next; } } } public static void main(String[] args) {//删除全部出现为key的节点 System.out.print(请输入你要删除的元素删除所有); int data6 scanner.nextInt(); mySinglyLinkedList.removeAllKey(data6); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }4.3 清空链表//删除整个链表 Override public void clear() { while(this.head ! null) { ListNode cur this.head.next; this.head cur; if(this.head ! null) { //表示未走到最后一个位置 cur this.head.next; } } } public static void main(String[] args) { //清空链表 System.out.print(接下来是清空后的链表:); mySinglyLinkedList.clear(); }5.修改节点的元素public class SizeException extends RuntimeException { public SizeException(String message) { super(message); } } //指定位置数据元素的修改 Override public void exchange(int index, int data) { //指定第一个数据节点所在的位置为0 int len size(); //表示指定位置有错那么我们就报错 if(index 0 || index len) { throw new SizeException(你指定位置有误); } ListNode cur this.head; for (int i 0; i index; i) { cur cur.next; } //这里说明到了指定的位置了 cur.val data; } public static void main(String[] args) { //修改指定位置的元素 System.out.print(请输入你要修改的元素); int data_e scanner.nextInt(); System.out.print(请输入你要修改的元素的位置); int index_e scanner.nextInt(); mySinglyLinkedList.exchange(index_e, data_e); System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }2.2.3 总结针对单链表我们需要记住的是单链表是用一段物理地址不连续的存储单元依次存储数据元素的线性结构。也就是说我们需要记住的是单链表的结构至于具体的方法要根据存储的数据元素的类型来进行改写对存储不同类型数据元素的单链表的操作并不相同。2.3 MyDoublyLinkedList双向不带头非循环链表单链表是“向前看”的简洁设计当你需要“回头”时就会付出遍历的代价。而双链表为“回头看”这个能力多花了一点内存每个节点需要额外存储一个prev指针和操作时间执行具体操作步骤时需要多做几次指针赋值换来了更高的灵活性。在学习双向链表时我们不需要有过多压力、认为双向链表很难其实双向链表的操作在逻辑上和单向链表无异只是在实操过程中需要多处理一个指针。2.3.1 基本结构双向链表是通过一组物理地址不连续的存储单元节点来存储数据元素的线性结构。每个节点由数据域存储元素值、指针域存储下一个节点的地址和另一个指针域存储上一个节点的地址组成节点之间的逻辑顺序通过双向的指针链接实现。整个链表通过头指针指向第一个节点来标识通常也会保留尾指针指向最后一个节点以便从尾部操作。第一个节点的“上一个节点”指针指向NULL最后一个节点的“下一个节点”指针也指向NULL表示链表的边界。2.3.2双向链表的增Create、删Delete、查Read、改Update——CRUD1.打印链表Override public void display() { ListNode cur this.head; while(cur ! null) { System.out.print(cur.val ); cur cur.next; } } public static void main(String[] args) { //我们进行打印 System.out.print(目前的链表元素是); mySinglyLinkedList.display(); }2.增加/插入节点2.1 头插法//1.头插法 public void addFirst(int data) { ListNode node new ListNode(data); if(this.head null) { this.head this.tail node; }else { node.next this.head; this.head.prev node; this.head node; } } public static void main(String[] args) { //1.头插 System.out.print(请输入你要添加的元素头插); int data1 scanner.nextInt(); myDoublyLinkedList.addFirst(data1); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }2.2 尾插法//2.尾插法 public void addLast(int data) { ListNode node new ListNode(data); if(this.head null) { this.head this.tail node; }else { node.prev this.tail; this.tail.next node; this.tail node; } } public static void main(String[] args) { //2.尾插 System.out.print(请输入你要添加的元素尾插); int data2 scanner.nextInt(); myDoublyLinkedList.addLast(data2); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }2.3 指定位置插入Override public int size() { ListNode cur this.head; int flag 0; while(cur ! null) { flag; cur cur.next; } return flag; } //3.任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data) { int len this.size(); if(index 0 || index len) { throw new SizeException(你指定的位置有错误); } ListNode node new ListNode(data); if(this.head null) { this.head this.tail node; } ListNode cur this.head; if(index 0) { this.addFirst(data); return; }else if(index len){ this.addLast(data); return; }else { int count 0; while(cur ! null) { if(count index) { break; } count; cur cur.next; } //走到这里表示 cur 为指定位置原来的节点 cur.prev.next node; node.prev node.prev; cur.prev node; node.next cur; } } public static void main(String[] args) { //3.任意位置插入 System.out.print(请输入你要添加的元素); int data3 scanner.nextInt(); System.out.print(请输入你要添加的元素的位置); int index scanner.nextInt(); myDoublyLinkedList.addIndex(index,data3); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }3.查找指定节点的数据元素//数据的查找 Override public boolean contains(int key) { ListNode cur head; //进行遍历 while(cur ! null) { if(cur.val key) { return true; } cur cur.next; } return false; } public static void main(String[] args) { //查找链表中是否有指定元素有的话就打印true System.out.print(请输入你要查找的元素); int data4 scanner.nextInt(); System.out.println(myDoublyLinkedList.contains(data4)); }4.删除节点4.1 删除第一次出现关键字为key的节点//删除第一次出现为key的节点 Override public void remove(int key) { if (this.head null) { System.out.println(当前是空链表不能进行删除); } ListNode cur this.head; while(cur.next ! null) { if(cur.val key) { //走到这里了表示cur就是要删除的节点 System.out.println(链表中有你要删除的节点,已删除一个); if(cur this.head) { this.head this.head.next; }else if(cur this.tail) { this.tail this.tail.prev; }else { cur.prev.next cur.next; cur.next.prev cur.prev; } break; } cur cur.next; } if(cur null) { //表示遍历到了最后了但是还是没有找到 System.out.println(当前链表中没有你要删除的节点); return; } } public static void main(String[] args) { //删除第一次出现为key的节点 System.out.print(请输入你要删除的元素删除第一个); int data5 scanner.nextInt(); myDoublyLinkedList.removeAllKey(data5); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }4.2 删除全部出现关键字为key的节点//删除全部出现为key的节点 Override public void removeAllKey(int key) { if (this.head null) { System.out.println(当前是空链表不能进行删除); } ListNode cur this.head; boolean flag false;//用来判断链表中是否有指定删除的节点 while(cur.next ! null) { if(cur.val key) { //表示找到了 flag true; if(cur this.head) { this.head this.head.next; }else if(cur this.tail) { this.tail this.tail.prev; }else { cur.prev.next cur.next; cur.next.prev cur.prev; } } cur cur.next; } if(flag) { System.out.println(链表中有你要删除的节点已删除所有); } } public static void main(String[] args) { System.out.print(请输入你要删除的元素删除所有); int data6 scanner.nextInt(); myDoublyLinkedList.removeAllKey(data6); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }4.3 清空链表需注意//清空链表 Override public void clear() { if(this.head null) { System.out.println(当前链表已是空链表不需要进行再次清空); return; } ListNode cur this.head; while(cur ! null) { ListNode curN cur.next; cur.prev null; cur.next null; cur curN; } this.head null; this.tail null; } public static void main(String[] args) { System.out.print(接下来是清空后的链表:); myDoublyLinkedList.clear(); myDoublyLinkedList.display(); }以上的清空链表的方法是和LinkedList一样原理的其实我们还有个更简单的方法清空链表那就是//清空链表 Override public void clear() { this.head null; this.tail null; } public static void main(String[] args) { System.out.print(接下来是清空后的链表:); myDoublyLinkedList.clear(); myDoublyLinkedList.display(); }至于为什么可以这样做我们来进行详细讲解一、数据槽的概念JVM 底层没有“变量”和“引用”的语义区分只有数据槽 (Slot)。它是一个确定大小的存储单元比如 32 位或 64 位例 int a 这个a就是数据槽。数据槽里存的都是“值”这个值就是一段二进制数字。区别在于如何解释这个“值”存基本类型这个值就是数据本身。JVM 直接用。存引用类型这个值是对象的地址。JVM 把它作为“线索”去堆里找真正的对象。多了的步骤确实对于引用类型JVM 多了“链接 (reference)”这一步——通过地址去堆里定位对象。二、什么在JVM栈上什么不在JVM栈上存在 JVM 栈上的说明例子局部变量方法内部声明的变量ListNode node new ListNode();方法参数方法传进来的参数public void addFirst(ListNode newNode)里的newNode操作数栈里的临时值JVM 执行字节码时的中间结果不需要关心i过程中的临时值不在栈上的存在哪例子成员变量堆head、tail、next、prev成员方法、静态变量方法区static ListNode cache对象本身堆new ListNode(10)创建出来的东西类定义、方法字节码方法区LinkedList.class三、GC Roots1.什么是 GC RootsGC Roots 是一组必须作为“可达性分析”起点的内存对象。用大白话说GC Roots 就是 JVM 认定“肯定活着”的那批对象以及能直接找到这些对象的引用入口。2.GC Roots干什么的有什么作用JVM 在进行垃圾回收时会以 GC Roots 作为根节点顺着它们的引用链向下查找。所有能被找到的对象都标记为存活找不到的就标记为垃圾等待回收。3.怎么判断是不是 GC Roots一个数据槽内存单元是 GC Roots当且仅当1它不在堆里2它里面存的是一个有效的堆内存地址这两个条件缺一不可。四、为啥令 head tail null 就把这个链表回收了首先myDoublyLinkedList 这个数据槽存储在 JVM栈 上作为GC Root。MyDoublyLinkedList 对象可达 ✅因为栈上有myDoublyLinkedList其次接着向下找当发现 head tail null 时ListNode 节点们不可达 ❌因为head tail null 不能到达 ListNode 对象所以说ListNode 节点就被一个一个的回收了5.修改节点的元素//修改指定位置的元素 Override public void exchange(int index_e, int data_e) { int len this.size(); if (index_e 0 || index_e len - 1) { //注意这里是修改不是尾插 throw new SizeException(你指定的位置有误); } if (this.head null) { System.out.println(这个表是空表无法修改元素); return; } ListNode cur this.head; if (index_e 0) { this.head.val data_e; return; } else if (index_e len - 1) { this.tail.val data_e; return; } else { int count 0; while (cur ! null) { if (count index_e) { break; } count; cur cur.next; } //cur是指定位置的节点 cur.val data_e; } } public static void main(String[] args) { //修改指定位置的元素 System.out.print(请输入你要修改的元素); int data_e scanner.nextInt(); System.out.print(请输入你要修改的元素的位置); int index_e scanner.nextInt(); myDoublyLinkedList.exchange(index_e, data_e); System.out.print(目前的链表元素是); myDoublyLinkedList.display(); }3.LinkedList3.1 LinkedList的简介LinkedList的底层是双向链表结构由于链表没有将元素存储在连续的空间中元素存储在单独的节点中然后通过引用将节点连接起来了因此在在任意位置插入或者删除元素时不需要搬移元素效率比较高。LinkdeList 采用单继承extends、多实现implement的结构关系实线 箭头 继承关系extends虚线 箭头 实现关系implement3.2 LinkedList的使用我们对于LinkedList的使用不进行详细解释只是对某些地方进行简单的提醒有兴趣的可以自己去看一看。3.2.1 LinkedList的基本结构3.2.2 LinkedList的构造方法解释LinkedList()无参构造LinkedList(Collection? extends E c)使用其他集合容器中元素构造Listpublic class TestDemo { public static void main(String[] args) { LinkedListInteger li new LinkedList(); li.add(1); li.add(2); li.add(3); li.add(4); System.out.println(li); LinkedListInteger li1 new LinkedList(li); System.out.println(li1); } }LinkedList() 的含义是创建了一个链表但是这个链表初始的时候是空的LinkedList(Collection? extends E c)的含义是1.我们先不要看? extends E也就是LinkedList(Collection c)这表明了我的参数须是一个实现了Collection接口的数据而我们的 li 是 LinkdeList 类型的LinkedList 实现了 Collection 接口2.? extends E的意思是我们的链表的操作对象的类型需要是E或者其子类 。我们的 li 的操作对象是Integer类型li1 要求的操作对象需要是Integer或者其子类3.这个构造方法的含义就是使用指定集合容器中的元素构造LinkedList3.2.3 LinkedList的遍历LinkedList的遍历有三种分别如下1.通过for循环进行遍历public class TestDemo { public static void main(String[] args) { LinkedListInteger li new LinkedList(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 for循环 进行遍历 for (int i 0; i li.size(); i) { System.out.print(li.get(i) ); } } }2.通过for—each循环进行遍历public class TestDemo { public static void main(String[] args) { LinkedListInteger li new LinkedList(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 for—each循环 进行遍历 for (int x: li) { System.out.print( x ); } } }3.通过迭代器Iterator/ListIterator进行遍历public class TestDemo { public static void main(String[] args) { LinkedListInteger li new LinkedList(); li.add(1); li.add(2); li.add(3); li.add(4); //通过 迭代器Iterator/ListIterator进行遍历 ListIteratorInteger it li.listIterator(); //正向遍历 while(it.hasNext()) { System.out.print(it.next() );// 1 2 3 4 } //反向遍历 while(it.hasPrevious()) { System.out.print(it.previous() );// 4 3 2 1 } } }提醒一句ListIterator继承了Iterator,在 LIstIterator类中多了反向遍历功能相关的方法3.2.4 LinkedList的常用方法4方法解释boolean add(E e)尾插 evoid add(int index, E element)将 e 插入到 index 位置boolean addAll(Collection? extends E c)尾插 c 中的元素E remove(int index)删除 index 位置元素boolean remove(Object o)删除遇到的第一个 oE get(int index)获取下标 index 位置元素E set(int index, E element)将下标 index 位置元素设置为 elementvoid clear()清空boolean contains(Object o)判断 o 是否在线性表中int indexOf(Object o)返回第一个 o 所在下标int lastIndexOf(Object o)返回最后一个 o 的下标ListE subList(int fromIndex, int toIndex)截取部分 list4.ArrayList 和 LinkedList不同点ArrayListLinkedList存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问支持 O(1)不支持O(N)头插需要搬移元素效率低 O(N)只需修改引用的指向时间复杂度为 O(1)插入需要搬移元素效率低 O(N)只需修改引用的指向时间复杂度为 O(1)扩容空间不够时需要扩容没有容量的概念应用场景元素高效存储 频繁访问任意位置插入和删除频繁