Java ArrayList與LinkedList使用方法詳解

Posted on by

前言

最近參加瞭21天打卡活動，希望可以讓自己養成寫博客的習慣…

ArrayList和LinkedList

ArrayList和LinkedList都是常用的List類型，兩者都繼承瞭AbstratctList，並實現List接口。

List的方法

列舉一些常見的方法，ArrayList和LinkedList會實現List裡面的方法

方法 描述
boolean isEmpty() 判斷當前列表是否為空
boolean contains(Object o) 是否包含這個元素
T[] toArray(T[] a)  
boolean add(E e) 添加一個元素
boolean remove(Object o) 移除
boolean containsAll(Collection<?> c)  
void add(int index, E element) 在固定位置添加元素
int indexOf(Object o) 定位元素
ListIterator listIterator() 遍歷列表

上述的方法都是List的常用方法，相信大傢都非常的熟悉。

ArrayList

ArrayList是實現List接口的可擴容數組（動態數組），它的內部是基於數組實現的，數組這個結構具有的特點

隨機存取：隨機存取就是可以通過索引直接訪問列表的元素

可以實現動態擴容，下面我們來看一下它的源碼實現

屬性 描述
size 列表的元素個數
DEFAULT_CAPACITY 創建一個空對象時的默認大小

我們來看一下ArrayList是怎麼實現動態擴容的。

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

如果當容量比初始容量大時，新的容量相當於是原來的1.5倍這裡

add

ArrayList重載瞭List的add方法，這裡面重寫的方法有直接添加，和在某一個位置添加一個元素，這裡就可以看出ArrayList的底層是由數組實現的瞭

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    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++;
    }

這裡采用的是System.arraycopy來進行數組的拷貝，屬於深度拷貝，效率很高。

remove

這裡的移除也是有直接移除某個索引下的數據，但是這裡面有兩個不同的方式移除數據，一個是remove，一個是fastRemove兩種方式移除元素，remove和fastRemove不同的是一個是需要返回刪除的元素，一個是不返回的。

LinkedList

LinkedList是基於雙向鏈表來實現的，是屬於鏈式存儲，隻能順序存取元素，不能隨機存取。

LinkedList的結點結構，包括指向下一個結點的指針next和指向上一個結點的指針prev

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

屬性包括

名稱 描述
size 元素個數
first 頭節點
last 尾節點

remove

移除頭節點，需要更新size大小和把刪除的節點為NULL，裡面還有removeRange方法，可以把從fromIndex到toIndex的全部節點釋放掉

 public E remove() {
        return removeFirst();
 }
 private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

get和peek

下面可以來看看LinkedList的訪問元素的形式，前面說瞭這個結構是隻能順序遍歷的，不能隨機進行訪問，需要遍歷整個列表，但是我們使用的是雙向鏈表，由於我們維護瞭頭節點和尾節點，當需要訪問元素時，如果根據的是下標（這裡的下標不是數組的下標），先判斷和頭節點近還是和尾節點近，然後再進行順序遍歷。

peek方法是訪問頭節點。

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

push

向列表中添加元素，我們可以采用offerFirst和offerLast往列表頭部添加元素或者往尾部添加元素，push方法調用的是addFrist方法，采用的是頭插法，刪除也是才有刪除頭部元素；

ArrayList和LinkedList的使用場景和區別

前面也提到兩者的存取結構是不同的，一個是用數組來操作，一個采用的是雙向鏈表，一般ArrayList用在訪問更加多的情況下，由於插入會相對較慢，但是LinkedList采用的是順序訪問，在插入和刪除較多的場景會更加適用。

到此這篇關於Java ArrayList與LinkedList使用方法詳解的文章就介紹到這瞭,更多相關Java ArrayList與LinkedList內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：