2 - Lists

1 IntLists

public class IntList {
    public int first;
    public IntList rest;

    public IntList(int f, IntList r) {
        first = f;
        rest = r;
    }
}

You may remember something like this called a “Linked List”.

// Build a list backwards.
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);

We’ll adopt the usual object oriented programming strategy of adding helper methods to our class to perform basic tasks.

1.1 Size

You are calling size on an object, for example L.size(). If L were null, then you would get a NullPointer error!

/** Return the size of the list using recursion. */
public int size() {
    if (rest == null) {
        return 1;
    }
    return 1 + this.rest.size();
}

/** Return the size of the list using iteration. */
public int iterativeSize() {
    IntList p = this;
    int totalSize = 0;
    while (p != null) {
        totalSize += 1;
        p = p.rest;
    }
    return totalSize;
}

1.2 Get

/** Return the ith item of the list. */
public int get(int i) {
    if (i == 0) {
        return first;
    }
    return rest.get(i - 1);
}

public int iterativeGet(int i) {
    IntList p = this;
    while (i > 0) {
        p = p.rest;
        i--;
    }
    return p.first;
}

2 SLLists

IntList is a naked recursive data structure. In order to use an IntList correctly, the programmer must understand and utilize recursion even for simple list related tasks. This limits its usefulness to novice(新手) programmers, and potentially introduces a whole new class of tricky errors that programmers might run into, depending on what sort of helper methods are provided by the IntList class.

Inspired by our experience with the IntList, we’ll now build a new class SLList (Singe Linked List), which much more closely resembles the list implementations that programmers use in modern languages. We’ll do so by iteratively adding a sequence of improvements.

2.1 Rebranding

我们先把IntList改名为IntNode

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

    public IntNode(int i, IntNode n) {
        item = i;
        next = n;
    }
}

2.2 Bureaucracy

翻译是政府机构、官僚主义？！
我们创建一个SLList类，用户会跟这个类交互

public class SLList {
    public IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }
}

这样，创建一个含一个元素的列表，两者分别是

IntList L1 = new IntList(5, null);
SLList L2 = new SLList(5);

The SLList hides the detail that there exists a null link from the user.

2.3 addFirst and getFirst

public class SLList {
    public IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }

    /** Retrieves the front item from the list */
    public int getFirst() {
        return first.item;
    }
}

Essentially, the SLList class acts as a middleman between the list user and the naked recursive data structure. As suggested above in the IntList version, there is a potentially undesireable possibility for the IntList user to have variables that point to the middle of the IntList.

如果我们给IntList写一个addFirst函数，可以是(注意不能this = new IntList(x, this);)

public void addFirst(int x) {
    IntList old = new IntList(first, rest);
    first = x;
    rest = old;
}

IntList的结构中，第一个结点就代表了整个list，第一个结点和整个list是一个对象，如果

IntList L = new IntList(10, new IntList(20, null));
IntList M = L;
L.addFirst(5);

原本L和M都指向10->20中的10，添加一项后，我们实际上改的是L，所以M也和L一样都指向5->10->20中的5了！可见使用IntList会带来不少潜在的问题，而SLList通过第一个结点当中间人来控制整个list，整个类代表一个list，而第一个结点只是其中的成员。

2.4 Public vs. Private

Unfortunately, our SLList can be bypassed and the raw power of our naked data structure (with all its dangers) can be accessed.

SLList L = new SLList(15);
L.addFirst(10);
L.first.next.next = L.first.next;

This results in a malformed list with an infinite loop. To deal with this problem, we can modify the SLList class so that the first variable is declared with the private keyword.

Private variables and methods can only be accessed by code inside the same .java file, e.g. in this case SLList.java. That means that a class like SLLTroubleMaker below will fail to compile, yielding a first has private access in SLList error.

public class SLLTroubleMaker {
    public static void main(String[] args) {
        SLList L = new SLList(15);
        L.addFirst(10);
        L.first.next.next = L.first.next;
    }
}

In large software engineering projects, the private keyword is an invaluable signal that certain pieces of code should be ignored (and thus need not be understood) by the end user. Likewise, the public keyword should be thought of as a declaration that a method is available and will work forever exactly as it does now.

2.5 Nested Classes

