Java容器類研究5：LinkedList

frank_fun 發布于2019-08-15 12:13 / 2049人閱讀

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

java.util.LinkedList

Java中有現成的隊列可以用嗎

有，就是LinkedList。LinkedList實現的接口如下，其實也可以當做stack使用：

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

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

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

LinkedList用什么結構來實現

同樣很簡單，是一個Node的雙向鏈表結構。

    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記錄著鏈表的開始和結束節點。

在鏈表中通過下標取值是低效的

在LinkedList中，大量的方法需要先獲得指定下標的節點，具體實現如下：

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

可以看出，開發者已經盡力優化，根據index大小決定從何處開始遍歷。

LinkedList實現了自己的ListIterator

遍歷方法利用了鏈表結構的特性，進行遍歷。其中有如下屬性記錄遍歷狀態。

    private Node lastReturned; //記錄最近一次返回的節點
    private Node next;    //記錄下一個要返回的節點
    private int nextIndex;   //記錄下一個要返回的位置
    private int expectedModCount = modCount;  //記錄期望的修改次數

LinkedList的Spliterator采用什么樣的分割策略

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

        //該方法位于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到數組中
                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;
        }

云服務器 GPU云服務器 LinkedList 自定義容器類 java目前研究 java研究網

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67799.html

Java 基礎 | Collection 集合概覽

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

codergarden 2019-08-19 10:26 評論0 收藏0
Java容器類研究1：Collection

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

AprilJ 2019-08-15 12:07 評論0 收藏0
Java容器類研究6：Vector

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

Charles 2019-08-15 12:16 評論0 收藏0
Java 持有對象（11）

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

summerpxy 2019-08-16 12:46 評論0 收藏0
Week 2 - Java 容器 - 詳細剖析 List 之 ArrayList, Vector,

摘要：底層使用的是雙向鏈表數據結構之前為循環鏈表，取消了循環。快速隨機訪問就是通過元素的序號快速獲取元素對象對應于方法。而接口就是用來標識該類支持快速隨機訪問。僅僅是起標識作用。，中文名為雙端隊列。不同的是，是線程安全的，內部使用了進行同步。前言學習情況記錄時間：week 2 SMART子目標：Java 容器記錄在學習Java容器知識點中，關于List的需要重點記錄的知識點。...

MartinDai 2019-08-16 18:35 評論0 收藏0