本篇內(nèi)容主要講解“怎么理解LinkedList源碼”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么理解LinkedList源碼”吧!
成都創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括汪清網(wǎng)站建設(shè)、汪清網(wǎng)站制作、汪清網(wǎng)頁制作以及汪清網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，汪清網(wǎng)站推廣取得了明顯的社會效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到汪清省份的部分城市，未來相信會繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！
LinkedList是也是非常常見的集合類，LinkedList是基于鏈表實(shí)現(xiàn)的集合。它擁有List集合的特點(diǎn)：
存取有序
帶索引
允許重復(fù)元素
還擁有Deque集合的特點(diǎn)：
先入先出
雙端操作
它本身的特點(diǎn)是：
對元素進(jìn)行插入或者刪除，只需要更改一些數(shù)據(jù)，不需要元素進(jìn)行移動。
依然是通過源碼來看看LinkedList如何實(shí)現(xiàn)自己的特性的。
Doubly-linked list implementation of the {@code List} and {@code Deque} interfaces. Implements all optional list operations,and permits all elements (including {@code null}).
對于List接口和Deque接口的雙鏈表實(shí)現(xiàn)。實(shí)現(xiàn)了所有List接口的操作并且能存儲所有的元素。
public class LinkedListextends AbstractSequentialList implements List , Deque , Cloneable, java.io.Serializable
可以看到LinkedList實(shí)現(xiàn)了一個(gè)Deque接口，其實(shí)是說，LinkedList除了有List的特性，還有Deque的特性，那么Deque是什么呢？
public interface Dequeextends Queue public interface Queue extends Collection
原來是繼承了Collection集合的另一個(gè)接口。
Queue就是我們常說的隊(duì)列，它的特性是FIFO( First In First Out )先進(jìn)先出，它的操作只有兩個(gè)：
把元素存進(jìn)隊(duì)列尾部
從頭部取出元素
就像排隊(duì)辦事一樣的。
而它的子接口Deque除了這兩操作以外，還能比Queue隊(duì)列有更多的功能
既可以添加元素到隊(duì)尾，也可以添加元素到隊(duì)頭
既可以從隊(duì)尾取元素，也可以從隊(duì)頭取元素
如此看來就像兩邊都可以當(dāng)隊(duì)頭和隊(duì)尾一樣，所以Deque又叫雙端隊(duì)列 。
理所應(yīng)當(dāng)?shù)?，LinkedLisk也實(shí)現(xiàn)了這些特性，并且有Doubly-linked(雙鏈表的特性)。
那么什么又是鏈表呢？
其實(shí)鏈表是一種線性的存儲結(jié)構(gòu)，意思是將要存儲的數(shù)據(jù)存在一個(gè)存儲單元里面，這個(gè)存儲單元里面除了存放有待存儲的數(shù)據(jù)以外，還存儲有其下一個(gè)存儲單元的地址。
雙鏈表顧名思義，存儲單元除了存儲其下一個(gè)存儲單元的地址，還存儲了上一個(gè)存儲單元的地址。每次查找數(shù)據(jù)的時(shí)候，就通過存儲單元里存儲的地址信息進(jìn)行查找。
成員變量：
transient int size = 0; transient Nodefirst; transient Node last;
只有三個(gè)，size代表LinkedList存儲的元素個(gè)數(shù)。那這個(gè)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; } }
它是LinkedList內(nèi)部的數(shù)據(jù)結(jié)構(gòu)Node，作為LinkedList的基本存儲單元，也最能體現(xiàn)LinkedList雙鏈表的特性。
像這樣的。
其中prev存儲上一個(gè)節(jié)點(diǎn)的引用(地址)，next存儲下一個(gè)單元的引用，item就是具體要存的數(shù)據(jù)。
First和Last用來標(biāo)明隊(duì)頭跟隊(duì)尾。
添加數(shù)據(jù)：
重慶分公司
重慶分公司
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
} 默認(rèn)是調(diào)用添加到尾部的方法。前面說過，LinkedList的基本存儲單元是Node，所以添加進(jìn)來的數(shù)據(jù)會被封裝進(jìn)Node的item屬性里，而且這個(gè)新Node的prev會指向前一個(gè)Node，前一個(gè)Node的next會指向這個(gè)新Node。
類似這樣，但是注意畫線只是一種形象的表達(dá)方法，就如上面所說，在Node里的prev屬性和next屬性是用來存儲引用的，通過這個(gè)引用就能找到前一個(gè)Node或者后一個(gè)Node。
public void addFirst(E e) {
linkFirst(e);
}
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++;
}
public void addLast(E e) {
linkLast(e);
}
public boolean offerLast(E e) {
addLast(e);
return true;
} 其實(shí)LinkedList很多不同名的方法，但是實(shí)現(xiàn)方式都是類似的，這是因?yàn)槲覀冇锌赡苡肔inkedList表達(dá)不同的數(shù)據(jù)結(jié)構(gòu)，雖然都是添加元素到隊(duì)首/隊(duì)尾，但是清晰的描述對代碼的可讀性是有好處的。像如果要用LinkedList表示Stack(棧)數(shù)據(jù)結(jié)構(gòu)時(shí)候用push()/pop()/peek()等方法來描述，用LinkedList表示Queue(隊(duì)列)數(shù)據(jù)結(jié)構(gòu)時(shí)候用add()/offer()等方法來描述。(當(dāng)然，更好的實(shí)現(xiàn)方式是多態(tài)。)
刪除數(shù)據(jù)：
//刪除頭Node
public E removeFirst() {
final Node f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//刪除操作
private E unlinkFirst(Node f) {
// assert f == first && f != null;
final E element = f.item;
final Node next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
//刪除尾Node
public E removeLast() {
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
//刪除操作
private E unlinkLast(Node l) {
// assert l == last && l != null;
//拿到最后一個(gè)元素存放的數(shù)據(jù)
final E element = l.item;
//拿到最后一個(gè)元素的prev前元素的引用
final Node prev = l.prev;
//將它們賦值為null
l.item = null;
l.prev = null; // help GC
//現(xiàn)在前元素是list(最后一個(gè)Node)
last = prev;
//如果前元素已經(jīng)是null說明沒有Node了
if (prev == null)
first = null;
else
//說明前面還有元素，那么前元素的next就存放null
prev.next = null;
size--;
modCount++;
return element;
} 先看看簡單的刪除， 這里是指定刪除最前跟最后的元素，所以只要判斷刪除后Node的prev或者next是否還有值，有就說明還有Node，沒有就說明LinkedList已經(jīng)為空了。
怎樣才算刪除了頭/尾Node，只要它的next/prev為空，說明沒有引用指向它了，那么我們就認(rèn)為它從LinkedList里刪除了，因?yàn)槲覀儫o法通過存儲單元的引用找到這個(gè)Node，所以GC很快也會來回收掉這個(gè)Node。
這只是刪除頭尾Node，那要是刪除中間的Node呢？這要跟下面的查找和插入一起看。
查找元素：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
// assert isElementIndex(index);
//如果索引小于元素個(gè)數(shù)的一半，就從前遍歷
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;
}
} 數(shù)組默認(rèn)是有下標(biāo)的，可以一次就取出所在位置的元素，但是LinkedList底層可沒有維護(hù)這么一個(gè)數(shù)組，那怎么知道第幾個(gè)元素是什么呢？
笨方法，我有size個(gè)元素，我不知道你指定的index在哪，那我一個(gè)一個(gè)找過去不就完事了？畢竟我的存儲單元Node記得它旁邊的單元的引用(地址)。
如果你的index比我size的一半還大，那我就從后面找，因?yàn)槲沂请p端隊(duì)列，有Last的引用(地址)，所以可以調(diào)換兩頭。
所以，在LinkedList里面找元素可不容易，最多可能要找size/2次才能找到。
只要找到了想要的位置，那么插入和刪除指定的這個(gè)Node就很簡單了。
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node x) {
// assert x != null;
//拿到所要?jiǎng)h除的Node的item
final E element = x.item;
//后一個(gè)Node
final Node next = x.next;
//前一個(gè)Node
final Node prev = x.prev;
//如果前一個(gè)Node為null(說明是第一個(gè)Node)
if (prev == null) {
//那么后一個(gè)Node作為first
first = next;
} else {//否則說明前面有Node
//那前一個(gè)Node的下一個(gè)Node引用變?yōu)楹笠粋€(gè)Node
prev.next = next;
//當(dāng)前的前引用變成null
x.prev = null;
}
//如果后一個(gè)Node為null(說明是最后一個(gè)Node)
if (next == null) {
//那么前一個(gè)Node作為last
last = prev;
} else {//否則說明后面還有Node
//那后一個(gè)Node的下一個(gè)Node引用變?yōu)榍耙粋€(gè)Node
next.prev = prev;
//當(dāng)前的后引用變?yōu)閚ull
x.next = null;
}
//保存的元素也設(shè)為null
x.item = null;
//元素-1
size--;
//修改次數(shù)+1
modCount++;
return element;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
void linkBefore(E e, Node succ) {
// assert succ != null;
//要插入位置的前一個(gè)Node
final Node pred = succ.prev;
//新Node，前引用是前一個(gè)Node，后引用是當(dāng)前位置的Node
final Node newNode = new Node<>(pred, e, succ);
//后一個(gè)Node的前引用變?yōu)檫@個(gè)新Node
succ.prev = newNode;
//如果沒有前一個(gè)Node
if (pred == null)
//說明添加的就是第一個(gè)Node了
first = newNode;
else//說明前面還有Node
//將前一個(gè)Node的后引用變?yōu)檫@個(gè)新的Node
pred.next = newNode;
//元素+1
size++;
modCount++;
} 只是改變了存儲單元Node里的prev和next，我們就可以認(rèn)為這個(gè)Node被插入/刪除了。
代碼的注釋配合著下圖看，就會方便理解很多，其中注意區(qū)分源代碼中的命名，最好拿筆記一下容易區(qū)分一些。
如果是插入元素，倒著看就可以了。
關(guān)于遍歷：
我們可以了解到，LinkedList最大的性能消耗就在node(index)這步，這會需要去查找大量的元素。但是只要找到了這個(gè)元素所在的Node，插入跟刪除就非常的方便了。
所以對于get(index)這個(gè)方法，我們需要非常小心的去使用，如果只想看一看這個(gè)位置的元素，可以用這個(gè)方法，但是如果是遍歷LinkedList，千萬不可以這樣寫：
for (int i = 0; i < linkedList.size(); i++) {
linkedList.get(i).equals(Obj);
}這樣對于每次循環(huán),get總會從前或者從后走i次，不考慮get方法中>>1的優(yōu)化的話，這是一種O(n^2)時(shí)間復(fù)雜度的做法，效率十分低下。
所以LinkedList提供了內(nèi)部的Iterator迭代器供我們使用：
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; }
其實(shí)就是通過不斷調(diào)用next()方法取得Node，然后再對Node做操作，這樣時(shí)間復(fù)雜度就是O(n)了，不會有大量重復(fù)無用的遍歷。
到此，相信大家對“怎么理解LinkedList源碼”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
