关于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