LinkedList的構造方法

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList實現了List、Deque接口,說明它有雙端隊列的特征，同時支持克隆，序列化。

我們都知道LinkedList是由鏈表實現的，下面是它的鏈表節點：

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

LinkedList的屬性

1、LinkedList對象實例的大小

transient int size = 0;

2、頭指針：指向LinkedList中的第一個元素

transient Node<E> first;

3、尾指針：指向LinkedList中的最后一個元素

transient Node<E> last;

為什么讓node都防止序列化呢？很簡單，如果A node序列化，那么A node的下一個節點B node也要序列化，B node序列化時，B node的上一個節點A node也要序列化，這樣就陷入了無限的循環之之中，所以必須手動序列化，也就是重寫readObject和writeObject，如果還是不明白，可以參考：Effective Java之考慮自定義的序列化模式(七十五)

LinkedList的構造方法

1、無參構造函數

無參構造函數，即構造一個空鏈表。

public LinkedList() {}

2、有參構造函數

public LinkedList(Collection<? extends E> c) {this();//調用無參構造方法構造一個空的鏈表addAll(c);}

這里能看出來它的ArrayList的一些不同之處，它沒有默認的大小，也沒有傳入默認大小的參數的構造方法，構造方法相對簡單。

這里有個addAll(c);不著急解釋，看到后面就知道了。

Add方法

public boolean add(E e) {linkLast(e);return true;} 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;elsel.next = newNode;size++;modCount++;}

節點鏈接再last節點之后，并處理了last節點可能為空的情況。如果為空，則first也應該是指向這個新節點newNode

既然上面有linkLast，LinkedList中也有linkFirst(E e),方法差不多，不再贅述。還有個方法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;elsepred.next = newNode;size++;modCount++;}

LinkedList還提供了addFirst和addLast方法。如下：

public void addFirst(E e) {linkFirst(e);}public void addLast(E e) {linkLast(e);}

addFirst(E e)函數是借助于linkFirst來實現的，而addLast(E e)是借助于linkLast來實現的。add(int index,E element)添加到指定位置用LinkBefore

addAll方法

public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);//索引有效性檢查，即檢查index>=0&&index<=sizeObject[] a = c.toArray();int numNew = a.length;if (numNew == 0)return false;Node<E> pred, succ;/*pred：用于表示即在此節點位置的后面插入新的節點succ：用于表示在此節點的前面位置插入節點，即插入之前此時此刻鏈表中的index位置的節點如果index==size，則在尾結點處插入否則：找到索引為index（從零開始）的位置節點*/if (index == size) {succ = null;pred = last;} else {succ = node(index);pred = succ.prev;}//將所有元素加入在pre指向之后for (Object o : a) {@SuppressWarnings("unchecked") E e = (E) o;Node<E> newNode = new Node<>(pred, e, null);//構造新的節點if (pred == null)//如果pred為null，則說明此時加入的為第一個結點first = newNode;elsepred.next = newNode;pred = newNode;}/*在尾結點加入時，pred所指向的就是last的位置，否則，則將pred與succ的指向要進行連接起來。*/if (succ == null) {last = pred;} else {pred.next = succ;succ.prev = pred;}size += numNew;//更改鏈表大小modCount++;//增加修改次數return true;}

方法很簡單，先找到index所在的節點，然后再這個節點的前面添加元素，如果這個節點的前面是空節點，那么這直接讓first指向集合開頭。

不知道大家都沒有發現LinkedList和ArrayList不同的地方，LinkedList添加一個集合modCount只加一，ArrayList的modCount加它加上的集合的大小。

其他方法

get和set方法很簡單，都是改變值的操作，相信大家不用看都應該知道怎么寫，這里就不再贅述了

remove方法其實跟add方法類似，LinkedList同樣封裝了一個方法：unlinkFirst，unlinkLast，unlinkBefore方法，下面展示unlinkFirst方法：

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 GCfirst = next;/*下面對next是否為空進行分支處理;如果為空，說明鏈表為空，即應該使得last=null;如果不為空，則將next的pre指向null。*/if (next == null) last = null;elsenext.prev = null;size--;modCount++;return element;}

remove的類似方法removeFirst,removeLast，remove(int index)，remove(Object object)其實都是調用這類封裝方法。

這都是非常不錯的封裝，相比于ArrayList，它用鏈表來實現，實現的思路非常清晰易懂。

總結

以上是生活随笔為你收集整理的容器源码分析之LinkedList(三)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。