今天我們說一下 LinkedList ,在列表的使用中,我們很多時候會糾結(jié)于列表的選擇,是選擇數(shù)組實現(xiàn)的 ArrayList 還是選擇鏈表實現(xiàn)的 LinkedList.

屬性

列表的基本屬性有三個,和 ArrayList 類似,第一個屬性是:

列表大小

用來表示列表存儲的元素個數(shù),
鏈表的擴(kuò)容非常自由,所以它的初始化容量是0

    transient int size = 0;

兩個數(shù)據(jù)元素

LinkedList 是一個雙向鏈表,所以它有兩個重要元素,就是頭和尾.

    transient Node<E> first;
    transient Node<E> last;

其中我們有一個 Node 對象.
這是一個很常見的對象,它有著元素內(nèi)容,前后的元素的引用.

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

調(diào)整鏈表

LinkedList 提供幾個內(nèi)部的調(diào)整方法,比如:在最前面新增,在最后新增,在某個元素前面新增,移除最前面的,移除最后面的,移除某個元素.
這些操作基本上是對于鏈表中點的引用的調(diào)整,來實現(xiàn)這些個方法的.具體的不詳細(xì)贅述.

返回某個元素

我們都知道列表相對于數(shù)組最方便的地方在于新增元素,因為我們只需要將點連接到后面就可以了.而不需要考慮在新增一個元素的時候去檢查數(shù)組長度.

但是相對于這一點來說,鏈表也有不方便的一點,就是去獲取某個特定的元素:

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

在 這里我們看到了,當(dāng)我們需要獲取第 n 個元素的時候,鏈表需要先檢查我們的第 n 個元素是舉例頭和尾哪個點更近一些,之后再從頭或尾開始計算,一個一個去遍歷,直到到達(dá)我們所需要的點為止.
所以這個操作要消耗很多的行為,所以當(dāng)數(shù)據(jù)量很大的時候,這種尋找一個點的方式就會變得很慢.
當(dāng)然,這種慢是僅限于在取出的點距離頭尾相對較遠(yuǎn)的情況,如果取出的點是距離頭尾很近的情況下,這種速度的影響其實微乎其微.

ArrayList 和 LinkedList 的差異

所以我們根據(jù)上面可以得到結(jié)論:

• 當(dāng)對于數(shù)據(jù)列表只是單純的存儲的情況下, LinkedList 的效率要更高一些,因為它避免了在新增一個元素的時候為了考慮擴(kuò)容的情況所消耗的成本.
• 當(dāng)對于數(shù)據(jù)列表需要頻繁取值的情況下, ArrayList 的效率要更高一點,因為數(shù)組在查詢某個元素的情況下是可以直接定位到對應(yīng)的元素位置.

所以我們可以看出,在使用列表的時候,列表的選擇其實對于我們的運行效率產(chǎn)生了相當(dāng)?shù)挠绊?

關(guān)于 LinkedList 我們就研究到這里,之后我們有機(jī)會會繼續(xù)研究其它的集合類.

歡迎關(guān)注我的博客: 既然來了就坐坐吧
小站剛開始起步,歡迎您的駕到.