LinkedList里面涉及到的一些操作，非常細(xì)致，以避免出現(xiàn)的空指針，理解后對(duì)于其優(yōu)點(diǎn)與確定會(huì)有一個(gè)更加整體的認(rèn)識(shí)吧。
繼承關(guān)系圖(對(duì)比ArrayList)
元素的存儲(chǔ)結(jié)構(gòu)
// 典型的鏈表結(jié)構(gòu)
private static class Node<E> {E item;// 存儲(chǔ)元素Node<E> next;// 指向上一個(gè)元素Node<E> prev;// 指向下一個(gè)元素Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}
transient int size = 0;//當(dāng)前列表的元素個(gè)數(shù)
/*** Pointer to first node.* Invariant: (first == null && last == null) ||* ? ? ? ? ? ?(first.prev == null && first.item != null)*/
transient Node<E> first;// 第一個(gè)元素
/*** Pointer to last node.* Invariant: (first == null && last == null) ||* ? ? ? ? ? ?(last.next == null && last.item != null)*/
transient Node<E> last;// 最后一個(gè)元素
public LinkedList() {}//無(wú)參構(gòu)造函數(shù)
public LinkedList(Collection<? extends E> c) {this();addAll(c);//將c中的元素都添加到此列表中
}
public boolean addAll(Collection<? extends E> c) {return addAll(size, c);//此時(shí) size == 0
}
public boolean addAll(int index, Collection<? extends E> c) {// 檢查位置是否合法 位置是[0,size]，注意是閉區(qū)間 否則報(bào)異常checkPositionIndex(index);Object[] a = c.toArray();// 得到一個(gè)元素?cái)?shù)組int numNew = a.length;// c中元素的數(shù)量if (numNew == 0)return false;// 沒(méi)有元素，添加失敗// 主要功能是找到第size個(gè)元素的前驅(qū)和后繼。得到此元素需要分情況討論。// 這段代碼是各種情況的總和，可能有一點(diǎn)點(diǎn)容易懵逼。Node<E> pred, succ;// 前驅(qū)與后繼if (index == size) {// 如果位置與當(dāng)前的size相同succ = null;// 無(wú)后繼pred = last;// 前驅(qū)為last，即第size個(gè)元素(最后一個(gè)元素)} else {// 若與size不同，即index位于[0, size)之間succ = node(index);// 后繼為第index個(gè)元素pred = succ.prev;// 前驅(qū)為后繼的前驅(qū)}// 后文有詳細(xì)的圖片說(shuō)明// 開始逐個(gè)插入for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;// 新建一個(gè)以pred為前驅(qū)、null為后繼、值為e的節(jié)點(diǎn)Node<E> newNode = new Node<>(pred, e, null);if (pred == null)// 前驅(qū)為空，則此節(jié)點(diǎn)被當(dāng)做列表的第一個(gè)節(jié)點(diǎn)first = newNode;else// 規(guī)避掉了NullPointerException，感覺又達(dá)到了目的，又實(shí)現(xiàn)了邏輯pred.next = newNode;// 不為空，則將前驅(qū)的后繼改成當(dāng)前節(jié)點(diǎn)pred = newNode;// 將前驅(qū)改成當(dāng)前節(jié)點(diǎn)，以便后續(xù)添加c中其它的元素}// 至此，c中元素已添加到鏈表上，但鏈表中從size開始的那些元素還沒(méi)有鏈接到列表上// 此時(shí)就需要利用到之前找出來(lái)的succ值，它是作為這個(gè)c的整體后繼if (succ == null) {// 如果后繼為空，說(shuō)明無(wú)整體后繼last = pred;// c的最后一個(gè)元素應(yīng)當(dāng)作為列表的尾元素} else {// 有整體后繼pred.next = succ;// pred即c中的最后一個(gè)元素，其后繼指向succ，即整體后繼succ.prev = pred;// succ的前驅(qū)指向c中的最后一個(gè)元素}// 添加完畢，修改參數(shù)size += numNew;modCount++;return true;
}
Node<E> node(int index) {// assert isElementIndex(index);// 這個(gè)地方很有意思。視其與中值得差距，覺得從前遍歷還是從后遍歷。if (index < (size >> 1)) {Node<E> x = first;// 循環(huán)index次 迭代到所需要的元素for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;// 循環(huán)size-1-index次for (int i = size - 1; i > index; i--)x = x.prev;return x;}
}
public class Main {public static void main(String[] args) {List<String> list = new LinkedList<>(Arrays.asList("1", "2", "3"));System.out.println(list.toString());list.addAll(2, Arrays.asList("4", "5"));System.out.println(list.toString());list.addAll(0, Arrays.asList("6", "7"));System.out.println(list.toString());}
}
---
[1, 2, 3]
[1, 2, 4, 5, 3]
[6, 7, 1, 2, 4, 5, 3]
將e鏈接成列表的第一個(gè)元素
private void linkFirst(E e) {final Node<E> f = first;// 前驅(qū)為空，值為e，后繼為ffinal Node<E> newNode = new Node<>(null, e, f);first = newNode;// first指向newNode// 此時(shí)的f有可能為nullif (f == null)// 若f為空，則表明列表中還沒(méi)有元素last = newNode;// last也應(yīng)該指向newNodeelsef.prev = newNode;// 否則，前first的前驅(qū)指向newNodesize++;modCount++;
}
后續(xù)狀態(tài)：
void linkLast(E e) {final Node<E> l = last;// 找到最后一個(gè)節(jié)點(diǎn)// 前驅(qū)為前l(fā)ast，值為e，后繼為nullfinal Node<E> newNode = new Node<>(l, e, null);last = newNode;// last一定會(huì)指向此節(jié)點(diǎn)if (l == null)// 最后一個(gè)節(jié)點(diǎn)為空，說(shuō)明列表中無(wú)元素first = newNode;// first同樣指向此節(jié)點(diǎn)elsel.next = newNode;// 否則，前l(fā)ast的后繼指向當(dāng)前節(jié)點(diǎn)size++;modCount++;
}
void linkBefore(E e, Node<E> succ) {// assert succ != null;final Node<E> pred = succ.prev; // 找到succ的前驅(qū)// 前驅(qū)為pred，值為e，后繼為succfinal Node<E> newNode = new Node<>(pred, e, succ);// 將succ的前驅(qū)指向當(dāng)前節(jié)點(diǎn)succ.prev = newNode;if (pred == null)// pred為空，說(shuō)明此時(shí)succ為首節(jié)點(diǎn)first = newNode;// 指向當(dāng)前節(jié)點(diǎn)elsepred.next = newNode;// 否則，將succ之前的前驅(qū)的后繼指向當(dāng)前節(jié)點(diǎn)size++;modCount++;
}
?public boolean add(E e) {linkLast(e);return true;}// 只有這個(gè)是有一點(diǎn)邏輯的public void add(int index, E element) {checkPositionIndex(index);if (index == size)// 為最后一個(gè)節(jié)點(diǎn)，當(dāng)然是添加到最后一個(gè)~linkLast(element);elselinkBefore(element, node(index));}public void addFirst(E e) {linkFirst(e);}public void addLast(E e) {linkLast(e);}
刪除首節(jié)點(diǎn)
private E unlinkFirst(Node<E> f) {// assert f == first && f != null;別忽略這里的斷言final E element = f.item;// 取出首節(jié)點(diǎn)中的元素final Node<E> next = f.next;// 取出首節(jié)點(diǎn)中的后繼f.item = null;f.next = null; // help GCfirst = next;// first指向前first的后繼，也就是列表中的2號(hào)位if (next == null)// 如果此時(shí)2號(hào)位為空，那么列表中此時(shí)已無(wú)節(jié)點(diǎn)last = null;// last指向nullelsenext.prev = null;// 首節(jié)點(diǎn)無(wú)前驅(qū)size--;modCount++;return element;// 返回首節(jié)點(diǎn)保存的元素值
}
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;別忽略這里的斷言
final E element = l.item;// 取出尾節(jié)點(diǎn)中的元素
final Node<E> prev = l.prev;// 取出尾節(jié)點(diǎn)中的后繼
l.item = null;
l.prev = null; // help GC
last = prev;// last指向前l(fā)ast的前驅(qū)，也就是列表中的倒數(shù)2號(hào)位
if (prev == null)// 如果此時(shí)倒數(shù)2號(hào)位為空，那么列表中已無(wú)節(jié)點(diǎn)first = null;// first指向null
elseprev.next = null;// 尾節(jié)點(diǎn)無(wú)后繼
size--;
modCount++;
return element;// 返回尾節(jié)點(diǎn)保存的元素值
}
// x即為要?jiǎng)h除的節(jié)點(diǎn)
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;// 保存x的元素值
final Node<E> next = x.next;// 保存x的后繼
final Node<E> prev = x.prev;// 保存x的前驅(qū)if (prev == null) {// 前驅(qū)為null，說(shuō)明x為首節(jié)點(diǎn)first = next;// first指向x的后繼
} else {prev.next = next;// x的前驅(qū)的后繼指向x的后繼，即略過(guò)了xx.prev = null;// x.prev已無(wú)用處，置空引用
}if (next == null) {// 后繼為null，說(shuō)明x為尾節(jié)點(diǎn)last = prev;// last指向x的前驅(qū)
} else {next.prev = prev;// x的后繼的前驅(qū)指向x的前驅(qū)，即略過(guò)了xx.next = null;// x.next已無(wú)用處，置空引用
}x.item = null;// 引用置空
size--;
modCount++;
return element;// 返回所刪除的節(jié)點(diǎn)的元素值
}
public E removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);
}
public E removeLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return unlinkLast(l);
}
// 遍歷列表中所有的節(jié)點(diǎ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;
}
public E remove(int index) {checkElementIndex(index);return unlink(node(index));
}
public E set(int index, E element) {checkElementIndex(index);Node<E> x = node(index);// 獲取到需要修改元素的節(jié)點(diǎn)E oldVal = x.item;// 保存之前的值x.item = element;// 修改return oldVal;// 返回修改前的值}
查詢?cè)?通過(guò)位置，循環(huán)index次，獲取到節(jié)點(diǎn)，然后返回該節(jié)點(diǎn)中元素的值public E get(int index) {checkElementIndex(index);return node(index).item;// 獲取節(jié)點(diǎn)，并返回節(jié)點(diǎn)中的元素值
}
還有兩個(gè)獲取首尾節(jié)點(diǎn)的元素的方法：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;
}
獲取元素位置
從0開始往后遍歷public int indexOf(Object o) {int index = 0;if (o == null) {// null時(shí)分開處理for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)// 說(shuō)明找到return index;// 返回下標(biāo)index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))// 說(shuō)明找到return index;// 返回下標(biāo)index++;}}return -1;// 未找到，返回-1
}
從size - 1開始遍歷。基本操作與上述操作類似，只是起始位置不同。public int lastIndexOf(Object o) {int index = size;if (o == null) {for (Node<E> x = last; x != null; x = x.prev) {index--;if (x.item == null)return index;}} else {for (Node<E> x = last; x != null; x = x.prev) {index--;if (o.equals(x.item))return index;}}return -1;
}
// 下標(biāo)，保證數(shù)組訪問(wèn)不越界。
private boolean isElementIndex(int index) {return index >= 0 && index < size;
}
// 位置
private boolean isPositionIndex(int index) {return index >= 0 && index <= size;
}
?
總結(jié)
以上是生活随笔 為你收集整理的LinkedList源码阅分析 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
