浅谈JAVA容器之list

1、  list

          1、ArrayList

 

publicclass ArrayList<E> extends AbstractList<E>

        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

 

AbstractList继承了AbstractCollection类实现了List类

AbstractCollection又实现了Collection类。List也是继承了Collection。

ArrayList存储的形式是一个数组，读取时可以按下标读取。插入的时候是把要插入的数据放到对应的位置，在把之前此位置之后的所有数据重新拷贝到，插入数据之后。

publicvoid add(int index, E element) {

        rangeCheckForAdd(index);

 

        ensureCapacityInternal(size + 1);  // Increments modCount!!

        System.arraycopy(elementData, index, elementData, index + 1,

                         size - index);

        elementData[index] = element;

        size++;

    }

 

A、set(int index, E element)方法与add(int index, E element)

 

set(int index, E element)就是将 index位替换为element。

 

add(int index, E element)与set方法不同的是，add是先将index位移到size+1位，然后再将element放到index位。

 

 

        public E set(int index, E e) {

            rangeCheck(index);

            checkForComodification();

            E oldValue = ArrayList.this.elementData(offset + index);

            ArrayList.this.elementData[offset + index] = e;

            return oldValue;

        }

 

B、remove(int index),remove(Object o)与 removeRange(int fromIndex, int toIndex)

remove(int index)移除第index位，index+1位开始向前移动一位，然后将size位置为null

remove(Object o)通过比较移除O对象，index+1位开始向前移动一位，然后将size位置为null

removeRange(int fromIndex, int toIndex)移除从fromIndex位到toIndex位的对象

    public E remove(int index) {

        rangeCheck(index);

 

        modCount++;

        E oldValue = elementData(index);

 

        int numMoved = size - index - 1;

        if (numMoved > 0)

            System.arraycopy(elementData, index+1, elementData, index,

                             numMoved);

        elementData[--size] = null; // clear to let GC do its work

 

        return oldValue;

    }

 

    publicboolean remove(Object o) {

        if (o == null) {

            for (int index = 0; index < size; index++)

                if (elementData[index] == null) {

                    fastRemove(index);

                    returntrue;

                }

        } else {

            for (int index = 0; index < size; index++)

                if (o.equals(elementData[index])) {

                    fastRemove(index);

                    returntrue;

                }

        }

        returnfalse;

    }

    protectedvoid removeRange(int fromIndex, int toIndex) {

        modCount++;

        int numMoved = size - toIndex;

        System.arraycopy(elementData, toIndex, elementData, fromIndex,

                         numMoved);

 

        // clear to let GC do its work

        int newSize = size - (toIndex-fromIndex);

        for (int i = newSize; i < size; i++) {

            elementData[i] = null;

        }

        size = newSize;

    }

 

C、addAll(Collection c)与addAll(int index,Collection c)

addAll(Collection c)直接从最后位置添加对象

addAll(int index,Collection c)先将原index位及以后的所有位添加到index+c.size以后的位置。再将c放到从index位往后放。相当于在将c对象从index位开始插入，原数据依次往后推。

publicboolean addAll(Collection<? extends E> c) {

        Object[] a = c.toArray();

        int numNew = a.length;

        ensureCapacityInternal(size + numNew);  // Increments modCount

        System.arraycopy(a, 0, elementData, size, numNew);

        size += numNew;

        return numNew != 0;

    }

publicboolean addAll(int index, Collection<? extends E> c) {

        rangeCheckForAdd(index);

 

        Object[] a = c.toArray();

        int numNew = a.length;

        ensureCapacityInternal(size + numNew);  // Increments modCount

 

        int numMoved = size - index;

        if (numMoved > 0)

            System.arraycopy(elementData, index, elementData, index + numNew,

                             numMoved);

 

        System.arraycopy(a, 0, elementData, index, numNew);

        size += numNew;

        return numNew != 0;

    }

A、 D、removeAll(Collection<?> c)与retainAll(Collection<?> c)

Are       moveAll删除c，retainAll保留c

 

publicboolean removeAll(Collection<?> c) {

        return batchRemove(c, false);

    }

publicboolean retainAll(Collection<?> c) {

        return batchRemove(c, true);

    }

