java 集合LinkedList與ArrayList源碼分析

一、LinkedList

1、結構，廢話不多說吧，直接看條件應該就大概懂了。

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;

主要有三個元素，容量，第一節點，最後節點。每一個node中又包含了前節點跟下一個節點。這個node的構造器很重要，第一個參數是prev節點我個人就叫他前置節點，next我就叫他後置節點。雙向連結清單由此展現。

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

2、新增

public boolean add(E e) {
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        final Node<E> l = last;
        //上面node的構造器，重複一遍參數，前置節點，元素，後置節點。
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

首先擷取最後一個節點，然後在最後節點上新增節點，判斷最後節點是否為空，如果為空設定為第一節點，不為空增加到最後節點後面稱為最後節點。size加1，更改次數加1。是以說預設的就是加到末尾。

2.1在指定下标進行新增

public void add(int index, E element) {
 	//檢查是否越界等等不截圖了很簡單
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
	//如果新增index 與size相等 就直接加到後面
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    //succ為之前下标元素，擷取之前下标元素的前置節點pred。
    //然後通過構造器建立pred為前置節點，succ(之前下标對應元素)為後置節點的新node。
    //把新node設定為succ的前置節點pred的後置節點。
        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++;
    }

3、删除，先判斷删除下标是否越界很簡單的就不截圖了，擷取要删除的元素節點，

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

//擷取要的元素 這個地方get也會用到
    Node<E> node(int index) {
        // assert isElementIndex(index);
		//與size一半進行比較 
		//雖然取了一半但是還有大大的for循環
        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;
        }
    }

移除元素，擷取此元素的pre節點跟next節點。判斷pre節點是否為空，為空next節點設定為第一節點，否則此節點的next節點設定為pre節點的next節點。判斷next節點是否為空，為空pre節點設定為最後節點，否則pre節點設定為next節點的pre節點。

E unlink(Node<E> x) {
        // assert x != null;
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

4、擷取制定下标元素

public E get(int index) {
  	//同樣的先校驗
        checkElementIndex(index);
        //上面删除指點元素有哈
        return node(index).item;
    }

二、ArrayList

1、結構是一個Object數組

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        //Object 數組麼這不是
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        //喲這個也是長度為空的數組
        //private static final Object[] EMPTY_ELEMENTDATA = {}
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

2、新增

public boolean add(E e) {
    	//數組長度跟新增之後長度進行比較
    	//size+1 就是後面minCapacity 可以先有個印象
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //如果初始長度滿足新增
        elementData[size++] = e;
        return true;
    }

首先咱們先看下，這個方法在指定下标新增也會用到喲。

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    //我直接把calculateCapacity方法粘過來
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
	//進行比較看看是不是預設的預設的就是10
	// private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
         //private static final int DEFAULT_CAPACITY = 10;
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

	
    private void ensureExplicitCapacity(int minCapacity) {
    //更改次數自增，不重要忽略~
        modCount++;

        // overflow-conscious code
        //數組長度跟新增之後長度進行比較
        if (minCapacity - elementData.length > 0)
        //
            grow(minCapacity);
    }

//擴容集合長度
	//minCapacity 為更新之後長度
    private void grow(int minCapacity) {
        // overflow-conscious code
        //擷取原來集合的長度
        int oldCapacity = elementData.length;
        //新長度為原來長度的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
 //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
        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);
    }
        private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

應該是很簡單吧看着，最後回到數組下标指派。

public boolean add(E e) {
    	//數組長度跟新增之後長度進行比較
    	//size+1 就是後面minCapacity 可以先有個印象
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //如果初始長度滿足新增
        elementData[size++] = e;
        return true;
    }

2.1 在指定下标新增

public void add(int index, E element) {
        rangeCheckForAdd(index);
		//似曾相識 就是上面的那個
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //好了這個 System 已經說明一切了
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
      /*
        從指定的源數組複制數組，從指定位置，到目标數組的指定位置。
        從源中複制陣列元件的子序列由<code>src</code>引用到目标數組的數組由<code>dest</code>引用。
        複制的元件數為等于<code>長度</code>參數。
        元件位于位置<code>srcPos</code>到将源數組中的<code>srcPos+length-1</code>
        複制到位置<code>destPos</code>到目的地的<code>destPos+length-1數組。
        */
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

3、指定下标删除

public E remove(int index) {
    //同樣的先校驗
        rangeCheck(index);

        modCount++;
        //直接把下面的方法粘貼過來
        /*   
         E elementData(int index) {
        return (E) elementData[index]; }
        */
        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;
    }

4、擷取指點下标元素

public E get(int index) {
        rangeCheck(index);
 		/*   也是直接粘貼過來
         E elementData(int index) {
        return (E) elementData[index]; }
        */
        return elementData(index);
    }

list 小總結：

1、LinkedList

沒有容量的限制，采用的雙向連結清單的方式。
新增隻需要建構新node，更新原來下标元素前置節點的後置節點，跟原來下标元素的前置節點。其實新增節點，更改引用。是以說會快一點。
删除隻需要更改原來下标元素前置節點的next，跟原來下标元素後置節點的pre。其實就是更改引用。是以說會快一點。
擷取元素需要先取size的一半然後進行周遊。

2、ArrayList

會有容量擴容的機制，采用的Object數組的方式。
新增要判斷數組是否需要擴容，然後調用System的方法進行對資料遷移。
删除調用System的方法進行對資料遷移。
直接通過數組下标進行擷取。

java 集合LinkedList與ArrayList源碼分析

一、LinkedList

二、ArrayList

list 小總結：

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method