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

边读边写【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 workreturn 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 同时删除最后一个元素。



   

查看更多 下一篇