成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Java容器類研究5：LinkedList

frank_fun / 2076人閱讀

摘要：提供了順序訪問(wèn)的方法，當(dāng)然，大部分方法都依賴于來(lái)實(shí)現(xiàn)，所以將鍋甩給了子類。實(shí)現(xiàn)了自己的遍歷方法利用了鏈表結(jié)構(gòu)的特性，進(jìn)行遍歷。其中有如下屬性記錄遍歷狀態(tài)。該方法位于中到數(shù)組中這里返回的不是，其實(shí)是

java.util.LinkedList

Java中有現(xiàn)成的隊(duì)列可以用嗎

有，就是LinkedList。LinkedList實(shí)現(xiàn)的接口如下，其實(shí)也可以當(dāng)做stack使用：

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

Deque是一個(gè)雙端隊(duì)列的接口，而Deque又繼承了接口Queue。所以LinkedList可以作為隊(duì)列、雙端隊(duì)列來(lái)使用。

AbstractSequentialList提供了順序訪問(wèn)的方法，當(dāng)然，大部分方法都依賴于ListIterator來(lái)實(shí)現(xiàn)，所以將鍋甩給了子類。

LinkedList用什么結(jié)構(gòu)來(lái)實(shí)現(xiàn)

同樣很簡(jiǎn)單，是一個(gè)Node的雙向鏈表結(jié)構(gòu)。

    private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

有屬性first和last記錄著鏈表的開(kāi)始和結(jié)束節(jié)點(diǎn)。

在鏈表中通過(guò)下標(biāo)取值是低效的

在LinkedList中，大量的方法需要先獲得指定下標(biāo)的節(jié)點(diǎn)，具體實(shí)現(xiàn)如下：

    Node node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

可以看出，開(kāi)發(fā)者已經(jīng)盡力優(yōu)化，根據(jù)index大小決定從何處開(kāi)始遍歷。

LinkedList實(shí)現(xiàn)了自己的ListIterator

遍歷方法利用了鏈表結(jié)構(gòu)的特性，進(jìn)行遍歷。其中有如下屬性記錄遍歷狀態(tài)。

    private Node lastReturned; //記錄最近一次返回的節(jié)點(diǎn)
    private Node next;    //記錄下一個(gè)要返回的節(jié)點(diǎn)
    private int nextIndex;   //記錄下一個(gè)要返回的位置
    private int expectedModCount = modCount;  //記錄期望的修改次數(shù)
LinkedList的Spliterator采用什么樣的分割策略

