\(2.5\)数组型链表

1.数组型链表的引入与搭建

  在\(SLList\)与\(DLList\)中，我们可以轻易地实现getFirst和getLast，但只能用线性的时间复杂度实现get(int index)。而数组可以实现常数时间复杂度的访问(参考\(cs61a\)的懒惰计算)。

  可以初步搭建出以下的\(AList\)框架：

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

    public AList {
        items = new int[100];
        size = 0;
    }

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

    public void get(int index) {
        return items[i];
    }

    public int size() {
        return size;
    }
}

  这一实现遵循了以下不变量：

• 下一个插入元素的插入位置一直是\(size\)。
• \(AList\)中的元素数量永远是\(size\)。
• 最后一个元素的位置永远是\(size-1\)。

2.对链表的思考

  在实现removeLast操作时，我们先明确一个重要的发现：在我们实现某个方法时，对链表的任何改变都应该导致一个或多个内存盒子(\(memory\;box\))的改变。

  链表是一个抽象的概念用户使用我们提供的抽象(addLast，removeLast)来对列表进行的任何更改，而我们必须将这些更改以符合用户期望的方式反映在这些内存盒子中。中间的过程并不重要，我们只需要让数组型链表的行为与用户所设想的相一致就好了。

  而\(size\)，\(items\)，\(items[i]\)的内存盒子(\(memory\;boxes\))是这个概念的具体表示，是我们已经设计好的事实。我们的目标就是通过操作这些具体的表示形式，来实现用户想要的模型。

3.removeLast的实现

  通过上面对链表的思考，我们可以只通过改变\(size\)来实现removeLast：

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

  这种removeLast的实现是基于\(AList\)的不变量的。只要我们改变\(Size\)，那么下一个元素插入的位置就一定是\(size\)，不管\(size\)这个位置有没有元素，而最后一个元素的位置是\(size-1\)，用户并不能去访问\(size\)这个位置。因此可以通过这个手段实现元素的删除。至于\(size\)位置的元素，我们想把它改为几都可以。

  不过，与\(int\)型的链表不同，当我们链表的存储类型为\(generic\)时，我们会将\(size\)位置的元素置为null，因为如果对\(size\)位置的元素置之不理的话，这个元素就会一直占用内存，导致内存的浪费。而设为null后，由于对它的引用丢失了，\(Java\)会在内存中删掉它。

4.数组大小的调整

  在\(Java\)中，数组必须有固定的大小，因此在数组容量不够时，我们需要调整数组的大小(\(resize\))。

  实现调整数组的办法很简单：创建一个具有所需大小的数组，然后把原数组的元素复制过来，最后返回这个新数组即可：

int[] a = new int[size + 1];
System.arraycopy(items, 0, a, 0, size);
a[size] = 11;
items = a;
size = size + 1;

  但是，这种在需要扩容时增加一部分的做法过于缓慢。例如我们每次扩容\(1\)，则当数组扩容到\(n\)时，由于每次扩容都要先创建一个新的数组，一共创建了\(\sum_{i=1}^n i ={ {n(n+1)}\over 2}\)个单位大小的数组，时间复杂度为\(O(n^2)\)，这样的效率十分低。

  因此，我们一般不采用上面的扩容方式，而是在需要扩容的时候适当地多扩大一些，以减少创建数组的次数。一般的做法如下：

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

5.内存使用率

  数组中的实际元素个数与数组大小之比的数值是内存利用率。下面的数组的内存使用率为\(0.04\)：

  当数组的内存使用率较低的时候，我们可以考虑resize(size \ 2)，缩小数组空间来节约内存。这种做法被称为以空间换时间。