亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

Java容器類研究5：LinkedList

frank_fun / 2106人閱讀

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

java.util.LinkedList

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

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

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

Deque是一個雙端隊列的接口，而Deque又繼承了接口Queue。所以LinkedList可以作為隊列、雙端隊列來使用。

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

LinkedList用什么結(jié)構(gòu)來實現(xiàn)

同樣很簡單，是一個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記錄著鏈表的開始和結(jié)束節(jié)點。

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

在LinkedList中，大量的方法需要先獲得指定下標(biāo)的節(jié)點，具體實現(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;
        }
    }

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

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

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

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

LinkedList每次劃分，不是采用的1/2策略，而是每次分裂出來的一塊數(shù)據(jù)都增加一個BATCH_UNIT(1024)的大小。比較有趣的是，每次分裂出來的Spliterator并不是LinkedList自己實現(xiàn)的Spliterator，而是一個ArraySpliterator，ArraySpliterator采用的是1/2的分裂策略。所以LinkedList每次分裂都想盡可能快的分裂出更多的元素，并且分裂過程中將鏈表結(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，其實是ArraySpliterator
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

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

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/67799.html

相關(guān)文章

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

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

    codergarden 評論0 收藏0

  • Java容器類研究1：Collection

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

    AprilJ 評論0 收藏0

  • Java容器類研究6：Vector

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

    Charles 評論0 收藏0

  • Java 持有對象（11）

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

    summerpxy 評論0 收藏0

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

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

    MartinDai 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<