LinkedList每次劃分，不是采用的1/2策略，而是每次分裂出來(lái)的一塊數(shù)據(jù)都增加一個(gè)BATCH_UNIT(1024)的大小。比較有趣的是，每次分裂出來(lái)的Spliterator并不是LinkedList自己實(shí)現(xiàn)的Spliterator，而是一個(gè)ArraySpliterator，ArraySpliterator采用的是1/2的分裂策略。所以LinkedList每次分裂都想盡可能快的分裂出更多的元素，并且分裂過(guò)程中將鏈表結(jié)構(gòu)轉(zhuǎn)化為數(shù)組結(jié)構(gòu)，這樣做可能是出于性能的考慮，具體什么原因還是比較納悶的。

        //該方法位于class LLSpliterator中
        public Spliterator trySplit() {
            Node p;
            int s = getEst();
            if (s > 1 && (p = current) != null) {
                int n = batch + BATCH_UNIT;
                if (n > s)
                    n = s;
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
                //copy到數(shù)組中
                Object[] a = new Object[n];
                int j = 0;
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
                //這里返回的不是LLSpliterator，其實(shí)是ArraySpliterator
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/67799.html

相關(guān)文章

  • Java 基礎(chǔ) | Collection 集合概覽

    摘要：說(shuō)到復(fù)盤基礎(chǔ)，并不是所有的都會(huì)復(fù)盤，沒(méi)那個(gè)時(shí)間更沒(méi)那個(gè)必要。比如，一些基礎(chǔ)的語(yǔ)法以及條件語(yǔ)句，極度簡(jiǎn)單。思前想后，我覺(jué)得整個(gè)計(jì)劃應(yīng)該從集合開(kāi)始，而復(fù)盤的方式就是讀源碼。通常，隊(duì)列不允許隨機(jī)訪問(wèn)隊(duì)列中的元素。 ?showImg(https://segmentfault.com/img/remote/1460000020029737?w=1080&h=711); 老讀者都知道，我是自學(xué)轉(zhuǎn)行...

    codergarden 評(píng)論0 收藏0

  • Java容器類研究1：Collection

    摘要：集合類關(guān)系是和的父接口。相等必須是對(duì)稱的，約定只能和其它相等，亦然。和接口在中引入，這個(gè)單詞是和的合成，用來(lái)分割集合以給并行處理提供方便。這些并不立即執(zhí)行，而是等到最后一個(gè)函數(shù)，統(tǒng)一執(zhí)行。 集合類關(guān)系： Collection ├List │├LinkedList │├ArrayList │└Vector │　└Stack └Set Map ...

    AprilJ 評(píng)論0 收藏0

  • Java容器類研究6：Vector

    摘要：不同點(diǎn)是線程安全的，方法有關(guān)鍵字修飾。容量增長(zhǎng)策略默認(rèn)的增長(zhǎng)策略是每次在原容量的基礎(chǔ)上。的怎么做到線程安全的實(shí)現(xiàn)了自己的，為了保證并發(fā)線程安全的共享一個(gè)，開(kāi)發(fā)者在等方法中也加入了。與類繼承自，的實(shí)現(xiàn)不止一種方式，比如。 java.util.Vector Vector與ArrayList的異同 相同點(diǎn)：隨機(jī)存取，可通過(guò)位置序號(hào)直接獲取數(shù)據(jù)。都是通過(guò)一個(gè)數(shù)組來(lái)存放元素。 不同點(diǎn)：Vecto...

    Charles 評(píng)論0 收藏0

  • Java 持有對(duì)象（11）

    摘要：如果一個(gè)程序只包含固定數(shù)量且其生命周期都是已知的對(duì)象，那么這是一個(gè)非常簡(jiǎn)單的程序。 如果一個(gè)程序只包含固定數(shù)量且其生命周期都是已知的對(duì)象，那么這是一個(gè)非常簡(jiǎn)單的程序。 1.泛型和類型安全的容器 通過(guò)使用泛型，可以在編譯期防止將錯(cuò)誤類型的對(duì)象放置到容器中. 2.基本概念 Java容器類庫(kù)的用途是保存對(duì)象，并將其劃分為兩個(gè)不同的概念：Collection，Map. Collection...

    summerpxy 評(píng)論0 收藏0

  • Week 2 - Java 容器 - 詳細(xì)剖析 List 之 ArrayList, Vector,

    摘要：底層使用的是雙向鏈表數(shù)據(jù)結(jié)構(gòu)之前為循環(huán)鏈表，取消了循環(huán)。快速隨機(jī)訪問(wèn)就是通過(guò)元素的序號(hào)快速獲取元素對(duì)象對(duì)應(yīng)于方法。而接口就是用來(lái)標(biāo)識(shí)該類支持快速隨機(jī)訪問(wèn)。僅僅是起標(biāo)識(shí)作用。，中文名為雙端隊(duì)列。不同的是，是線程安全的，內(nèi)部使用了進(jìn)行同步。 前言 學(xué)習(xí)情況記錄 時(shí)間：week 2 SMART子目標(biāo) ：Java 容器 記錄在學(xué)習(xí)Java容器 知識(shí)點(diǎn)中，關(guān)于List的需要重點(diǎn)記錄的知識(shí)點(diǎn)。...

    MartinDai 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<