JDK源碼閱讀——LinkedList

2019-11-11 01:39:52

字體：大中小

供稿：網(wǎng)友

序

作為數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的兩種結(jié)構(gòu)，數(shù)組與鏈表，在java中都有對(duì)應(yīng)的實(shí)現(xiàn)——ArrayList與LinkedList。本文主要分析一下LinkedList中的比較重要的源碼。 LinkedList是實(shí)現(xiàn)了List與Deque的雙向鏈表。他不是線程安全的，在多線程情況下需要用戶手動(dòng)保證線程安全性。系統(tǒng)推薦使用下面的方法來保證線程安全。

List list = Collections.synchronizedList(new LinkedList(...));

Field

transient int size = 0; //頭結(jié)點(diǎn) transient Node<E> first; //尾節(jié)點(diǎn)transient Node<E> last;//節(jié)點(diǎn)本身是一個(gè)內(nèi)部類PRivate static class Node<E> { //節(jié)點(diǎn)內(nèi)容本身 E item; //下一個(gè)節(jié)點(diǎn) Node<E> next; //上一個(gè)節(jié)點(diǎn) Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

構(gòu)造器

//構(gòu)造一個(gè)普通的新鏈表對(duì)象 public LinkedList() { } //構(gòu)造一個(gè)新鏈表，并將入?yún)⒓蟖ppend到新鏈表中 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }//append的核心代碼在這里public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); //需要新增的結(jié)點(diǎn)個(gè)數(shù) int numNew = a.length; if (numNew == 0) return false; //聲明頭結(jié)點(diǎn)與尾節(jié)點(diǎn) Node<E> pred, succ; //從尾部開始appedn if (index == size) { succ = null; pred = last; } else { //從中間開始append,如圖1 succ = node(index); pred = succ.prev; }

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; }

上述循環(huán)的作用就是鏈表的插入操作，如圖2。不停的移動(dòng)pred，把輸入的集合全都append到鏈表尾部。