Java中的LinkedList集合詳解
一、介紹
LinkedList 是一個雙向鏈表結構（JDK1.6 之前為循環(huán)鏈表，JDK1.7 取消了循環(huán)），在任意位置插入刪除都很方便，但是不支持隨機取值，每次都只能從一端開始遍歷，直到找到查詢的對象，然后返回；不過，它不像 ArrayList 那樣需要進行內存拷貝，因此相對來說效率較高，但是因為存在額外的前驅和后繼節(jié)點指針，因此占用的內存比 ArrayList 多一些。
LinkedList 采用鏈表存儲，所以對于add(E e)方法的插入，刪除元素時間復雜度不受元素位置的影響，近似 O(1)，如果是要在指定位置i插入和刪除元素的話（(add(int index, Eelement)） 時間復雜度近似為o(n))因為需要先移動到指定位置再插入
二、源碼分析
1、LinkedList實現(xiàn)的接口
如下圖：
觀察上圖：
AbstractSequentialList抽象類：繼承自 AbstractList，是 LinkedList 的父類，是 List 接口 的簡化版實現(xiàn)，具有雙端隊列的功能
- List接口：列表，add、set、等一些對列表進行操作的方法
- Deque接口：實現(xiàn)了雙端隊列接口Deque，因此具有雙端隊列的功能
- Serializable接口：主要用于序列化，即：能夠將對象寫入磁盤。與之對應的還有反序列化操作，就是將對象從磁盤中讀取出來。因此如果要進行序列化和反序列化，ArrayList的實例對象就必須實現(xiàn)這個接口，否則在實例化的時候程序會報錯（java.io.NotSerializableException）。
- Cloneable接口：實現(xiàn)Cloneable接口的類能夠調用clone方法，如果沒有實現(xiàn)Cloneable接口就調用方法，就會拋出異常（java.lang.CloneNotSupportedException）。
2、LinkedList中的變量
- transient int size = 0：雙向鏈表節(jié)點數(shù)量size。默認初始化值為0，包訪問權限。
- transient Node<E> first：雙向鏈表的頭節(jié)點。包訪問權限。
- transient Node<E> last：雙向鏈表的尾節(jié)點。包訪問權限。
3、LinkedList的構造方法
（1）無參構造方法
public LinkedList() {
}總結：無參構造方法，此時雙向鏈表的節(jié)點數(shù)量size為0，雙向鏈表的頭尾節(jié)點為null。
（2）帶集合參數(shù)的構造方法
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}總結：先將集合轉換為數(shù)組，然后將數(shù)組中的元素按照索引順序一個個從雙向鏈表的尾部插入到空的雙向鏈表中。
4、LinkedList中的重要方法
（1）靜態(tài)內部類Node
private static class Node<E> {
//元素
E item;
//后驅指針
Node<E> next;
//前驅指針
Node<E> prev;
//構造方法
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}（2）add()方法
public boolean add(E e) {
//將元素添加到鏈表的尾部
linkLast(e);
return true;
} void linkLast(E e) {
final Node<E> l = last;
//創(chuàng)建新節(jié)點
final Node<E> newNode = new Node<>(l, e, null);
//把之前的尾指針節(jié)點指向新節(jié)點
last = newNode;
//如果尾節(jié)點為空，則代表是新鏈表，直接賦值給頭指針；如果不為空，則把尾指針指向新節(jié)點
if (l == null)
first = newNode;
else
l.next = newNode;
//長度++
size++;
//代表對集合的操作次數(shù)
modCount++;
}通過上述分析，可以看到：add()方法調用了linkLast()方法，將新節(jié)點插入到鏈表的尾部。在linkLast()方法里對尾指針last進行了判斷，如果尾節(jié)點為空，說明是第一次插入元素，則直接將新節(jié)點賦值給頭指針；如果尾節(jié)點不為空，則將節(jié)點的尾指針指向新節(jié)點即可，然后再將size和modCount自增1。modCount不是LinkedList里的變量，而是來自于AbstractList。
接下來看一下如何在指定位置添加元素：
public void add(int index, E element) {
//檢查索引位置
checkPositionIndex(index);
//如果和當前長度size相等，則直接添加元素到末尾，否則就將元素插入到指定的位置
if (index == size)
linkLast(element);
else
linkBefore(element, node(index)); //node用來獲取給定index處的元素節(jié)點
}
//索引校驗
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//linkLast()前面已經(jīng)介紹，這里只展示linkBefore()
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}由上述分析可以看到：在指定位置添加元素的時候，首先調用checkPositionIndex()方法判斷下標是否越界，然后判斷index是否等于 size，如果相等則添加到末尾，否則將該元素插入的 index 的位置。linkBefore()方法負責把元素 e 插入到 succ 之前。
node(index)方法是獲取 index 位置的節(jié)點，它將index與當前鏈表的一半進行比較，如果比一半小則從頭遍歷，如果比一半大則向后遍歷。
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}在前面介紹LinkedList的有參構造時，我們可以看到其調用了addAll()方法，那么接下來看看這個方法又是如何實現(xiàn)的？
//調用addAll(index, c)
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
//檢查index是否越界
checkPositionIndex(index);
//將集合轉為數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//遍歷數(shù)組，將數(shù)組中的元素創(chuàng)建為節(jié)點，并按照順序連接起來
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
//修改當前節(jié)點個數(shù)size的值
//操作次數(shù)modCount+1
size += numNew;
modCount++;
return true;
}（3）remove()方法
如果是刪除指定位置的元素，則先檢查下標是否越界，然后再調用unlink()方法釋放節(jié)點，移除掉指定的元素。
//移除指定位置的元素
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//如果移除的是頭節(jié)點，則頭節(jié)點后移
if (prev == null) {
first = next;
} else {
prev.next = next; //否則就釋放節(jié)點的遷移借宿
x.prev = null;
}
//如果溢出的是尾節(jié)點，則尾節(jié)點前移
if (next == null) {
last = prev;
} else {
next.prev = prev; //否則就釋放節(jié)點的后一個元素
x.next = null;
}
//節(jié)點數(shù)據(jù)置為空
x.item = null;
size--;
modCount++;
return element;
}remove(Object o)從該列表中刪除第一個出現(xiàn)的指定元素（如果存在）。如果此列表不包含該元素，則它將保持不變。
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}除了上述的移除元素方法，還有一些其他的方法，如：removeFirst()、removeLast()、poll()等，這里不再贅述。
（4）set()方法
set()方法通過修改下標獲取到下標節(jié)點，獲取出舊值返回，把新值賦值元素
public E set(int index, E element) {
//檢查索引是否越界
checkElementIndex(index);
//獲取到要修改的元素的下標
Node<E> x = node(index);
//獲取舊值
E oldVal = x.item;
//修改
x.item = element;
return oldVal;
}（5）get()方法
get()方法根據(jù)下標獲取元素遍歷找到當前元素并返回，遍歷利用的是判斷當前獲取元素位于鏈表的前半段還是后半段，前半段則從頭遍歷到當前位置返回，后半段則從尾遍歷到當前位置返回
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}除此之外，還有getFirst()、element()、peek()、peekFirst() 這四個獲取頭結點方法，區(qū)別在于對鏈表為空時的處理，是拋出異常還是返回null，其中getFirst() 和element() 方法將會在鏈表為空時，拋出異常；因為內部都保存了頭節(jié)點所以直接獲取頭節(jié)點就可以。getLast() 方法在鏈表為空時，會拋出NoSuchElementException，而peekLast() 則不會，只是會返回 null；內部保存了尾節(jié)點直接返回即可。
三、總結
1、LinkedList總結
- linkedList本質上是一個雙向鏈表，通過一個Node內部類實現(xiàn)的這種鏈表結構。
- LinkedList能存儲null值。
- LinkedList在刪除和增加等操作上性能好，而ArrayList在查詢的性能上好。
- 從源碼中看，它不存在容量不足的情況。
- LinkedList不光能夠向前迭代，還能像后迭代，并且在迭代的過程中，可以修改值、添加值、還能移除值。
- LinkedList不光能當鏈表，還能當隊列使用，這個就是因為實現(xiàn)了Deque接口。
2、雙向鏈表與雙向循環(huán)鏈表
雙向鏈表就是一個元素有3個屬性，一個向前的指針，一個向后的指針，一個當前節(jié)點值；雙向就是本節(jié)點既有向后的指向，也有向前的
雙向循環(huán)鏈表的差別在于循環(huán)，雙向鏈表首位不相連，指針都指向空，雙向循環(huán)鏈表是首位相連形成環(huán)狀
3、JDK1.7為什么把雙向循環(huán)鏈表改為雙向鏈表
- 雙向循環(huán)鏈表是通過new一個headerEntry管理首尾相連得，可以少創(chuàng)建對象
- 寫操作主要分為2種，一種頭尾插入，一種中間插入；雙向鏈表的有點在于頭尾插入的時候只需要維護一個指針，中間插入2個沒什么區(qū)別，但實際使用中頭尾插入是最頻繁的
4、ArrayList 與LinkedList比較
- ArrayList是基于數(shù)組實現(xiàn)的，LinkedList是基于雙鏈表實現(xiàn)的。另外LinkedList類不僅是List接口的實現(xiàn)類，可以根據(jù)索引來隨機訪問集合中的元素，除此之外，LinkedList還實現(xiàn)了Deque接口，Deque接口是Queue接口的子接口，它代表一個雙向隊列，因此LinkedList可以作為雙向隊列 ，棧（可以參見Deque提供的接口方法）和List集合使用，功能強大。
- ArrayList是基于索引(index)的數(shù)據(jù)結構，它使用索引在數(shù)組中搜索和讀取數(shù)據(jù)是很快的，可以直接返回數(shù)組中index位置的元素，因此在隨機訪問集合元素上有較好的性能。Array獲取數(shù)據(jù)的時間復雜度是O(1),但是要插入、刪除數(shù)據(jù)卻是開銷很大的，因為這需要移動數(shù)組中插入位置之后的的所有元素。LinkedList的隨機訪問集合元素時性能較差，因為需要在雙向列表中找到要index的位置，再返回；但在插入，刪除操作是更快的。因為LinkedList不像ArrayList一樣，不需要改變數(shù)組的大小，也不需要在數(shù)組裝滿的時候要將所有的數(shù)據(jù)重新裝入一個新的數(shù)組，這是ArrayList最壞的一種情況，時間復雜度是O(n)，而LinkedList中插入或刪除的時間復雜度僅為O(1)。ArrayList在插入數(shù)據(jù)時還需要更新索引（除了插入數(shù)組的尾部）。
- LinkedList需要更多的內存，因為ArrayList的每個索引的位置是實際的數(shù)據(jù)，而LinkedList中的每個節(jié)點中存儲的是實際的數(shù)據(jù)和前后節(jié)點的位置。也就是說，ArrayList在查找方面速度快。LinkedList在增刪速度快。
- ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結構，LinkedList基于鏈表的數(shù)據(jù)結構。 對于隨機訪問get和set，ArrayList覺得優(yōu)于LinkedList，因為LinkedList要移動指針。對于新增和刪除操作add和remove，LinedList比較占優(yōu)勢，因為ArrayList要移動數(shù)據(jù)
- 如果應用程序對數(shù)據(jù)有較多的隨機訪問，ArrayList對象要優(yōu)于LinkedList對象；如果應用程序有更多的插入或者刪除操作，較少的隨機訪問，LinkedList對象要優(yōu)于ArrayList對象；不過ArrayList的插入，刪除操作也不一定比LinkedList慢，如果在List靠近末尾的地方插入，那么ArrayList只需要移動較少的數(shù)據(jù)，而LinkedList則需要一直查找到列表尾部，反而耗費較多時間，這時ArrayList就比LinkedList要快。
到此這篇關于Java中的LinkedList集合詳解的文章就介紹到這了,更多相關LinkedList集合詳解內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
springboot工程，是沒有webapp文件夾的，靜態(tài)文件放在src/main/resources/static文件夾下即可，模板文件放在src/main/resources/templates下，本文給大家介紹springBoot快速訪問工程目錄下的靜態(tài)資源的相關知識，一起看看吧2021-06-06
消息的可靠性傳遞是指保證消息百分百發(fā)送到消息隊列中去，這篇文章主要介紹了RabbitMQ實現(xiàn)消息可靠性傳遞過程，感興趣想要詳細了解可以參考下文2023-05-05
這篇文章主要為大家詳細介紹了Java中的遞歸的實現(xiàn)以及應用，文中的示例代碼講解詳細，對我們學習Java有一定幫助，需要的可以參考一下2022-10-10
這篇文章主要介紹了Java Annotation Overview,需要的朋友可以參考下2014-02-02
Spring事務有可能會提交，回滾、掛起、恢復，所以Spring事務提供了一種機制，可以讓程序員來監(jiān)聽當前Spring事務所處于的狀態(tài)，這篇文章主要介紹了Spring底層事務原理,需要的朋友可以參考下2022-12-12
這篇文章主要介紹了Java面向對象編程（封裝/繼承/多態(tài)）實例解析的相關內容，具有一定參考價值，需要的朋友可以了解下。2017-10-10
Spring?Boot整合持久層之JPA多數(shù)據(jù)源
JPA（Java Persistence API）Java 持久化 API，是 Java 持久化的標準規(guī)范，Hibernate 是持久化規(guī)范的技術實現(xiàn)，而 Spring Data JPA 是在 Hibernate 基礎上封裝的一款框架2022-08-08
這篇文章主要介紹了Spring中@Cacheable注解的使用詳解,Spring框架提供了@Cacheable注解來輕松地將方法結果緩存起來,以便在后續(xù)調用中快速訪問,本文將詳細介紹@Cacheable注解的使用方法,并從源碼級別解析其實現(xiàn)原理,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了Java都有哪些創(chuàng)建線程的方法，文章分享Java創(chuàng)建線程得幾種方法及推薦使用哪種方法，下面詳細內容需要的小伙伴可以參考一下2022-05-05
springboot項目打成war包部署到tomcat遇到的一些問題
這篇文章主要介紹了springboot項目打成war包部署到tomcat遇到的一些問題,需要的朋友可以參考下2017-06-06