宿迁网站建设,个人网站psd,WordPress高级版破解,像网站的ppt怎么做的本文内容为构建双向循环链表、使用 Java 的泛型将其优化为通用类型的链表以及数组的基本语法介绍。
1. 双向链表
回顾上一节课写的代码#xff0c;当执行 addLast() 与 getLast() 方法时需要遍历链表#xff0c;效率不高#xff0c;因此可以添加一个指向链表末尾的索引当执行 addLast() 与 getLast() 方法时需要遍历链表效率不高因此可以添加一个指向链表末尾的索引这样 addLast() 与 getLast() 方法的时间复杂度就为 O ( 1 ) O(1) O(1)。
但是我们再考虑一下 removeLast() 方法如下图所示 即使我们有了指向链表末尾的指针 last但是当我们要移除最后一个节点时需要的不是最后一个节点“50”的信息而是倒数第二个节点“9”我们需要将“9”的 next 置为 null并将 last 指向“9” 那么我们想要定位到这个节点“9”的唯一方法还是需要从头遍历一遍链表同理如果你想将 last 指向链表的倒数第二个节点认为这样就能快速定位那么就会有新的问题当节点“50”被删除后如何更新 last 指向节点“3”显然又需要从头遍历链表。
有什么办法能快速定位到这个节点呢我们可以让每个节点不仅指向后一个节点还能指向前一个节点这就是双向链表Doubly Linked List 但是此时又会出现棘手的问题那就是 last 指针在链表为空时会指向哨兵节点在链表不为空时又会指向最后一个实值节点 有什么办法能统一起来呢能想到的第一个方案就是同样给尾部设定一个哨兵节点就和之前的表头哨兵节点类似 此外还有更完美的解决方案那就是构建循环链表这样只需要一个哨兵节点无需指向链表末尾的指针当链表为空时哨兵的前一个节点和后一个节点都是指向自己当链表不为空时哨兵的前一个结点为末尾节点末尾节点的后一个节点为哨兵 实现代码如下
package CS61B.Lecture5;public class DLList {private static class IntNode {public int val;public IntNode next;public IntNode prev;public IntNode(int val, IntNode next, IntNode prev) {this.val val;this.next next;this.prev prev;}}private IntNode sentinel new IntNode(0, null, null);private int size;public DLList() {this.sentinel.next this.sentinel.prev sentinel;this.size 0;}public DLList(int val) {IntNode p new IntNode(val, this.sentinel, this.sentinel);this.sentinel.next this.sentinel.prev p;this.size 1;}public int size() {return this.size;}public int getFirst() {return this.sentinel.next.val;}public void addFirst(int val) {IntNode p new IntNode(val, this.sentinel.next, this.sentinel);this.sentinel.next.prev p;this.sentinel.next p;this.size;}public void removeFirst() {if (this.size 0) return;this.sentinel.next.next.prev this.sentinel;this.sentinel.next this.sentinel.next.next;this.size--;}public int getLast() {return this.sentinel.prev.val;}public void addLast(int val) {IntNode p new IntNode(val, this.sentinel, this.sentinel.prev);this.sentinel.prev.next p;this.sentinel.prev p;this.size;}public void removeLast() {if (this.size 0) return;this.sentinel.prev.prev.next this.sentinel;this.sentinel.prev this.sentinel.prev.prev;this.size--;}Overridepublic String toString() {StringBuilder res new StringBuilder(DLList: [);IntNode p this.sentinel;while (p.next ! this.sentinel) {res.append(p.next.val);p p.next;if (p.next ! this.sentinel) res.append(, );}res.append(]);return res.toString();}public static void main(String[] args) {DLList L new DLList();L.addFirst(5);L.addFirst(10);System.out.println(L.getFirst()); // 10System.out.println(L); // DLList: [10, 5]L.removeFirst();System.out.println(L); // DLList: [5]System.out.println(L.size()); // 1L.addLast(20);System.out.println(L.getLast()); // 20System.out.println(L); // DLList: [5, 20]L.removeFirst();L.removeLast();System.out.println(L); // DLList: []}
}2. 通用类型双向链表
现在我们的链表只能存放整数如果想存放其他数据类型例如字符串那么需要拷贝一份代码将其中的 int 修改为 String显然这样很冗余。
如果想实现一个通用类型的数据结构就需要引入 Java 的泛型概念我们可以将 DLList 定义为泛型类这样能够编写出类型安全的、可重用的代码同时避免类型转换的繁琐操作和潜在的运行时错误。
通过在 中添加类型参数用来表示泛型类型参数通常使用单个大写字母表示常见的命名约定如下
TType类型EElement元素KKey键VValue值NNumber数字
需要注意
泛型类型参数必须是引用类型不能是基本数据类型如 int、double 等。如果需要使用基本数据类型可以使用其对应的包装类如 Integer、Double。泛型类型参数不能是 final 修饰的类因为它们不能被继承。
package CS61B.Lecture5;public class DLListT {private class IntNode {public T val;public IntNode next;public IntNode prev;public IntNode(T val, IntNode next, IntNode prev) {this.val val;this.next next;this.prev prev;}}private IntNode sentinel new IntNode(null, null, null);private int size;public DLList() {this.sentinel.next this.sentinel.prev sentinel;this.size 0;}public DLList(T val) {IntNode p new IntNode(val, this.sentinel, this.sentinel);this.sentinel.next this.sentinel.prev p;this.size 1;}public int size() {return this.size;}public T getFirst() {return this.sentinel.next.val;}public void addFirst(T val) {IntNode p new IntNode(val, this.sentinel.next, this.sentinel);this.sentinel.next.prev p;this.sentinel.next p;this.size;}public void removeFirst() {if (this.size 0) return;this.sentinel.next.next.prev this.sentinel;this.sentinel.next this.sentinel.next.next;this.size--;}public T getLast() {return this.sentinel.prev.val;}public void addLast(T val) {IntNode p new IntNode(val, this.sentinel, this.sentinel.prev);this.sentinel.prev.next p;this.sentinel.prev p;this.size;}public void removeLast() {if (this.size 0) return;this.sentinel.prev.prev.next this.sentinel;this.sentinel.prev this.sentinel.prev.prev;this.size--;}Overridepublic String toString() {StringBuilder res new StringBuilder(DLList: [);IntNode p this.sentinel;while (p.next ! this.sentinel) {res.append(p.next.val);p p.next;if (p.next ! this.sentinel) res.append(, );}res.append(]);return res.toString();}public static void main(String[] args) {DLListString L new DLList(); // new DLListString()中的String可以省略Java会自动判断L.addFirst(World);L.addFirst(Hello);System.out.println(L.getFirst()); // HelloSystem.out.println(L); // DLList: [Hello, World]L.removeFirst();System.out.println(L); // DLList: [World]System.out.println(L.size()); // 1L.addLast(Algorithm);System.out.println(L.getLast()); // AlgorithmSystem.out.println(L); // DLList: [World, Algorithm]L.removeFirst();L.removeLast();System.out.println(L); // DLList: []}
}注意 IntNode 类需要改为非静态的泛型类型变量不能直接在静态方法或静态上下文中使用因为泛型类型变量是与类的实例相关联的而静态上下文与类的实例无关。
3. 数组
数组的大小在创建时必须指定并且一旦创建其大小不能改变。如果需要更大的数组必须创建一个新的数组并复制数据。但数组通过索引直接访问元素时间复杂度为 O ( 1 ) O(1) O(1)适合频繁读取的场景。
3.1 数组基本语法
建议每次创建数组时都使用关键字 new因为数组也是一个 Object在声明了数组中的变量后也可以省略 new 关键字
package CS61B.Lecture5;import java.util.Arrays;public class ArraySyntax {public static void main(String[] args) {int[] a new int[3];int[] b new int[]{1, 2, 3};int[] c {1, 2, 3};Arrays.stream(a).forEach(x - System.out.print(x )); // 0 0 0System.out.println();Arrays.stream(b).forEach(x - System.out.print(x )); // 1 2 3System.out.println();Arrays.stream(c).forEach(x - System.out.print(x )); // 1 2 3}
}现在再来看下面这段代码
package CS61B.Lecture5;public class ArrayBasics {public static void main(String[] args) {int[] a null;int[] b, c;b new int[]{1, 2, 3, 4, 5};c b;b new int[]{-1, 2, 5, 4, 99};c new int[3];a new int[0];int b_length b.length;String[] s new String[6];s[4] ketchup;s[b[3] - b[1]] muffins;int[] x {9, 10, 11};System.arraycopy(x, 0, b, 3, 2);}
}首先声明了一个名为 a 的数组引用但是并没有调用 new 关键字此时 Java 并没有创建空间只是创建了用于存放数组引用的整数空间。同样 b 和 c 只是声明了一个整数数组的引用未存放实际的数组。
之后通过初始化了一个长度为5的数组new 关键字使得 Java 在内存中挖掘5个连续的位置用来存放这个数组的内容并将其地址返回给变量 b。当执行 c b 时是将数组的引用赋值给 c因此实际上这时候 b 和 c 指向了同一个数组如下图所示 接下来执行的 b new int[]{-1, 2, 5, 4, 99}; 语句使用 new 关键字重新创建了一个数组这时候新数组返回了一个新的内存地址此时 b 和 c 便指向了不同数组 再看下一步的 c new int[3]; 改变了 c 使其指向一个新的长度为3的数组 此时最早创建的数组 {1, 2, 3, 4, 5} 消失了因为已经没有任何引用能找到这个数组的地址了垃圾收集器会将其清理掉永远无法再访问这个数组。
再看下一行创建了一个长度为0的数组虽然这样几乎没什么意义但是只是想说明一下可以这么做 b.length 能够获取 b 所指向的数组的长度但是从之前的图上我们没看到任何其他变量能够记录数组的长度因此事实证明数组有一个隐秘的实例变量记录长度通过 Java Visualizer 无法查看这个值在哪。
String 是引用数据类型因此如果创建了数组并不能将字符串的值直接存放在数组的那个位置上而是在其他某个位置创建一个字符串对象后再将其引用存放在数组的某个位置上。
最后一行的 System.arraycopy() 方法是将 x 数组从0开始索引取2个值也就是 [9, 10]复制到 b 数组从3开始索引的对应位置上 3.2 二维数组
我们创建一个4行的二维数组
package CS61B.Lecture5;public class Array2D {public static void main(String[] args) {int[][] a new int[4][];a[0] new int[]{1};a[1] new int[]{1, 1};a[2] new int[]{1, 2, 1};a[3] new int[]{1, 3, 3, 1};}
}此时我们实际上是在内存中创建了5个数组a 指向了一个长度为4的数组这个数组中的每个位置又存放了一个指向某个一维数组的引用如下图所示
