Java深入篇~04.List資料結構的實作(JDK1.8)

上一篇文章

前言

通常程式總是根據運行之后才知道的某些條件去創建物件，在此之前并不知道所需物件的數量,甚至也不知道物件的型別，為了解決這個問題,則需要在任意時刻任意位置來創建這個所需要的物件，這樣一來,陣列是肯定行不通的，因為陣列的尺寸是固定的不可改變的，所以在大多數編程語言里面都會提供某種方法來解決，比如C++有STL,而Java則有一套容器類，

C++ STL容器

在集合類的基本型別里,分別有List,Set,Map,Queue，容器提供了相當完善的方法來保存物件,我們可以用它們來解決很多的問題，

List

List可以將元素維護在特定的序列中,List介面在Collection的基礎上添加了大量的方法，使得可以在List中間插入和移除元素，

本人過去也寫過和List資料結構相關的博客，歡迎大家可以點進去看~嘿嘿

線性表的基本實作和概念

順序表的操作

雙鏈表的操作

堆疊和佇列的基本概念

順序堆疊和鏈堆疊

使用自定義的堆疊來優化二叉樹的遍歷

List的型別

基本的順序存盤 : ArrayList，從名字就可以看出,這是一個陣列的List,底層實作的則是動態陣列,資料結構類似順序表，底層原理類似前面說過的StringBuilder,但也不太一樣，ArrayList的優點就是隨機訪問效率高，但是中間插入和洗掉則就有點慢了，在"順序表的操作"那篇博客里說過具體原因，

鏈式資料存盤:LinkedList，它的優點就是插入和洗掉的效率高,但是訪問中間任何一個元素都需要遍歷,所以隨機訪問效率不如ArrayList，在線性表的基本實作和概念里面有具體原因，

ArrayList

ArrayList底層是一個動態陣列,在初次new它的時候,會構建一個大小為10的空串列，

	public Arst() {
	        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	    }

當ArrayList的陣列容量不夠用的時候,則會對陣列的長度進行擴容，和StringBuilder不同的是,StringBuilder每次擴容的量是當前長度的一倍+2，而ArrayList則是擴容當前長度的0.5倍，所以,在資源上,ArrayList每次多出的容量會比StringBuilder小，ArrayList的構造方法還可以手動設定初始大小，如果用戶在使用ArrayList之前就已經知道最少要存盤多少資料,則可以將初始長度設定到最小值,這樣可以減少擴容的次數,進一步微妙的提升效率，

	private void grow(int minCapacity) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

add方法

ArrayList的add方法既可以直接在尾部添加元素,也可以根據索引來添加元素，其程序則是先判斷容量是否夠用,不夠用則擴容,夠用則直接在陣列的索引位置后面的一個位置添加進去，ArrayList和StringBuilder一樣,陣列的長度并不等于容器的長度，當要根據索引來添加元素的時候,可能有人會想到回圈,這樣做也可以，但是為了效率則可以使用System.arraycopy在指定的位置騰出一個空間來存盤需要存盤的值，

尾部插入

	public boolean add(E e) {
	        ensureCapacityInternal(size + 1);
	        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++;
	    }

remove方法

remove方法既可以根據索引來洗掉元素,也可以根據物件來洗掉元素，當使用索引洗掉元素的時候則會將索引后面的元素向左移動覆寫掉它，而當根據物件洗掉元素的時候,它則會洗掉第一個和那個物件相同的元素，也就是說,假如我要洗掉元素'A'，即使這個容器里有多個'A',但最終也只會洗掉第一個,其作業原理則是利用回圈找到索引,然后再采用索引洗掉的方案，因此效率上,物件洗掉要低于索引洗掉，

索引洗掉

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

物件洗掉

	public boolean remove(Object o) {
	        if (o == null) {
	            for (int index = 0; index < size; index++)
	                if (elementData[index] == null) {
	                    fastRemove(index);
	                    return true;
	                }
	        } else {
	            for (int index = 0; index < size; index++)
	                if (o.equals(elementData[index])) {
	                    fastRemove(index);
	                    return true;
	                }
	        }
	        return false;
	    }

get方法

ArrayList的get方法就沒什么好說的了,因為ArrayList底層是陣列,只要索引合法,直接回傳陣列即可，

	E elementData(int index) {
	        return (E) elementData[index];
	    }

