public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
1.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;
}
}
Node是LinkedList的靜态内部類，從節點的結構可知，LinkedList是通過雙向連結清單實作的，是不是雙向循環連結清單呢？等會代碼中就知道了。
2.成員變量
//連結清單元素的的長度
transient int size = 0;
//連結清單的頭結點
transient Node<E> first;
//連結清單的尾結點
transient Node<E> last;
頭尾節點的作用在哪裡呢？這個在Node<E> node(int index)裡面就會提到，這樣可能是為了操作方面，node方法會判斷index在前半部分還是後半部分，進而減少搜尋的複雜度，前半部分用first周遊，後半部分用last周遊。
3.、構造方法
//構造一個空的連結清單
public LinkedList() {
}
//先構造一個空表，然後将集合使用addAll方法添加進連結清單中
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
addAll方法放到後面分析。
思考：為什麼LinkedList沒有提供像ArrayList裡面的ArrayList(int initialCapacity)構造指定大小的list的構造方式？
因為ArrayList的這種構造方式，可以知道需要向系統申請多少個連續的空間，進而構造指定空間的數組，這樣可以避免空間的浪費；但是LinkedList的空間可連續可不連續，并且動态增加元素很輕松，按照需要add就行了。
4.添加元素
//将指定元素連接配接到表尾，隻傳回true？？因為隻要空間配置設定足夠，就不會添加失敗
//當空間不夠的時候，記憶體溢出，抛出OOM
public boolean add(E e) {
linkLast(e);
return true;
}
//将e添加到連結清單的尾部
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++;
modCount++;
}
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
具體過程如下：
①暫存連結清單舊的尾節點l
②建立一個新節點，prev = l，item=e，next = null；
③新節點指派為新的尾節點
④判斷原來尾結點是否為空（連結清單是否為空）
4.1如果為空，讓頭結點指向新節點，即當隻有一個節點，頭尾結點指向同一個節點
4.2如果不為空，讓舊的尾節點next指向新的節點
⑤長度加1
大緻思路：
①建構一個新節點
②将新節點作為新的尾節點，如果原來尾節點為null，說明空連結清單，則将新節點作為頭結點，即頭結點=尾節點=新節點，如果不為空，将原來尾節點next=新節點
③增加連結清單長度
此時可以知道，新節點的next=null，即新的尾節點的next=null，那麼由此可見，LinkedList隻是雙向連結清單不是雙向循環連結清單
//上述過程已描述，不再贅述
public void addLast(E e) {
linkLast(e);
}
//将元素連接配接到表頭
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
過程分析：
①暫存連結清單舊的頭節點f
②建立一個新節點，prev = null，item=e，next = f；
③新節點指派為新的頭節點
④判斷原來頭結點是否為空（連結清單是否為空）
4.1如果為空，讓尾結點指向新節點，即當隻有一個節點，頭尾結點指向同一個節點
4.2如果不為空，讓舊的頭節點prev指向新的節點
⑤長度加1
大緻思路：
--建立一個新節點
--将新節點作為新的頭結點，如果原來頭結點為空，說明空連結清單，那麼頭結點=尾節點=新節點，如果不是，那麼将之前的頭結點的prev指向新節點
| //push方法，對比入棧方法，往頭結點添加元素 public void push(E e) { addFirst(e); } //添加元素到連結清單尾部，内部就是調用add（e） public boolean offer(E e) { return add(e); } //添加元素到連結清單頭部 public boolean offerFirst(E e) { addFirst(e); return true; } //添加元素到末尾 public boolean offerLast(E e) { addLast(e); return true; } //添加指定元素到指定位置 public void add(int index, E element) { checkPositionIndex(index);//檢查是否越界 if (index == size)//如果等于size，則直接調用插入表尾方法 linkLast(element); else//如果不在表尾，在index對應的節點前插入元素，該方法後面詳解 linkBefore(element, node(index)); } //如果isPositionIndex為false抛出數組越界異常 private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //檢查index是否在0-size中 private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //傳回指定index處的非空節點 Node<E> node(int index) { // assert isElementIndex(index); 這裡思想很巧妙，如果index在連結清單前半部分，從first往後找，否則，從last往前找 if (index < (size >> 1)) {//判斷index是否在前半部分 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; } } //在非空節點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++; } ①記錄succ的前一個節點 ②産生新的節點，prev=pred，item=e，next=succ ③succ的prev指向新節點 ④判斷succ前一個節點pred是否為空 4.1 如果為空，即succ為連結清單的頭結點，first指向新的節點作為頭結點 4.2 如果不為空，pred的next指向新的節點 ⑤長度加1 |
| //按照指定集合的疊代器傳回的順序将指定集合中的所有元素追加到此清單的末尾。 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //将指定集合中的所有元素插入到此清單中，從指定的位置開始 public boolean addAll(int index, Collection<? extends E> c) { //①判斷是否越界 checkPositionIndex(index); //②将集合轉換為數組 Object[] a = c.toArray(); //③記錄需要插入的集合元素個數 int numNew = a.length; //④如果元素個數為0，直接傳回false if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { //找到index位置的節點，指派給succ，succ節點之前是pred， //即在succ與pred之間插入資料 succ = node(index); pred = succ.prev; } //⑥循環将集合中所有元素連接配接到pred後面，過程與succ無關，即結束後 //新插入的最後一個節點的next=null；還需要進行連結 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); //如果pred為空，說明succ為頭結點或者連結清單為空，那麼将newNode作為新的頭結點 if (pred == null) first = newNode; //如果不為空就讓pred的next指向newNode else pred.next = newNode; //newNode作為新的pred pred = newNode; } //⑦此時就是為了連結，判斷succ是否為空 7.1如果為空，說明最後一個插入的元素（現在是pred）就是尾節點 7.2如果不為空，說明隻要和succ連結即可 if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } //⑧連結清單長度加numNew size += numNew; modCount++; return true; } |
5.删除元素
| //移除連結清單的第一個節點 public E remove() { return removeFirst(); } //移除連結清單第一個節點 public E removeFirst() { final Node<E> f = first; //注意：如果是空連結清單，抛異常沒有該元素 if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } //将第一個節點删掉，f就是first private E unlinkFirst(Node<E> f) { // assert f == first && f != null; //①記錄第一個節點的資料值 final E element = f.item; //②記錄下一個節點 final Node<E> next = f.next; //③将第一個節點置空 幫助回收GC f.item = null; f.next = null; // help GC //④将下一個節點作為新的頭結點 first = next; //⑤如果下一個為空，表示first就是唯一一個元素，删除後成空表 //如果不為空，就将下一個節點的prev=null if (next == null) last = null; else next.prev = null; //⑥連結清單長度-1 size--; modCount++; return element; } //移除指定位置元素 public E remove(int index) { checkElementIndex(index); //node(index)找到index處的節點 return unlink(node(index)); } //移除節點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; //②前一個節點是否為空 2.1如果為空，x為頭結點，将x.next作為新的頭結點 2.2如果不為空，前一個節點的next指針指向x的下一個節點 if (prev == null) { first = next; } else { prev.next = next; x.prev = null; } //③判斷x後一個節點是否為空 3.1如果為空，說明x節點是尾節點，讓x的prev稱為新的尾節點 3.2如果不為空，将x的next的prev指向x的prev if (next == null) { last = prev; } else { next.prev = prev; x.next = null; } //④x節點資料值清空 x.item = null; //⑤連結清單長度-1 size--; modCount++; return element; } //從連結清單中删除第一次出現的o對象，不管o是否為null //①判斷o是否為空 //1.1如果為空，找到第一個資料值為null的節點，進行删除 //1.2如果非空找到第一個與o的資料值相等的節點 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; } //從連結清單中删除第一次出現的指定元素o，内部調用remove(object) public boolean removeFirstOccurrence(Object o) { return remove(o); } //删除連結清單的最後一個元素并傳回 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } //移除連結清單的最後一個元素，l為last private E unlinkLast(Node<E> l) { // assert l == last && l != null; //①記錄尾節點的資料值、以及前一個節點 final E element = l.item; final Node<E> prev = l.prev; //②将尾節點置為空 友善GC l.item = null; l.prev = null; // help GC //③指定新的尾節點，為l的prev last = prev; //④判斷prev是否為null //4.1為空說明該表隻有一個節點last，删除之後，為空表 //4.2不為空，就将l的前一個節點的next置為null if (prev == null) first = null; else prev.next = null; //⑤連結清單長度-1 size--; modCount++; //⑦傳回之前的尾節點的資料 return element; } |
| //從連結清單中删除最後一次出現o的指定元素o public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } //擷取第一個元素的同時删除第一個元素，當連結清單無節點時，不會報錯 public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //擷取第一個元素的同時删除第一個元素，當連結清單無節點時，會報錯 public E pop() { return removeFirst(); } |
6.修改元素
public E set(int index, E element) {
//①入參檢測
checkElementIndex(index);
//②找到index處節點
Node<E> x = node(index);
//③儲存目前節點舊值
E oldVal = x.item;
//④替換新值
x.item = element;
return oldVal;
}
7.查詢元素
//得到連結清單的第一個元素
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//得到指定索引的元素
public E get(int index) {
//①入參檢驗
checkElementIndex(index);
//②擷取指定索引處節點資料值
return node(index).item;
}
//得到第一個元素
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//得到最後一個元素
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
8.周遊
| //獲得listIterator疊代器 public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } //實作了ListIterator接口 private class ListItr implements ListIterator<E> { //上一次傳回的節點 private Node<E> lastReturned; //下一個節點 private Node<E> 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(); //②将本次通路到的next節點指派為lastReturned lastReturned = next; //③next後移 next = next.next; //④索引++； nextIndex++; //⑤傳回本次的值 return lastReturned.item; } //是否還有前一個元素，nextIndex是否大于0 public boolean hasPrevious() { return nextIndex > 0; } //擷取前一個元素 public E previous() { checkForComodification(); //①如果沒有前一個元素，則抛異常 if (!hasPrevious()) throw new NoSuchElementException(); //②next==null表明目前節點就是尾節點的next， //故把next設定為last， //如果next不是null，那就指向将next指向next之前 lastReturned = next = (next == null) ? last : next.prev; //③索引值-1，傳回目前last對應的元素 nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } //移除目前周遊到的元素 public void remove() { checkForComodification(); //①移除目前周遊到的元素，如果為空，直接抛異常 if (lastReturned == null) throw new IllegalStateException(); //②記錄目前節點的下一個節點 Node<E> lastNext = lastReturned.next; //③移除目前節點 unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; expectedModCount++; } |
分析為什麼
| //設定目前正在周遊的值 public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } //添加一個值 public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } //循環，往後周遊，每周遊一個節點就回調目前節點資料值 public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); while (modCount == expectedModCount && nextIndex < size) { action.accept(next.item); lastReturned = next; next = next.next; nextIndex++; } checkForComodification(); } |
9.總結
①底層是雙向連結清單的存儲資料，并記錄了頭結點和尾節點
②添加元素非常快，如果添加頭部和尾部更快，因為已經有了頭尾節點，如果添加道中間，需要先找到索引處的元素
③周遊的時候，建議采用forEach周遊，這樣可以在每次擷取下一個元素時都非常輕松，如果是通過for和get進行周遊，效率比較低