The List ADT (ArrayList)

链表通常包含的操作有:

• printList and makeEmpty
• find:返回第一个元素的位置
• insert and remove:从某个位置插入或者移除

Simple Array implementation of Lists

这些操作可以使用数组实现。虽然数组有一个固定的容量，但当我们需要时我们可以创建一个两倍容量的新数组。

int [] arr = new int [10];
...
//Later on we decide arr needs to be larger.
int [] newArr = new int [arr.length * 2];
for (int i=0; i<arr.length; i++)
  newArr[i] = arr[i];
arr = newArr;

数组实现可以使printList在线性时间完成，findKth操作常量时间。但是，insert和delete取决于插入和删除的位置，有可能非常昂贵。当查询和打印操作频繁时可以使用数组实现，但是当插入和删除频繁时可以使用the linked list。

Simple Linked Lists

为了避免插入和删除的线性复杂度，我们需要保证链表不是被连续存储，这样我们就可以不用移动剩余元素的位置。
链式链表包含一系列节点，不需要在内存中临近，每一个节点包含一个元素和一个连接到他的继任节点,我们称之为next链接，最后一个单元的next为null。

Lists in the Java Collections API

Collections API属于包java.util。集合的方法通常包含以下几种，它们做一些如它们名字含义的事情，集合并不指定如何判断x是否在集合中，这由具体的实现来保证。add和remove返回true当操作成功时，反之false。Collection interface实现了Iterable接口，从而可以通过for循环来遍历访问所有元素。

public interface Collection<AnyType> extends Iterable<AnyType>
{
  int size();
  boolean isEmpty();
  void clear();
  boolean contains(AnyType x);
  boolean add(AnyType x);
  boolean remove(AnyType x);
  java.util.Iterator<AnyType> iterator();
}

public static <AnyType> void print(Collection<AnyType> coll)
{
  for(AnyType item:coll)
    System.out.println(item);
}

public interface Iterator<AnyType>
{
  boolean hasNext();
  AnyType next();
  void remove();
}

public static <AnyType> void print(Collection <AnyType> coll)
{
  Iterator<AnyType> itr = coll.iterator();
  while(itr.hasNext())
  {
    AnyType item = itr.next();
    System.out.println(item);
  }
}

The List interface, ArrayList and LinkedList

List interface继承Collection接口，因此它包含Collection的所有操作，并附加了一些其他操作。get和set允许客户端访问或修改指定位置的元素，listIterator提供一个更复杂的Iterator。

public interface List<AnyType> extends Collection<AnyType>
{
  AnyType get(int idx);
  AnyType set(int idx, AnyType newVal);
  void add(int idx, AnyType x);
  void remove(int idx);
  ListIterator<AnyType> listIterator(int pos);
}

有两种最流行的链表实现：ArrayList和LinkedList
ArrayList的优点是获取和更改数据可以在常量时间完成，缺点是插入新数据和删除数据则比较昂贵，除非你是在最后一个节点。LinkedList提供了List的双向链表实现，优点则是删除和插入数据非常容易，但LinkedList没用索引，无法直接get到相应数据。
以删除方法为例

public static void removeEventsVers1(List<Interger> lst)
{
    int i = 0;
    while(i < lst.size()) 
        if(lst.get(i) % 2 == 0) 
            lst.remove(i);
        else
            i++;
}

对于ArrayList来说复杂度是平方的，而对于LinkedList由于get的低效时间复杂度也是平方的。

public static void removeEventsVer2(List<Interger> lst)
{
    for(interger x : lst)
        if(x % 2 == 0)
            lst.remove(x);
}

上面这个方法尝试解决这个问题，为了替代get方法，使用iterator来迭代链表。但我们使用Collection的remove方法则会再次寻找这个变量。更严重的是，当我们运行这个代码时，程序会直接报错，因为当元素被删除时，增强for循环潜在使用的iterator是无效的。

public static void removeEventsVer3(List <interger> lst)
{
    Iterator<Integer> itr = lst.iterator();
    
    while(itr.hasNext())
        if(itr.next() % 2 == 0)
            itr.remove();
}

这个方法则可以解决这个问题。同时，对于LinkedList来说删除的操作是常量时间的。

ArrayList实现

我们现在要自己设计一个ArrayList，它大致应该满足以下几点：

1. MyArrayList会保留基本的数组，数组容量，和存储一定的元素
2. MyArrayList需要提供一个机制可以改变低层数组的容量。容量通过获取新的数组，并复制老的数组到新的数组，同时允许虚拟机回收老数组
3. MyArrayList提供get和set的实现
4. MyArrayList提供基本的操作，例如：size、isEmpty、clear、remove、add。add可能会导致容量的增加
5. MyArrayList提供一个类实现Iterator的接口。这个类会存储下一个元素的索引，提供next、hasNext、remove方法。MyArrayList的iterator方法返回一个实现了Iterator接口的实例。

public class MyArrayList<AnyType> implements  Iterable<AnyType> {
    private static final int DEFAULT_CAPACITY = 10;

    
    private  int theSize;
    private AnyType [] theItems;

    public  MyArrayList() {
        doClear();
    }

    public  void clear() {
        doClear();
    }

    private void doClear() {
        theSize = 0;
        ensureCapacity(DEFAULT_CAPACITY);
    }

    public int size() {
        return theSize;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public void trimToSize() {
        ensureCapacity(size());
    }

    public AnyType get(int idx) {
        if (idx < 0 || idx >= size()) {
            throw  new ArrayIndexOutOfBoundsException();
        }
        return theItems[idx];
    }

    public AnyType set(int idx, AnyType newVal) {
        if (idx < 0 || idx >= size()) {
            throw  new ArrayIndexOutOfBoundsException();
        }
        AnyType old = theItems[idx];
        theItems[idx] = newVal;
        return old;
    }

    public void ensureCapacity(int newCapacity) {
        if (newCapacity < theSize)
            return;

        AnyType [] old = theItems;
        theItems = (AnyType []) new Object[newCapacity];
        for (int i = 0; i < size(); i++) {
            theItems[i] = old[i];
        }
    }

    public boolean add(AnyType x) {
        add(size(), x);
        return true;
    }

    public void add(int idx, AnyType x) {
        if(theItems.length == size()) {
            ensureCapacity(size() * 2 + 1);
        }
        for(int i = theSize; i >idx; i--)
            theItems[i] = theItems[i - 1];
        theItems[idx] = x;

        theSize++;
    }

    public AnyType remove(int idx) {
        AnyType removedItem = theItems[idx];
        for(int i = idx; i < size() - 1; i++) {
            theItems[i] = theItems[i + 1];
        }

        theSize--;
        return removedItem;
    }

    public java.util.Iterator<AnyType> iterator() {
        return new ArrayListIterator();
    }

    private class ArrayListIterator implements  java.util.Iterator<AnyType> {
        private int current = 0;

        public boolean hasNext() {
            return current <size();
        }

        public AnyType next() {
            if (!hasNext()) {
                throw new java.util.NoSuchElementException();
            }
            return theItems[current++];
        }

        public void remove() {
            MyArrayList.this.remove(--current);
        }
    }
}