Java中的List


List

ArrayList

通过动态数组存储数据的,数组默认长度为10,实际使用过程中可以通过trimToSize()方法剪裁到实际的list大小。

ArrayList是线程不安全的;

ArrayList由于通过数组索引定位,所以查找效率比较高,但是插入和删除操作需要移动数组元素,因此插入和删除效率比较低;

当数组元素增加的时候,会增加原来尺寸的一半进行扩容;如果还不满足,则直接用原来的长度加上添加元素的长度作为最终的长度。

实现了RandomAccess接口,可以随机访问;

无参构造函数new出来的ArrayList数组默认长度为10,在明确元素个数的时候可以指定数组长度;

操作的关键在于对数组的控制,比如扩容,复制等等。

扩容关键代码

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

查找关键代码

public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

插入关键代码

public void 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++;
    }

LinkedList

基于链表实现的,LinkedList中持有一个size,一个头结点,一个尾结点。

每个结点包括结点值,指向前一个结点的引用,指向后一个结点的引用:

private static class 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是线程不安全的;

实现了Deque,可以用做双向队列。

插入/删除效率比较高,但是查询效率比ArrayList低。

操作的关键在于对链表的操作,比如新增,删除,查找,遍历等。

插入关键代码

public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

        /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

查找关键代码

public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

Vector

基于数组实现的List,可以扩容和裁剪。

Vector是线程安全的。

默认长度为10。

扩容方式与ArrayList不同,Vector中在构造函数里可以传入一个增量扩容大小capacityIncrement,如果不指定则默认为0;当扩容的时候,先判断这个增量扩容大小capacityIncrement,如果capacityIncrement大于0,则容量增加capacityIncrement,否则容量翻倍。

查询效率高,插入,删除效率低,由于是同步操作,比ArrayList性能低。

扩容关键代码

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

插入关键代码

public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

查找关键代码

public synchronized int indexOf(Object o, int index) {
        if (o == null) {
            for (int i = index ; i < elementCount ; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = index ; i < elementCount ; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

Stack

继承自Vector,新增了pop/push操作。

继承Vector的特性。

pop/push操作关键代码

public E push(E item) {
        addElement(item);

        return item;
    }

public synchronized E pop() {
        E       obj;
        int     len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

CopyOnWriteArrayList

基于数组实现,并利用ReentrantLock实现同步机制,保证线程安全。

然后利用了写时复制的思想,在修改的时候首先复制一个副本,在副本上进行修改,最后将引用设置到副本上。

插入关键代码

public void add(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            if (index > len || index < 0)
                throw new IndexOutOfBoundsException("Index: "+index+
                                                    ", Size: "+len);
            Object[] newElements;
            int numMoved = len - index;
            if (numMoved == 0)
                newElements = Arrays.copyOf(elements, len + 1);
            else {
                newElements = new Object[len + 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index, newElements, index + 1,
                                 numMoved);
            }
            newElements[index] = element;
            setArray(newElements);
        } finally {
            lock.unlock();
        }
    }

查找关键代码

private static int indexOf(Object o, Object[] elements,
                               int index, int fence) {
        if (o == null) {
            for (int i = index; i < fence; i++)
                if (elements[i] == null)
                    return i;
        } else {
            for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;
        }
        return -1;
    }

文章作者: 姜康
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 姜康 !
评论
 上一篇
Java中的Map Java中的Map
哈希表/散列表 通俗的说就是,使用散列函数将key值映射到数组下标,这样就可以根据key值直接访问到元素存储位置,这种结构就叫哈希表(散列表)。 将key值映射到数组下标的函数就做散列函数,这个映射过程是一个key值压缩的过程,因而不可避
2020-05-15
下一篇 
Java队列 Java队列
先来看一下Queue的定义: public interface Queue<E> extends Collection<E> { //插入成功返回true,如果容量不足,抛出异常 boolean add(
2020-05-15
  目录