鏈表是對(duì)上一篇博文所說的順序表的一種實(shí)現(xiàn)。

與ArrayList思路截然不同，鏈表的實(shí)現(xiàn)思路是：

不同元素實(shí)際上是存儲(chǔ)在離散的內(nèi)存空間中的。

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

從鏈表的概念來講，它可以算是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，因?yàn)殒湵砟玫舻谝粋€(gè)元素剩下的部分，依然構(gòu)成一個(gè)鏈表。

時(shí)間空間復(fù)雜度

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

插入元素。實(shí)際上插入元素需要看情況：

如果指定鏈表中某個(gè)元素將其插之其后，那么首先得找出該元素對(duì)應(yīng)的節(jié)點(diǎn)，還是O(n)。

如果能夠直接指定節(jié)點(diǎn)往其后插入(如通過迭代器)，那么僅僅需要移動(dòng)指針即可完成，O(1)。

移除元素。移除和插入類似，得看提供的參數(shù)是什么。如果提供的是元素所在的節(jié)點(diǎn)，那么也只需要O(1)。

LinkedList的繼承結(jié)構(gòu)

首先繼承結(jié)構(gòu)和ArrayList類似，實(shí)現(xiàn)了List接口。

但是，它繼承的是繼承了AbstractList類的AbstractSequentialList類，

這個(gè)類的作用也是給List中的部分函數(shù)提供默認(rèn)實(shí)現(xiàn)，只是這個(gè)類對(duì)鏈表這種List的實(shí)現(xiàn)提供了更多貼合的默認(rèn)函數(shù)實(shí)現(xiàn)。

還有可以注意到，LinkedList實(shí)現(xiàn)了Deque接口，這也很顯然，鏈表這種結(jié)構(gòu)天然就適合當(dāng)做雙端隊(duì)列使用。

LinkedList源碼分析

節(jié)點(diǎn)定義

先來看鏈表的節(jié)點(diǎn)定義：

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;

}

}

可以看到，鏈表節(jié)點(diǎn)除了保存數(shù)據(jù)外，還需要保存指向前后節(jié)點(diǎn)的指針。

這里，鏈表即有后繼指針也有前驅(qū)指針，因此這是一個(gè)雙向鏈表。

一組節(jié)點(diǎn)之間按順序用指針指起來，就形成了鏈表的鏈狀結(jié)構(gòu)。

屬性和構(gòu)造函數(shù)

transient int size = 0;

transient Node first;

transient Node last;

三個(gè)屬性，first和last分別指向鏈條的首節(jié)點(diǎn)和尾節(jié)點(diǎn)。

這樣有個(gè)好處，就是鏈表即可以使用頭插法也可以采用尾插法。

size屬性跟蹤了鏈表的元素個(gè)數(shù)。雖然說遍歷一遍鏈表也能統(tǒng)計(jì)到元素個(gè)數(shù)，

但是那是O(n)的費(fèi)時(shí)操作。

因此，我們可以發(fā)現(xiàn)鏈表的size方法是O(1)的時(shí)間復(fù)雜度。

public LinkedList() {

}

LinkedList的代碼很簡(jiǎn)單，構(gòu)造函數(shù)空空如也。

空表中，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的思路都是先根據(jù)索引定位到鏈表節(jié)點(diǎn)，然后獲得或設(shè)置節(jié)點(diǎn)中的數(shù)據(jù)，這抽象出了node函數(shù)，根據(jù)索引找到鏈表節(jié)點(diǎn)。

node的思路也很顯然，遍歷一遍即可得到。

這里做了一點(diǎn)優(yōu)化，我們可以發(fā)現(xiàn)LinkedList的實(shí)現(xiàn)是一個(gè)雙向鏈表，并且LinkedList持有了頭尾指針。

那么，根據(jù)索引和size就可以知道該節(jié)點(diǎn)是在鏈表的前半部分還是后半部分，

從而決定從頭節(jié)點(diǎn)開始遍歷還是從尾節(jié)點(diǎn)開始遍歷，這樣最多遍歷 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++;

}

添加/刪除的思路都類似，刪除的代碼就不貼了。如果能夠提供需要被操作的節(jié)點(diǎn)，就能直接移動(dòng)下指針，O(1)完成。否則就需要遍歷找到這個(gè)節(jié)點(diǎn)再操作。

需要關(guān)注兩點(diǎn)：

有的操作是操作頭指針，有的操作是操作尾指針。但是不管操作哪一個(gè)，都需要維護(hù)另外一個(gè)指針及size的值。

如果是刪除，刪除后及時(shí)把相關(guān)節(jié)點(diǎn)的item字段置為null，以幫助gc能更快的釋放內(nèi)存。

modCount字段分析

之前閱讀ArrayList的代碼時(shí)發(fā)現(xiàn)了modCount這一字段，它是定義在AbstractList類中的。之前不知道它起到什么作用，這次給弄明白了。

迭代器

迭代器迭代中表被修改

考慮以下這段代碼：

List list = new LinkedList<>();

Iterator it = list.listIterator();

list.add(1);

it.next();

在迭代器創(chuàng)建之后，對(duì)表進(jìn)行了修改。這時(shí)候如果操作迭代器，則會(huì)得到異常java.util.ConcurrentModificationException。

這樣設(shè)計(jì)是因?yàn)?#xff0c;迭代器代表表中某個(gè)元素的位置，內(nèi)部會(huì)存儲(chǔ)某些能夠代表該位置的信息。當(dāng)表發(fā)生改變時(shí)，該信息的含義可能會(huì)發(fā)生變化，這時(shí)操作迭代器就可能會(huì)造成不可預(yù)料的事情。

因此，果斷拋異常阻止，是最好的方法。

實(shí)際上，這種迭代器迭代過程中表結(jié)構(gòu)發(fā)生改變的情況，更經(jīng)常發(fā)生在多線程的環(huán)境中。

記錄表被修改的標(biāo)記

這種機(jī)制的實(shí)現(xiàn)就需要記錄表被修改，那么思路是使用狀態(tài)字段modCount。

每當(dāng)會(huì)修改表的操作執(zhí)行時(shí)，都將此字段加1。使用者只需要前后對(duì)比該字段就知道中間這段時(shí)間表是否被修改。

如linkedList中的頭插和尾插函數(shù)，就將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();

}

}

迭代器開始時(shí)記錄下初始的值：

private int expectedModCount = modCount;

然后與現(xiàn)在的值對(duì)比判斷是否被修改：

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

這是一個(gè)內(nèi)部類，隱式持有LinkedList的引用，能夠直接訪問到LinkedList中的modCount字段。

總結(jié)

以上是生活随笔為你收集整理的java 集合modcount_源码|jdk源码之LinkedList与modCount字段的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。