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

屬性

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

列表大小

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

    transient int size = 0;

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

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

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

其中我們有一個(gè) Node 對(duì)象.
這是一個(gè)很常見的對(duì)象,它有著元素內(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 提供幾個(gè)內(nèi)部的調(diào)整方法,比如:在最前面新增,在最后新增,在某個(gè)元素前面新增,移除最前面的,移除最后面的,移除某個(gè)元素.
這些操作基本上是對(duì)于鏈表中點(diǎn)的引用的調(diào)整,來實(shí)現(xiàn)這些個(gè)方法的.具體的不詳細(xì)贅述.

返回某個(gè)元素

我們都知道列表相對(duì)于數(shù)組最方便的地方在于新增元素,因?yàn)槲覀冎恍枰獙Ⅻc(diǎn)連接到后面就可以了.而不需要考慮在新增一個(gè)元素的時(shí)候去檢查數(shù)組長(zhǎng)度.

但是相對(duì)于這一點(diǎn)來說,鏈表也有不方便的一點(diǎn),就是去獲取某個(gè)特定的元素:

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

ArrayList 和 LinkedList 的差異

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

• 當(dāng)對(duì)于數(shù)據(jù)列表只是單純的存儲(chǔ)的情況下, LinkedList 的效率要更高一些,因?yàn)樗苊饬嗽谛略鲆粋€(gè)元素的時(shí)候?yàn)榱丝紤]擴(kuò)容的情況所消耗的成本.
• 當(dāng)對(duì)于數(shù)據(jù)列表需要頻繁取值的情況下, ArrayList 的效率要更高一點(diǎn),因?yàn)閿?shù)組在查詢某個(gè)元素的情況下是可以直接定位到對(duì)應(yīng)的元素位置.

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

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

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