Java基礎之集合（一）

目錄

1.1 List

1.1.1 ArrayList

1.1.2 Vector

1.1.3 LinkedList

1.1 List

List是常用的資料類型，是一種有序的集合

1.1.1 ArrayList

底層由數組實作

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

當數組長度不能滿足存儲要求時，ArrayList會建立一個更大的數組并将數組中已有的資料複制到新數組中

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }
           

提供了add()、remove()、get()、size()等功能

ArrayList list = new ArrayList();
        list.add("1"); //添加元素
        list.add("4");
        list.add("2");
        list.add("3");
        list.add("1");
        System.out.println(list);

        list.remove(3); //移除第i+1位元素
        System.out.println(list);
        list.size(); //獲得大小

        Object o = list.get(2);//獲得第i+1位元素的值
        System.out.println(o);
           

[1, 4, 2, 3, 1]
[1, 4, 2, 1]
2
           

從以上輸出結果可以得知ArrayList的元素必須連續存儲，是以當需要在某一特定位置插入或删除元素時，需要将待插入（删除）的節點後所有元素向後移動，修改代價高，并不适合随機插入或删除操作，更适合随機查找和周遊。

同時我們檢視ArrayList的源碼

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
           

發現，他并不是線程安全的。

綜上所述：ArrayList底層由數組實作，實作自動擴容，增删快，查詢慢，線程不安全

1.1.2 Vector

底層也是由數組實作

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

同ArrayList一樣同樣擁有add()、remove()、get()、size()等功能，擴容也同ArrayList一樣。

與ArrayList不同的是，他的方法中用了synchronized關鍵字修飾，例如

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
           

說明Vector是線程安全的，保證了多線程下資料的一緻性，但由于需要頻繁地對Vector執行個體進行加鎖和釋放鎖，是以Vector的讀寫效率整體上比ArrayList效率低。      

綜上所述，Vector和ArrayList一樣底層由數組實作，自動擴容，增删慢，查詢快，不一樣的是Vector線程安全。

1.1.3 LinkedList

底層由雙向連結清單實作，雙向連結清單的每個節點用内部類Node表示。LinkedList通過first和last引用分别指向連結清單的第一個和最後一個元素。

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;
}
           

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

增删采用add（）、remove（）方法

LinkedList list = new LinkedList();
        list.add("5");
        list.add("4");
        list.add("3");
        System.out.println(list);
        list.add(0,"1");
        System.out.println(list);
        list.remove("1");
        System.out.println(list);
        list.remove(1);
        System.out.println(list);
           

[5, 4, 3]
[1, 5, 4, 3]
[5, 4, 3]
[5, 3]
           

通過上述代碼以及結果可見，在對LinkedList進行插入和删除時，資料改動小，是以随機插入和删除的效率高。

LinkedList 底層基于連結清單結構，無法向 ArrayList 那樣随機通路指定位置的元素。LinkedList 查找過程需要從連結清單頭結點（或尾節點）向後查找

public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
}

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
           

上述代碼通過周遊的方式定位目标節點的位置，通過比較index與size/2決定從頭節點開始還是從尾結點開始。是以随機通路速度慢。

同時LinkedList提供了List中未定義的方法，用于操作連結清單頭部和尾部，有可能被當作堆棧和對列使用

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
}

public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
}
           

綜上所述LinkedList由雙向連結清單實作，增删快，查詢慢，線程不安全