java集合之LinkedList
摘要：
title: java集合之LinkedList
tags: java集合
author: 辰砂
一. LinkedList概述：
List 介面的連結列表實現。實現所有可選的列表操作，並且允許所有元素（包括 null）。除了實現 List 介面外，LinkedList 類還為...
title: java集合之LinkedList
tags: java集合
author: 辰砂
一. LinkedList概述：
List 介面的連結列表實現。實現所有可選的列表操作，並且允許所有元素（包括 null）。除了實現 List 介面外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將連結列表用作堆疊、佇列或雙端佇列。
注意，此實現不是同步的。如果不存在這樣的物件，則應該使用 Collections.synchronizedList 方法來“包裝”該列表。最好在建立時完成這一操作，以防止對列表進行意外的不同步訪問，如下所示：
List list = Collections.synchronizedList(new LinkedList(...));
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList 是一個繼承於AbstractSequentialList的雙向連結串列。它也可以被當作堆疊、佇列或雙端佇列進行操作。
LinkedList 實現 List 介面，能對它進行佇列操作。
LinkedList 實現 Deque 介面，即能將LinkedList當作雙端佇列使用。
LinkedList 實現了Cloneable介面，即覆蓋了函式clone()，能克隆。
LinkedList 實現java.io.Serializable介面，這意味著LinkedList支援序列化，能通過序列化去傳輸。
LinkedList 是非同步的
二.LinkedList的用法 (參考優秀博文)
public class LinkedListTest {
public static void main(String[] args) {
// 測試LinkedList的API
testLinkedListAPIs() ;
// 將LinkedList當作 LIFO(後進先出)的堆疊
useLinkedListAsLIFO();
// 將LinkedList當作 FIFO(先進先出)的佇列
useLinkedListAsFIFO();
}
/*
* 測試LinkedList中部分API
*/
private static void testLinkedListAPIs() {
String val = null;
//LinkedList llist;
//llist.offer("10");
// 新建一個LinkedList
LinkedList llist = new LinkedList();
//---- 新增操作 ----
// 依次新增1,2,3
llist.add("1");
llist.add("2");
llist.add("3");
// 將“4”新增到第一個位置
llist.add(1, "4");
System.out.println("\nTest \"addFirst(), removeFirst(), getFirst()\"");
// (01) 將“10”新增到第一個位置。失敗的話，丟擲異常！
llist.addFirst("10");
System.out.println("llist:"+llist);
// (02) 將第一個元素刪除。失敗的話，丟擲異常！
System.out.println("llist.removeFirst():"+llist.removeFirst());
System.out.println("llist:"+llist);
// (03) 獲取第一個元素。失敗的話，丟擲異常！
System.out.println("llist.getFirst():"+llist.getFirst());
System.out.println("\nTest \"offerFirst(), pollFirst(), peekFirst()\"");
// (01) 將“10”新增到第一個位置。返回true。
llist.offerFirst("10");
System.out.println("llist:"+llist);
// (02) 將第一個元素刪除。失敗的話，返回null。
System.out.println("llist.pollFirst():"+llist.pollFirst());
System.out.println("llist:"+llist);
// (03) 獲取第一個元素。失敗的話，返回null。
System.out.println("llist.peekFirst():"+llist.peekFirst());
System.out.println("\nTest \"addLast(), removeLast(), getLast()\"");
// (01) 將“20”新增到最後一個位置。失敗的話，丟擲異常！
llist.addLast("20");
System.out.println("llist:"+llist);
// (02) 將最後一個元素刪除。失敗的話，丟擲異常！
System.out.println("llist.removeLast():"+llist.removeLast());
System.out.println("llist:"+llist);
// (03) 獲取最後一個元素。失敗的話，丟擲異常！
System.out.println("llist.getLast():"+llist.getLast());
System.out.println("\nTest \"offerLast(), pollLast(), peekLast()\"");
// (01) 將“20”新增到第一個位置。返回true。
llist.offerLast("20");
System.out.println("llist:"+llist);
// (02) 將第一個元素刪除。失敗的話，返回null。
System.out.println("llist.pollLast():"+llist.pollLast());
System.out.println("llist:"+llist);
// (03) 獲取第一個元素。失敗的話，返回null。
System.out.println("llist.peekLast():"+llist.peekLast());
// 將第3個元素設定300。不建議在LinkedList中使用此操作，因為效率低！
llist.set(2, "300");
// 獲取第3個元素。不建議在LinkedList中使用此操作，因為效率低！
System.out.println("\nget(3):"+llist.get(2));
// ---- toArray(T[] a) ----
// 將LinkedList轉行為陣列
String[] arr = (String[])llist.toArray(new String[0]);
for(String str:arr) {
System.out.println("str:"+str);
}
// 輸出大小
System.out.println("size:"+llist.size());
// 清空LinkedList
llist.clear();
// 判斷LinkedList是否為空
System.out.println("isEmpty():"+llist.isEmpty()+"\n");
}
/**
* 將LinkedList當作 LIFO(後進先出)的堆疊
*/
private static void useLinkedListAsLIFO() {
System.out.println("\nuseLinkedListAsLIFO");
// 新建一個LinkedList
LinkedList stack = new LinkedList();
// 將1,2,3,4新增到堆疊中
stack.push("1");
stack.push("2");
stack.push("3");
stack.push("4");
// 列印“棧”
System.out.println("stack:"+stack);
// 刪除“棧頂元素”
System.out.println("stack.pop():"+stack.pop());
// 取出“棧頂元素”
System.out.println("stack.peek():"+stack.peek());
// 列印“棧”
System.out.println("stack:"+stack);
}
/**
* 將LinkedList當作 FIFO(先進先出)的佇列
*/
private static void useLinkedListAsFIFO() {
System.out.println("\nuseLinkedListAsFIFO");
// 新建一個LinkedList
LinkedList queue = new LinkedList();
// 將10,20,30,40新增到佇列。每次都是插入到末尾
queue.add("10");
queue.add("20");
queue.add("30");
queue.add("40");
// 列印“佇列”
System.out.println("queue:"+queue);
// 刪除(佇列的第一個元素)
System.out.println("queue.remove():"+queue.remove());
// 讀取(佇列的第一個元素)
System.out.println("queue.element():"+queue.element());
// 列印“佇列”
System.out.println("queue:"+queue);
}
三.原始碼解讀
1.資料結構
LinkedList 是一個雙向連結串列。內部類 Node 是 LinkedList 中的基本資料結構，包含當前節點值，上一個節點得引用，和下個節點的引用。
// 連結串列中有多少個節點，預設為 0
transient int size = 0;
// 頭節點
transient Node<E> first;
// 尾節點
transient Node<E> last;
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.構造方法
比較簡單，預設無參構造，和一個 Collection 引數的構造（ 將裡面元素按順序前後連線，修改節點個數，並且操作次數 + 1 ）。
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @paramc the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
3.新增方法ADD
// 尾部插入
public boolean add(E e) {
// 去為節點加
linkLast(e);
return true;
}
// 將指定的元素防止在連結串列的尾節點，以前的尾節點變成它前面的節點，如果上個尾節點為null，說明以前是的空連結串列。
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
// 新增一個，我們就需要把size增加
size++;
modCount++;
}
add(int index, E element)
public void add(int index, E element) {
// 邊界校驗
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 雙鏈表可以分別從 頭節點 或者尾節點開始遍歷，計算它是在前面一半，還是在後面的位置，決定遍歷方式。
// 這也是LinkedList 為什麼要使用雙向連結串列，提升了使用遊標操作連結串列的效率。
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;
}
}
/**
* Inserts element e before non-null Node succ.
*/
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++;
}
檢查索引是否越界，雖然 ListedList 中沒有索引概念；
如果 index 和 size 相同，則在尾節點上加上元素；
不相同的話，先去遍歷連結串列查詢到索引位置的節點，然後在它的前面插入節點。
1.s->prior=p->prior; 2. p->prior->next=s; 3. s->next=p; 4. p->prior=s;
4.獲取元素Get
public E get(int index) {
// 檢查索引越界；
// 跟上面的一樣，查詢該索引位置的節點，然後獲取它的元素。
checkElementIndex(index);
return node(index).item;
}
5.刪除元素Remove
public E remove() {
return removeFirst();
}
// 移除頭節點
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
// 引數 f 為頭節點
// 將頭節點指向 next 節點，如果 next節點 為 null 則連結串列 為 null ，連結串列大小減 1 ，修改次數記錄加 1.
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> 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;
}
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* Unlinks non-null node x.
*/
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;
// 如果本節點為頭節點，頭節點指向next
if (prev == null) {
first = next;
} else {
// 不是頭節點，則將前節點和後節點連線起來，然後刪掉本節點的引用 GC
prev.next = next;
x.prev = null;
}
// 如果是尾節點，則將尾節點指向前節點
if (next == null) {
last = prev;
} else {
// 連線，雙向連結串列，雙方都有引用，刪除自身的引用GC
next.prev = prev;
x.next = null;
}
// 刪除自身 GC
x.item = null;
size--;
modCount++;
return element;
}
// 遍歷 equals 找出 node，然後呼叫 unlink(Node<E> x)
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;
}
6.更新元素Set
/**
*有索引，第一件事去檢查索引是否越界；根據索引找出 node；
*替換 node 的元素，返回 該索引位置 Node 的舊元素的值。
*注意，Set 方法不增加LinkedList 的修改次數
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
7.清空clear()
//釋放所有的元素，讓他們直接無引用，垃圾回收器發現這些 node 元素是不可達的時候，釋放記憶體。 // 資料恢復預設；修改次數記錄加一。 public void clear() { // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit //more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
四、ArrayList和LinkedList比較
-
ArrayList的實現是基於陣列，LinkedList的實現是基於雙向連結串列。
-
對於隨機訪問，ArrayList優於LinkedList
-
對於插入和刪除操作，LinkedList優於ArrayList
-
LinkedList比ArrayList更佔記憶體，因為LinkedList的節點除了儲存資料，還儲存了兩個引用，一個指向前一個元素，一個指向後一個元素。
參考
https://blog.wuwii.com/java-linkedlist.html#more
https://www.cnblogs.com/skywang12345/p/3308807.html