关于java:cs61b-week2The-DLList

双链表

问题

本节没有讲太多常识，次要是围绕优化方面来开展，构想一下，对于单链表的 addLast()办法

public void addLast(int x) {
    size += 1;
    IntNode p = sentinel;
    while (p.next != null) {p = p.next;}

    p.next = new IntNode(x, null);
}

能够看出每次在增加一个新的开端结点之前都要遍历到以后的开端结点，工夫复杂度是 O(n), 有没有办法能够达到 O(1)的呢？

优化 1

增加一个变量 last，总是指向最初一个结点，相似于 C 语言的 尾指针

public class SLList {

    private IntNode last;

    public void addLast(int x) {last.next = new IntNode(x, null);
        last = last.next;
        size += 1;
    }
    ...
}

这样做之后对于新增开端结点 addLast()与求开端结点的值 getLast()的工夫复杂度都能够优化到 O(1)，然而对于 removeLast()，也就是删除开端结点来说，复杂度仍是 O(n), 因为当我要删除开端结点，那么我须要找到倒数第二个结点并将其 next 赋值为 NULL, 仍然须要从头遍历整个链表

优化 2

思考给每个结点减少一个 prev 指针域，指向其前一个结点，这样的话对于一个结点来说，既能够拜访其前一个结点，也能够拜访其后一个结点，也就是双链表

public class IntNode {
    public IntNode prev;
    public int item;
    public IntNode next;
}

优化之后，当咱们须要删除最初一个结点时，只需
last.prev.next = null
即可删除最初一个结点，工夫复杂度降到 O(1)
随之而来的问题是，当一个链表所有结点都删完了，只剩下哨兵结点时，sentinel 与 last 一起指向哨兵结点
这也就是说 last 有时候指向失常的结点，有时候却指向哨兵结点，因而咱们可能须要加很多特判条件，比方当删除到只剩哨兵结点时

优化 3

那么咱们能够思考减少两个哨兵结点，一个在头部，一个在尾部，家喻户晓哨兵结点数据域咱们不关怀（图中的？？），哨兵结点即标记结点的作用

另一种办法即 循环双链表，共享同一个哨兵结点，如图所示

泛型

咱们的 IntNode 代码定义是

    public class IntNode {
        public IntNode prev;
        public int item;
        public IntNode next;

这意味着咱们只能对链表结点的数据域增加整数，倘如咱们尝试应用字符串

DLList d2 = new DLList("hello");
d2.addLast("world");

那么很显然编译器会报错，一个间接的办法是将 int 全副改为 String，然而当我又想生成Double 类型的结点呢？岂不是又要改一遍，十分麻烦，因而 Java 提供了一种叫做 泛型 的语法，咱们只需在 class name(类名)前面加上 <Parameter>, 当咱们想应用任何类型的变量时，往里面传参即可，命名为 ElemType 只是便于了解，你能够自定义任何名字
DLList 能够包容任何类型的泛型如下所示：

public class DLList<ElemType> {
    private stuffNode sentinel;
    private int size;

    public class stuffNode {
        public stuffNode prev;
        public ElemType item;
        public stuffNode next;
        ...
    }
    ...
}

咱们曾经定义了 DLList 类的泛型。当咱们在 main()函数中应用时，传入咱们想实现的类型即可，咱们在申明时，将所需类型放在尖括号内，并在实例化时应用 < >。例如：
字符串类型

DLList<String> d2 = new DLList<>("hello");
d2.addLast("world");

整数类型

DLList<Integer> d1 = new DLList<>(5);
d1.addFirst(10);

留神
实例化泛型时，传参必须是类型的大写，即
Integer, Double, Character, Boolean, Long, Short, Byte, Float
而非int char