算法与数据结构回顾--线性表（1）

既然叫回顾，当然不能仅仅介绍基础，这里主要解析java的线性表--List、map、set。

ArrayList

ArrayList的数据结构是由数组实现的，数组的初始化需要定义大小。所以使用ArrayList之前要估计List的大小。太小虽然不会出现溢出的异常，但是因为需要扩容所以浪费了很多资源，太大又浪费空间。

ArrayList初始化源代码：

    public ArrayList(int initialCapacity) {super();        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal Capacity: "+                                               initialCapacity);this.elementData = new Object[initialCapacity];    }    public ArrayList() {this(10);    }

?扩容代码：

    public void ensureCapacity(int minCapacity) {modCount++;int oldCapacity = elementData.length;if (minCapacity > oldCapacity) {    Object oldData[] = elementData;    int newCapacity = (oldCapacity * 3)/2 + 1;        if (newCapacity < minCapacity)newCapacity = minCapacity;            // minCapacity is usually close to size, so this is a win:            elementData = Arrays.copyOf(elementData, newCapacity);}    }

可见，ArrayList在容量不足时，就会通过复制数组的方式扩容。这种做法比较浪费资源。

这里的modCount是用来检测iterator操作不一致的，比如在迭代List的同时又修改List，这就是并发问题了，是不允许的。所以要及时抛出ConcurrentModifacationException.如下：

public static void main(String[] args){List<String> strings = new ArrayList<String>();for(int i=0;i<10;i++){strings.add(String.valueOf(i));}Iterator it = strings.iterator();for(int i=0;i < strings.size();i++){System.out.println(it.next());strings.remove(i);}}

?检索代码：

    public E get(int index) {RangeCheck(index);return (E) elementData[index];    }

?可见检索的效率是非常高的，时间复杂度只为O(1)。但同时发现这个方法不是线程安全的，但同时相对于线程安全的方法，效率高一些。如果先要将ArrayList转换为线程安全的可以使用Collections.synchronizedCollection(strings)。 这个方法是用代理模式，将方法加锁。

删除代码：

    public E remove(int index) {RangeCheck(index);modCount++;E oldValue = (E) elementData[index];int numMoved = size - index - 1;if (numMoved > 0)    System.arraycopy(elementData, index+1, elementData, index,     numMoved);elementData[--size] = null; // Let gc do its workreturn oldValue;    }

?添加代码和这个相差不多，这里就不多说了。这里面的删除时然被删除的元素后面的元素依次向左移动一位。所以时间复杂度是O(n)。同样线程不安全，不建议在删除多的操作上使用ArrayList。

LinkedList：

初始化：

Entry(E element, Entry<E> next, Entry<E> previous) {    this.element = element;    this.next = next;    this.previous = previous;}    public LinkedList() {        header.next = header.previous = header;    }

?从这个代码开来，LinkedList是一个环形双向链表。它有2个头指针一个指向一个指向链表的头部一个指向链表的尾部，这样它就可以找检索路径最短的那一段开始检索。代码如下：

    private Entry<E> entry(int index) {        if (index < 0 || index >= size)            throw new IndexOutOfBoundsException("Index: "+index+                                                ", Size: "+size);        Entry<E> e = header;        if (index < (size >> 1)) {            for (int i = 0; i <= index; i++)                e = e.next;        } else {            for (int i = size; i > index; i--)                e = e.previous;        }        return e;    }

?这里使用了nb的位运算，它比正常的除以2运算效率要高。但是检索需要的时间是O（n）.

添加：

    public void add(int index, E element) {        addBefore(element, (index==size ? header : entry(index)));    }    private Entry<E> addBefore(E e, Entry<E> entry) {Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);newEntry.previous.next = newEntry;newEntry.next.previous = newEntry;size++;modCount++;return newEntry;    }    private Entry<E> entry(int index) {        if (index < 0 || index >= size)            throw new IndexOutOfBoundsException("Index: "+index+                                                ", Size: "+size);        Entry<E> e = header;        if (index < (size >> 1)) {            for (int i = 0; i <= index; i++)                e = e.next;        } else {            for (int i = size; i > index; i--)                e = e.previous;        }        return e;    }

?

添加的时间复杂度是O（n).

删除：

    public boolean remove(Object o) {        if (o==null) {            for (Entry<E> e = header.next; e != header; e = e.next) {                if (e.element==null) {                    remove(e);                    return true;                }            }        } else {            for (Entry<E> e = header.next; e != header; e = e.next) {                if (o.equals(e.element)) {                    remove(e);                    return true;                }            }        }        return false;    }

?

这里是根据value是不是null来分别区分，如果为null，就删除第一个为null的。如果不为null删除第一个相同（用equal是判断）的元素。