国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

源碼|jdk源碼之LinkedList與modCount字段

趙連江 / 969人閱讀

摘要:迭代器迭代器迭代中表被修改考慮以下這段代碼在迭代器創建之后,對表進行了修改。這樣設計是因為,迭代器代表表中某個元素的位置,內部會存儲某些能夠代表該位置的信息。

鏈表是對上一篇博文所說的順序表的一種實現。

與ArrayList思路截然不同,鏈表的實現思路是:

不同元素實際上是存儲在離散的內存空間中的。

每一個元素都有一個指針指向下一個元素,這樣整個離散的空間就被“串”成了一個有順序的表。

從鏈表的概念來講,它可以算是一種遞歸的數據結構,因為鏈表拿掉第一個元素剩下的部分,依然構成一個鏈表。

時間空間復雜度

通過索引定位其中的一個元素。由于不能像ArrayList那樣直接通過計算內存地址偏移量來定位元素,只能從第一個元素開始順藤摸瓜來數,因此為O(n)。

插入元素。實際上插入元素需要看情況:

如果指定鏈表中某個元素將其插之其后,那么首先得找出該元素對應的節點,還是O(n)。

如果能夠直接指定節點往其后插入(如通過迭代器),那么僅僅需要移動指針即可完成,O(1)。

移除元素。移除和插入類似,得看提供的參數是什么。如果提供的是元素所在的節點,那么也只需要O(1)。

LinkedList的繼承結構

首先繼承結構和ArrayList類似,實現了List接口。
但是,它繼承的是繼承了AbstractList類的AbstractSequentialList類,
這個類的作用也是給List中的部分函數提供默認實現,只是這個類對鏈表這種List的實現提供了更多貼合的默認函數實現。

還有可以注意到,LinkedList實現了Deque接口,這也很顯然,鏈表這種結構天然就適合當做雙端隊列使用。

LinkedList源碼分析 節點定義

先來看鏈表的節點定義:

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

可以看到,鏈表節點除了保存數據外,還需要保存指向前后節點的指針。
這里,鏈表即有后繼指針也有前驅指針,因此這是一個雙向鏈表。

一組節點之間按順序用指針指起來,就形成了鏈表的鏈狀結構。

屬性和構造函數
    transient int size = 0;
    transient Node first;
    transient Node last;

三個屬性,first和last分別指向鏈條的首節點和尾節點。
這樣有個好處,就是鏈表即可以使用頭插法也可以采用尾插法。

size屬性跟蹤了鏈表的元素個數。雖然說遍歷一遍鏈表也能統計到元素個數,
但是那是O(n)的費時操作。
因此,我們可以發現鏈表的size方法是O(1)的時間復雜度。

    public LinkedList() {
    }

LinkedList的代碼很簡單,構造函數空空如也。
空表中,first和last字段都為null。

get和set方法
    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

    public E set(int index, E element) {
        checkElementIndex(index);
        Node x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

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

get和set的思路都是先根據索引定位到鏈表節點,然后獲得或設置節點中的數據,這抽象出了node函數,根據索引找到鏈表節點。

node的思路也很顯然,遍歷一遍即可得到。
這里做了一點優化,我們可以發現LinkedList的實現是一個雙向鏈表,并且LinkedList持有了頭尾指針。
那么,根據索引和size就可以知道該節點是在鏈表的前半部分還是后半部分,
從而決定從頭節點開始遍歷還是從尾節點開始遍歷,這樣最多遍歷 N / 2次即可找到。

添加/刪除
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

    void linkBefore(E e, Node succ) {
        final Node pred = succ.prev;
        final Node newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

添加/刪除的思路都類似,刪除的代碼就不貼了。如果能夠提供需要被操作的節點,就能直接移動下指針,O(1)完成。否則就需要遍歷找到這個節點再操作。
需要關注兩點:

有的操作是操作頭指針,有的操作是操作尾指針。但是不管操作哪一個,都需要維護另外一個指針及size的值。

如果是刪除,刪除后及時把相關節點的item字段置為null,以幫助gc能更快的釋放內存。

modCount字段分析

之前閱讀ArrayList的代碼時發現了modCount這一字段,它是定義在AbstractList類中的。之前不知道它起到什么作用,這次給弄明白了。

迭代器 迭代器迭代中表被修改

考慮以下這段代碼:

List list = new LinkedList<>();
    Iterator it = list.listIterator();
    list.add(1);
    it.next();

在迭代器創建之后,對表進行了修改。這時候如果操作迭代器,則會得到異常java.util.ConcurrentModificationException
這樣設計是因為,迭代器代表表中某個元素的位置,內部會存儲某些能夠代表該位置的信息。當表發生改變時,該信息的含義可能會發生變化,這時操作迭代器就可能會造成不可預料的事情。
因此,果斷拋異常阻止,是最好的方法。

實際上,這種迭代器迭代過程中表結構發生改變的情況,更經常發生在多線程的環境中。

記錄表被修改的標記

這種機制的實現就需要記錄表被修改,那么思路是使用狀態字段modCount
每當會修改表的操作執行時,都將此字段加1。使用者只需要前后對比該字段就知道中間這段時間表是否被修改。

如linkedList中的頭插和尾插函數,就將modCount字段自增:

    private void linkFirst(E e) {
        final Node f = first;
        final Node newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    void linkLast(E e) {
        final Node l = last;
        final Node newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
迭代器

迭代器使用該字段來判斷,

    private class ListItr implements ListIterator {
        private Node lastReturned;
        private Node next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        /* ... */

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

迭代器開始時記錄下初始的值:

        private int expectedModCount = modCount;

然后與現在的值對比判斷是否被修改:

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

這是一個內部類,隱式持有LinkedList的引用,能夠直接訪問到LinkedList中的modCount字段。

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

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

相關文章

  • LinkedList源碼解析

    摘要:我們來看相關源碼我們看到封裝的和操作其實就是對頭結點的操作。迭代器通過指針,能指向下一個節點,無需做額外的遍歷,速度非常快。不同的遍歷性能差距極大,推薦使用迭代器進行遍歷。LinkedList類介紹 上一篇文章我們介紹了JDK中ArrayList的實現,ArrayList底層結構是一個Object[]數組,通過拷貝,復制等一系列封裝的操作,將數組封裝為一個幾乎是無限的容器。今天我們來介紹JD...

    番茄西紅柿 評論0 收藏0
  • LinkedList源碼解析

    摘要:我們來看相關源碼我們看到封裝的和操作其實就是對頭結點的操作。迭代器通過指針,能指向下一個節點,無需做額外的遍歷,速度非常快。不同的遍歷性能差距極大,推薦使用迭代器進行遍歷。LinkedList類介紹 上一篇文章我們介紹了JDK中ArrayList的實現,ArrayList底層結構是一個Object[]數組,通過拷貝,復制等一系列封裝的操作,將數組封裝為一個幾乎是無限的容器。今天我們來介紹JD...

    番茄西紅柿 評論0 收藏0
  • LinkedList源碼分析:JDK源碼分析系列

    摘要:介紹是線程不安全的,允許元素為的雙向鏈表。構造方法共有兩個構造方法,一個是創建一個空的構造函數,一個是將已有的添加到中。是將元素插入到的頭部。下一篇文章繼續分析上次分析了的結構和添加方法這次開始分析下面的。注意源碼版本為直接進入正題。 如果本文中有不正確的地方請指出由于沒有留言可以在公眾號添加我的好友共同討論。 1.介紹 LinkedList 是線程不安全的,允許元素為null的雙向鏈...

    blair 評論0 收藏0

發表評論

0條評論

趙連江

|高級講師

TA的文章

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