privateboolean batchRemove(Collection<?> c, boolean complement) {

        final Object[] elementData = this.elementData;

        int r = 0, w = 0;

        boolean modified = false;

        try {

            for (; r < size; r++)

if (c.contains(elementData[r]) == complement)

                    elementData[w++] = elementData[r];

        } finally {

            // Preserve behavioral compatibility with AbstractCollection,

            // even if c.contains() throws.

            if (r != size) {

                System.arraycopy(elementData, r,

                                 elementData, w,

                                 size - r);

                w += size - r;

            }

            if (w != size) {

                // clear to let GC do its work

                for (int i = w; i < size; i++)

                    elementData[i] = null;

                modCount += size - w;

                size = w;

                modified = true;

            }

        }

        return modified;

    }

E、subList(int fromIndex, int toIndex)

此方法意思是取fromIndex位到toIndex位作为一个新的ArrayList。实际上原list没有变而是新建了一个内部类重写了Arraylist的方法，每个涉及到指定位置的地方都index都变成index+fromIndex

 

    public List<E> subList(int fromIndex, int toIndex) {

        subListRangeCheck(fromIndex, toIndex, size);

        returnnew SubList(this, 0, fromIndex, toIndex);

    }

 SubList部分代码：

privateclass SubList extends AbstractList<E> implements RandomAccess {

        privatefinal AbstractList<E> parent;

        privatefinalintparentOffset;

        privatefinalintoffset;

        intsize;

 

        SubList(AbstractList<E> parent,

                int offset, int fromIndex, int toIndex) {

            this.parent = parent;

            this.parentOffset = fromIndex;

            this.offset = offset + fromIndex;

            this.size = toIndex - fromIndex;

            this.modCount = ArrayList.this.modCount;

        }

2、LinkedList

linkedlist存储单元形式是Node<E>，Node有三个属性：

E item;（当前存储内容）

               Node<E> next;（下一个节点内容）

Node<E> prev;（上一个节点内容）

每个节点都包括这三个属性，就构成了链表的形式。

所以linkedlist中的添加删除插入等方法都是通过改变每个Node节点的next和prev来实现的。

链头的prev是null，链尾的next同样也是null。

linkedList有三个属性size-长度，first-链头，last-链尾。First和last分别就是在链头和链为的Node<E>

privatestaticclass Node<E> {

        E item;

        Node<E> next;

        Node<E> prev;

 

        Node(Node<E> prev, E element, Node<E> next) {

            this.item = element;

            this.next = next;

            this.prev = prev;

        }

    }

LinkedList插入时只需要修改相应位置的prev和next就可以。然而ArrayList如果要进行插入操作，插入的时候是把要插入的数据放到对应的位置，在把之前此位置之后的所有数据重新拷贝到，插入的数据之后。由此可见LinkedList插入要比ArrayList快。然而ArrayList读取的时候很方便。可以直接找到位置，LinkedList读取需要循环的读。

3、Vector

继承AbstractList类，实现List接口。也是list的一个实现类。Vector存储的形式是一个Object数组

public Vector(int initialCapacity, int capacityIncrement) {

        super();

        if (initialCapacity < 0)

            thrownew IllegalArgumentException("Illegal Capacity: "+

                                               initialCapacity);

        this.elementData = new Object[initialCapacity];

        this.capacityIncrement = capacityIncrement;

    }

Vector的对外方法都用synchronized修饰，也就是说vector其实就是一个线程安全的ArrayList。

Stack：

Stack继承自Vector，是Vector的一个扩展类。此类扩展的比较简单，只扩展了push、pop、peek、search。

Push():就是调用Vector的addElement方法，就是在数组最后增加添加一个数据

public E push(E item) {

        addElement(item);

 

        return item;

    }

    publicsynchronizedvoid addElement(E obj) {

        modCount++;

        ensureCapacityHelper(elementCount + 1);

        elementData[elementCount++] = obj;

    }

pop()：是从数组最后删除一个数据

peek():是获取数组最后一个数据。

这几个增加、删除、获取的方法就是实现了堆栈的概念（先进后出）。

search(Object o)：就是循环比较，然后返回o在数组中的位置。

还有一个heap(堆)的概念heap与stack的异同点还没有具体研究。