indexOf方法

這個方法主要就是使用回圈進行遍歷然后對比,根據物件找到第一個索引

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

LinkedList

LinkedList則是鏈式存盤結果,其底層采用的是雙向鏈表，鏈表的結點可以散落在記憶體中的任意位置,且不需要一次性劃分所有結點所需的空間給鏈表,而是根據需求臨時劃分，因此,鏈表支持存盤空間的動態分配，我在"線性表的基本概念"那篇博客有介紹，因此初次new一個LinkedList物件的時候,和ArrayList不同，初次new物件的時候LinkedList是個空的，

add方法

和ArrayList一樣，add方法既可以直接在尾部添加元素,也可以根據索引來添加元素，根據索引添加元素的時候,不再像陣列一樣需要找到索引然后去騰出一個位置,而是直接改變指標的指向即可，可能對于學過C語言的人來說會更加容易理解一點，當索引添加的時候,索引的位置剛好是最后一個,則會呼叫尾部添加的方案，如果不是，則找到那個索引的前一個位置,加入到前一個位置的后一個位置即可，

尾部添加

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

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

索引添加

	public void add(int index, E element) {
	        checkPositionIndex(index);
	
	        if (index == size)
	            linkLast(element);
	        else
	            linkBefore(element, node(index));
	    }

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

remove方法

在LinkedList中remove會有一個無引數的方案,那個方案則是直接洗掉頭一個元素，由于鏈表洗掉的原理是將元素的前一個的指標指向元素后一個指標,(我在單鏈表的操作中提到過)然后夾在中間的則被釋放掉實作，可當我要洗掉頭元素的時候,無法做到這種操作所以Java中則會采取另一種解決方案，至于物件洗掉元素,則也是先回圈找到索引,再采取索引洗掉元素的解決方案，

洗掉頭元素

	private E unlinkFirst(Node<E> f) {
	        final E element = f.item;
	        final Node<E> next = f.next;
	        f.item = null;
	        f.next = null; 
	        first = next;
	        if (next == null)
	            last = null;
	        else
	            next.prev = null;
	        size--;
	        modCount++;
	        return element;
	    }

索引洗掉元素

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

物件洗掉元素

	public boolean remove(Object o) {
	        if (o == null) {
	            for (Node<E> x = first; x != null; x = x.next) {
	                if (x.item == null) {
	                    unlink(x);
	                    return true;
	                }
	            }
	        } else {
	            for (Node<E> x = first; x != null; x = x.next) {
	                if (o.equals(x.item)) {
	                    unlink(x);
	                    return true;
	                }
	            }
	        }
	        return false;
	    }

get方法

鏈表的優點就是在添加和洗掉的時候,不需要遍歷只需要改變指標的指向就可以實作，但是缺點就是如果我要隨機訪問一個元素,就必須要回圈遍歷了，在這方面效率要低于ArrayList

	Node<E> node(int 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;
	        }
	    }

Stack

Stack則是繼承了Vector，而Vector也是List介面下的一個實作類,其原理和ArrayList差不多都是動態陣列，區別就在于Vector的執行緒比較同步,而ArrayList則不同步，因此Vector屬于執行緒安全但效率低,而ArrayList執行緒不安全但效率高，在使用上Vector幾乎不用，

Stack也就是堆疊，堆疊是一種只能在一端進行插入或洗掉的線性表，其中,允許插入或洗掉的一端為堆疊頂(TOP)，堆疊頂由一個稱為堆疊頂指標的位置指示器來指示，它是動態變化的，表的另一端為堆疊底,堆疊底固定不變，堆疊的插入和洗掉操作一般稱為入堆疊和出堆疊，由堆疊的定義可以看出,堆疊的主要特點就是先進后出，

在過去資料結構的學習當中就曾多次使用過堆疊，當我需要二叉樹遍歷的時候,使用堆疊遍歷二叉樹會比遞回效率好得多，當我需要實作鏈表反轉的時候,堆疊的先進后出特性可以得到非常簡便的效果，

事實上,堆疊其實就是受限制的線性表，以下三篇文章則是堆疊的基本概念和實作,這里就不重復了，

堆疊和佇列的基本概念

順序堆疊和鏈堆疊

使用自定義的堆疊來優化二叉樹的遍歷