边读边写【1】 ----java 集合包之深入List

一、java 集合包最常用的的2个接口Collection /和Map
List接口
最常用的有ArrayList ,LinkedList, Vector,Stack
ArrayList 的实现如下：

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

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
	this(10);
    }

可以看出它是通过数组来操作的，那么他的增删查都是通过数组方法的来实现：

 /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
	ensureCapacity(size + 1);  // Increments modCount!!
	elementData[size++] = e;
	return true;
    }

删除要复杂点：

 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 work

	return oldValue;
    }

将index 后面的对象当成一个数组，移动到index位置，然后将最后的一个给null.

get 最简单直接按数组下标找。

总结：
ArrayList 是一个基于数组实现的非线性安全的不限制容量的容器。在增加的时候要扩容，删除的时候却不减少容量


LinkedList：这是一个很有意思的双向链表
初始化的时候首先要new 一个 内部的entry 对象 。这个 对象代表一个元素

private static class Entry<E> {
	E element;  //当前元素
	Entry<E> next; //下一个
	Entry<E> previous; //前一个

	Entry(E element, Entry<E> next, Entry<E> previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }
 private transient Entry<E> header = new Entry<E>(null, null, null);
    private transient int size = 0;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
        header.next = header.previous = header; //都指给自己
    }

增加元素的时候 首先要创建一个 newEntry  将newEntry 前一个元素的next指给自己，将自己的next 的元素的previous 指向自己。 通俗点说，有2个位置，新来的坐后面，对面的人说，我是你的下一个，对将要来的第3个人说，我是你的前一个。

  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;
    }

删除元素的时候  就告诉你前面的说我走了，你的后面的将是我的后面的。告诉你的后面，你的前面的将是我的前面的。我自己的都为空，你们再也找不到我了。3人行变成2人行。

 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;
    }

 private E remove(Entry<E> e) {
	if (e == header)
	    throw new NoSuchElementException();

        E result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
	size--;
	modCount++;
        return result;
    }

在LinkedList 里面 查找是意见比较麻烦的事情，因为没有直接的索引，得一个一个去询问，jdk里面给的方法是：如果index >size/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;
    }

LinkedList 总结: 他是一个非线性安全的基于双向链表实现的容易。元素相互之间都非常熟悉。

Vector
Vector 其实跟ArrayList 的实现方式基本相同，但是他的方法前面都加了 synchronized.还有一点区别就是他的扩容策略跟ArrayList不一样。

  private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
//如果容量不足，将原来的容量*2  
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
            elementData = Arrays.copyOf(elementData, newCapacity);
	}
    }

Vector 总结： 他是一个线程安全的ArrayList 。

Stack

Stack 继承自Vector  push 操作就是vector 的addElement  peek 获得最后一个元素。pop 调用peek 同时删除最后一个元素。