At the moment, we have two .java files: IntNode and SLList. However, the IntNode is really just a supporting character in the story of SLList.

Java provides us with the ability to embed a class declaration inside of another for just this situation.

public class SLList {
       public class IntNode {
            public int item;
            public IntNode next;
            public IntNode(int i, IntNode n) {
                item = i;
                next = n;
            }
       }

       private IntNode first; 

       public SLList(int x) {
           first = new IntNode(x, null);
       } 
...

If the nested class has no need to use any of the instance methods or variables of SLList, you may declare the nested class static, as follows. Declaring a nested class as static means that methods inside the static class can not access any of the members of the enclosing class. In this case, it means that no method in IntNode would be able to access first, addFirst, or getFirst.

public class SLList {
       public static class IntNode {
            public int item;
            public IntNode next;
            public IntNode(int i, IntNode n) {
                item = i;
                next = n;
            }
       }

       private IntNode first;
...

This saves a bit of memory, because each IntNode no longer needs to keep track of how to access its enclosing SLList.

2.6 addLast() and size()

/** Adds an item to the end of the list. */
public void addLast(int x) {
    IntNode p = first;

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

对于size()函数，我们用递归来实现时，会有一个问题，SLList本身不像IntList一样是个递归的结构，它没有什么SLList next;的东西，所以没法用size()获取列表中除了第一个元素后剩下的列表的大小，我们可以创建一个private helper method，专门跟底层的递归的数据结构来交互

/** Returns the size of the list starting at IntNode p. */
private static int size(IntNode p) {
    if (p.next == null) {
        return 1;
    }
    
    return 1 + size(p.next);
}

/** Returns the size of the list. */
public int size() {
    return size(first);
}

Here, we have two methods, both named size. This is allowed in Java, since they have different parameters. We say that two methods with the same name but different signatures are overloaded.

2.7 Caching

目前的size()函数需要线性时间，因为必须遍历整个列表的每个元素，其实，我们可以加入一个size变量到SLList类来记录当前列表的大小，这种通过存储重要数据来加速检索的方法叫caching(缓存)

public class SLList {
    ... /* IntNode declaration omitted. */
    private IntNode first;
    private int size;

    public SLList(int x) {
        first = new IntNode(x, null);
        size = 1;
    }

    public void addFirst(int x) {
        first = new IntNode(x, first);
        size += 1;
    }

    public int size() {
        return size;
    }
    ...
}

This modification makes our size method incredibly fast, no matter how large the list. Of course, it will also slow down our addFirst and addLast methods, and also increase the memory of usage of our class, but only by a trivial amount. In this case, the tradeoff is clearly in favor of creating a cache for size.

2.8 The Empty List

A natural advantage of SLList is that we will be able to easily implement a constructor that creates an empty list.

public SLList() {
    first = null;
    size = 0;
}

Unfortunately, this causes our addLast method to crash if we insert into an empty list. Since first is null, the attempt to access p.next in while (p.next != null) below causes a null pointer exception.

我们当然可以修复addLast，比如加上个if (p == null)，但有更加统一的解决方法，使用这个方法后，addLast自然兼容于空列表

2.9 Sentinel Nodes

public void addLast(int x) {
    size += 1;

    if (first == null) {
        first = new IntNode(x, null);
        return;
    }

    IntNode p = first;
    while (p.next != null) {
        p = p.next;
    }

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

This solution works, but special case code like that shown above should be avoided when necessary. Human beings only have so much working memory, and thus we want to keep complexity under control wherever possible. For a simple data structure like the SLList, the number of special cases is small. More complicated data structures like trees can get much, much uglier.

A cleaner, though less obvious solution, is to make it so that all SLLists are the “same”, even if they are empty. We can do this by creating a special node that is always there, which we will call a sentinel node. The sentinel node will hold a value, which we won’t care about.

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

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

总结一下我们得到的SLList

public class SLList {
    public static class IntNode {
        public int item;
        public IntNode next;
        public IntNode(int i, IntNode n) {
            item = i;
            next = n;
        }
    }
    private IntNode sentinel;
    private int size;

    public SLList() {
        size = 0;
        sentinel = new IntNode(2019, null);
    }
    public SLList(int x) {
        size = 1;
        sentinel = new IntNode(2019, null);
        sentinel.next = new IntNode(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        sentinel.next = new IntNode(x, sentinel.next);
        size += 1;
    }

    /** Retrieves the front item from the list */
    public int getFirst() {
        return sentinel.next.item;
    }

    /** Adds an item to the end of the list. */
    public void addLast(int x) {
        size += 1;
        IntNode p = sentinel;
        while (p.next != null) {
            p = p.next;
        }

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

    /** Returns the size of the list. */
    public int size() {
        return size;
    }
}

2.10 Invariants

An invariant is a fact about a data structure that is guaranteed to be true (assuming there are no bugs in your code).

A SLList with a sentinel node has at least the following invariants:

• The sentinel reference always points to a sentinel node.

• The front item (if it exists), is always at sentinel.next.item.

• The size variable is always the total number of items that have been added.

Invariants make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.

3 DLLists and Arrays

3.1 DLLists

For a long list, the addLast method has to walk through the entire list. Similarly, we can attempt to speed things up by adding a last variable, to speed up our code.

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

如果我们想移除最后一个结点，是比较困难的，因为我们得先找到倒数第二个结点，如果用secondToLast去记录，移除最后一个结点后又得找原先的倒数第三个结点作为现在的倒数第二个结点，所以我们可以再做一个改进

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

这称作Doubly Linked List(DLList)

3.1.1 Sentinel Upgrade

但这样有个问题，last有时（表不空时）指向真实结点，有时（表空）指向sentinel，比如在表空时，如果调用addFirst，还要修改last，我们希望last指向的东西始终是一致的，就跟sentinel一样

所以，我们可以再加入一个sentinel，在列表的结尾

也可以让列表变成循环的，这时last就是sentinel.prev，虽然会变化，但在代码中会是统一的行为

3.1.2 Generic DLLists

In 2004, the creators of Java added generics(泛型) to the language, which will allow you to, among other things, create data structures that hold any reference type.

public class DLList<BleepBlorp> {
    private IntNode sentinel;
    private int size;

    public class IntNode {
        public IntNode prev;
        public BleepBlorp item;
        public IntNode next;
        ...
    }
    ...
}

这里BleepBlorp只是个名字，可以是任何其他名字，现在，我们定义了DLList的泛型版本，在实例化这个类时，需要在声明中把想要的类型放到尖括号里，在实例化时使用空的尖括号即可

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

Since generics only work with reference types, we cannot put primitives like int or double inside of angle brackets, e.g. <int>. Instead, we use the reference version of the primitive type, which in the case of int case is Integer, e.g.

For now, use the following rules of thumb:

• In the .java file implementing a data structure, specify your generic type name only once at the very top of the file after the class name.

• In other .java files, which use your data structure, specify the specific desired type during declaration, and use the empty diamond operator during instantiation.

• If you need to instantiate a generic over a primitive type, use Integer, Double, Character, Boolean, Long, Short, Byte, or Float instead of their primitive equivalents.

3.2 Arrays

Walrus w2 = new Walrus(30, 5.6); gets us 3 total memory boxes. One 64 bit box that stores Walrus references, one 32 bit box that stores the int size of the Walrus, and a 64 bit box that stores the double tuskSize of the Walrus.

Arrays are a special type of object that consists of a numbered sequence of memory boxes. This is unlike class instances, which have named memory boxes.

3.2.1 Extra Information on Arrays

创建数组有三种方式

x = new int[3]; // fill in each memory box with a default value

y = new int[]{1, 2, 3};

int[] z = {7, 8, 9};
// can only be used when combined with a variable declaration

复制数组的信息有一个函数，System.arraycopy，它带5个参数

1. The array to use as a source

2. Where to start in the source array

3. The array to use as a destination

4. Where to start in the destination array

5. How many items to copy
   System.arraycopy(b, 0,x, 3, 2) is the equivalent of x[3:5] = b[0:2] in Python.

二维数组就是数组的数组，比如new int[4][]就是一个有四个盒子的数组，每个盒子里可以放一个整数数组的地址，或者说每个盒子指向一个整数数组，整数数组的长度不固定，而new int[4][4]则是每个整数数组长度为4

用Java Visualizer看一下

int[][] pascalsTriangle;
pascalsTriangle = new int[4][];
int[] rowZero = pascalsTriangle[0];

pascalsTriangle[0] = new int[]{1};
pascalsTriangle[1] = new int[]{1, 1};
pascalsTriangle[2] = new int[]{1, 2, 1};
pascalsTriangle[3] = new int[]{1, 3, 3, 1};
int[] rowTwo = pascalsTriangle[2];
rowTwo[1] = -5;

int[][] matrix;
matrix = new int[4][];
matrix = new int[4][4];

int[][] pascalAgain = new int[][]{{1}, {1, 1},
                                 {1, 2, 1}, {1, 3, 3, 1}};

数组和类都能用来组织一些内存盒子，一个比较大的区别是[]允许我们在运行时再明确下标，比如

int indexOfInterest = askUserForInteger();
int[] x = {100, 101, 102, 103};
int k = x[indexOfInterest];
System.out.println(k);

$ javac arrayDemo
$ java arrayDemo
What index do you want? 2
102

但类就不能在运行时再指定field(声明在类里面、方法外面的变量，用于保存对象或类的状态)，比如

String fieldOfInterest = "mass";
Planet p = new Planet(6e24, "earth");
double mass = p.fieldOfInterest;

编译时会出错

$ javac classDemo
FieldDemo.java:5: error: cannot find symbol
        double mass = earth.fieldOfInterest;        
                           ^
  symbol:   variable fieldOfInterest
  location: variable earth of type Planet

4 ALists

Accessing the ith element of an array takes constant time on a modern computer.

简单来说，比如C语言的x = arr[500];实际上等价于x = *(arr + 500);，实际上只需要几步运算，即常数的单位时间。而我们之前使用的linked list，最坏情况下找第i个元素需要线性时间，取决于列表的大小

4.1 The Naive AList

public class AList {
    
    private int[] items;
    private int size;

    public AList() {
        items = new int[100]; // 100 is arbitrary.
        size = 0;
    }
    

    /** Gets the i th item in the list (0 is the front). */
    public int get(int i) {
        return items[i];
    }

    /** Retrieves the last item from the list */
    public int getLast() {
        return items[size - 1];
    }

    /** Adds an item to the end of the list. */
    public void addLast(int x) {
        items[size] = x;
        size += 1;
    }

    /** Returns the size of the list. */
    public int size() {
        return size;
    }
}

4.2 The Allegory of the Cave

下面我们想实现removeLast()
先设想一下，比如用户有一个列表[1, 2, 3]
调用一次removeLast()，用户会认为现在的列表是[1, 2]

我们要做的只是让列表表现得跟用户预期的一样，至于我们做了什么让列表能够这样，这并不重要，比如现在，真实的"actual truth"是我们用一个数组来表示列表，然后通过什么size -= 1的操作来实现移除，但之前的"actual truth"其实是个DLList，我们可以通过(last.prev)什么的来做移除。

对于用户来说，无论是AList还是DLList，它们的behavior都是一样的，用户就像是柏拉图洞穴寓言里看着洞穴壁上影子的人，我们就像是墙后拿着物体的人，用户看到的就是洞穴壁上影子呈现出的世界，如果用户看到一只鸟的影子并用弓箭射它，我们在墙的后面就也要把鸟的物体放下来

public int removeLast() {
    int x = getLast();
    size -= 1;
    return x;
}

实际上我们不需要把删除的那个元素设置为0，因为AList的不变量就是

• 下一个元素的位置是size
• size是AList的元素个数
• 列表中最后一个元素的位置是size-1
  移除最后一个元素，只需要调整size来维持不变量就够了，不用设置元素的值

4.3 Resizing ArrayList

数组的大小是固定的，万一元素个数超过100了怎么办呢，我们可以再创建一个新的更大的数组，让它成为新的items

/** Resizes the underlying array to the target capacity. */
private void resize(int capacity) {
    int[] a = new int[capacity];
    System.arraycopy(items, 0, a, 0, size);
    items = a;
}

public void addLast(int x) {
    if (size == items.length) {
        resize(size + 1);
    }
    items[size] = x;
    size += 1;
}

4.4 Analyzing the Naive Resizing Array

The approach that we attempted in the previous section has terrible performance. By running a simple computational experiment where we call addLast 100,000 times, we see that the SLList completes so fast that we can’t even time it. By contrast our array based list takes several seconds.

我们来思考这样一个问题，一个大小为100的数组，如果我们调用两次addLast，我们需要创建并填满多少个盒子呢？
第一次要创建一个101个盒子的数组，第二次要102个，一共203个

How many total boxes will we have at any one time, assuming that garbage collection happens as soon as the last reference to an array is lost?
第一次resize过程中，只要没复制完，原来的数组总是存在，最多会有201个盒子同时存在，之后原数组就被回收了，第二次resize时最多会有203个盒子同时存在

Creating all those memory boxes and recopying their contents takes time.

The SLList shows a straight line, which means for each add operation, the list takes the same additional amount of time. This means each single operation takes constant time.(这是因为常数积分得到的就是一条直线。理论上也确实如此，只需新建结点，然后改变一下指向即可，整体是常数时间)

By contrast, the naive array list shows a parabola, indicating that each operation takes linear time, since the integral of a line is a parabola. (理论上，如果超出容量，addLast需要新建数组并把原先数组的元素复制过来，必然要遍历整个数组，时间是线性的，考虑每次都会超出容量，那么时间跟数组元素数量的关系就是$t=n$，那么addLast $n$次的时间就是 $1+2+...+n=O(n^2)$ )

4.5 Geometric Resizing

We can fix our performance problems by growing the size of our array by a multiplicative amount.

public void addLast(int x) {
    if (size == items.length) {
        resize(size * REFACTOR);
    }
    items[size] = x;
    size += 1;
}

这样就会快很多，变成线性时间，后面我们会解释为什么

4.6 Memory Performance

Our AList is almost done, but we have one major issue. Suppose we insert 1,000,000,000 items, then later remove 990,000,000 items. In this case, we’ll be using only 10,000,000 of our memory boxes, leaving 99% completely unused.

To fix this issue, we can also downsize our array when it starts looking empty. Specifically, we define a “usage ratio” $R$ which is equal to the size of the list divided by the length of the items array.

In a typical implementation, we halve the size of the array when $R$ falls to less than 0.25.

public int removeLast() {
    int x = getlast();
    size--;

    double usageRatio = (double) size / items.length;

    // You can specify a minimal capacity.
    if (usageRatio < 0.25 && items.length > MIN_CAPACITY) {
        resize(items.length / 2);
    }

    return x;
}

4.7 Generic ALists

Just as we did before, we can modify our AList so that it can hold any data type, not just integers. To do this, we again use the special angle braces notation in our class and substitute our arbitrary type parameter for integer wherever appropriate. For example, below, we use Item as our type parameter.

There is one significant syntactical difference: Java does not allow us to create an array of generic objects due to an obscure issue with the way generics are implemented.

Item[] items = new Item[8]; // No !

Item[] items = (Item []) new Object[8]; // Yes !

The other change we make is that we null out any items that we “delete”. Whereas before, we had no reason to zero out elements that were deleted, with generic objects, we do want to null out references to the objects that we’re storing. This is to avoid “loitering(游荡引用)”. Recall that Java only destroys objects when the last reference has been lost. If we fail to null out the reference, then Java will not garbage collect the objects that have been added to the list.

public Item removeLast() {
    Item x = items[size - 1];

    items[size - 1] = null;
    size--;

    double usageRatio = (double) size / items.length;

    if (usageRatio < 0.25 && items.length > MIN_CAPACITY) {
        resize(items.length / 2);
    }

    return x;
}

如果“删除”后不设置为null，直到新的数据覆盖上来，这个引用一直在那个内存盒子中，因此不会被回收，即逻辑上元素被删除，但数组还保存着那个对象的引用，注意这里是Item必须代表引用类型，因为泛型要求一定是引用类型

4.8 Insert

最后我们实现一下插入

public void insert(int position, Item x) {
    Item[] a = (Item[]) new Object[items.length + 1];

    System.arraycopy(items, 0, a, 0, position);
    a[position] = x;

    System.arraycopy(items, position, a, position + 1, items.length - position);
    items = a;
}

public void addFirst(Item x) {
    insert(0,x);
}

public getFirst() {
    return get(0);
}