一蔓倍、簡述
我們知道奶栖，數(shù)據(jù)結(jié)構(gòu)中主要有兩種存儲結(jié)構(gòu)，分別是：順序存儲結(jié)構(gòu)（線性表）孽江、鏈式存儲結(jié)構(gòu)（鏈表）讶坯，在Java中，對這兩種結(jié)構(gòu)分別進行實現(xiàn)的類有：
- 順序存儲結(jié)構(gòu)：ArrayList岗屏、Vector辆琅、Stack
- 鏈式存儲結(jié)構(gòu)：LinkedList、Queue
二这刷、歸納
- 繼承了AbstractList抽象類婉烟，實現(xiàn)了List和Deque接口，底層基于雙向鏈表實現(xiàn)的崭歧，允許null的存在隅很。
- 實現(xiàn)了Cloneable, java.io.Serializable接口，所以支持復制(拷貝)、序列化屋彪。
- LinkedList中的元素就是一個個的節(jié)點，而真正的數(shù)據(jù)則存放在Node之中绒尊。
- 增和刪除操非承蠡樱快【時間復雜度：O(1)】，查和改操作相對較慢【時間復雜度：最快O(1)最慢O(n)】婴谱。
- LinkedList的操作單線安全蟹但，多線程不安全。
三谭羔、分析
1华糖、接口
在分析ArrayList源碼之前，我們先來看看集合的接口--List瘟裸。
public interface List<E> extends Collection<E> {
...
// 增
boolean add(E e);
void add(int index, E element);
// 刪
boolean remove(Object o);
E remove(int index);
// 改
E set(int index, E element);
// 查
E get(int index);
...
}
在上述接口中客叉，我只抽取了比較重要的幾個方法，然后以此為后續(xù)重點分析目標话告，其List接口對應的源碼中遠不止上述幾個方法兼搏，有興趣的同學可以自行翻閱。
2沙郭、成員變量
在LinkedList的源碼中,其成員變量并不多,所以在此把它們都一一列出佛呻。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
// 序列化唯一表示UID
private static final long serialVersionUID = 876323262645176354L;
// LinkedList的大小，其實就是其內(nèi)部維護的雙向鏈表存儲元素的數(shù)量
transient int size = 0;
// 頭結(jié)點病线，指向第一個節(jié)點的指針或引用吓著，默認為null
transient Node<E> first;
// 尾節(jié)點，指向最后一個節(jié)點的指針或引用氧苍，默認為null
transient Node<E> last;
...
}
3夜矗、構(gòu)造函數(shù)
構(gòu)造函數(shù)是一個類最常見的，同樣也是最常被使用到的让虐，接著我們分析LinkedList的兩個不同的構(gòu)造函數(shù)紊撕。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 無參的構(gòu)造函數(shù)
*/
public LinkedList() {
}
/**
* 有參構(gòu)造函數(shù)
* 構(gòu)造包含指定元素的列表集合
*
* @param c 集合元素
* @throws NullPointerException 如果c為null，則會拋出空指針異常
*/
public LinkedList(Collection<? extends E> c) {
// 指向無參的構(gòu)造函數(shù)
this();
addAll(c);
}
...
}
4赡突、內(nèi)部的Node節(jié)點
因為LinkedList是雙向鏈表对扶，故從下面的Node節(jié)點可以看出有兩個指針數(shù)據(jù)，一個指向上一個節(jié)點惭缰，一個指向下一個節(jié)點浪南；</br>
- 為什么Node這個類是靜態(tài)的？</br>
答案是：這跟內(nèi)存泄露有關(guān)漱受，Node類是在LinkedList類中的络凿，也就是一個內(nèi)部類，若不使用static修飾，那么Node就是一個普通的內(nèi)部類絮记，在java中摔踱，一個普通內(nèi)部類在實例化之后，默認會持有外部類的引用怨愤，這就有可能造成內(nèi)存泄露派敷。但使用static修飾過的內(nèi)部類（稱為靜態(tài)內(nèi)部類），就不會有這種問題撰洗，在Android中篮愉，有很多這樣的情況，如Handler的使用差导。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
private static class Node<E> {
// 存儲的元素
E item;
// 指向下一個節(jié)點
Node<E> next;
// 指向上一個節(jié)點
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
...
}
5试躏、增
LinkedList的增操作有兩種實現(xiàn)，分別為add(E e)和add(int index, E element)设褐，下面我們來分析其兩種實現(xiàn)冗酿。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 將指定的元素添加到此列表的末尾
*
* @param e 將要添加的元素
* @return 返回true標識添加成功
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 將指定的元素添加到指定的位置
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException 如果索引角標不合法，則拋出索引越界異常
*/
public void add(int index, E element) {
// 判斷index是否合法络断，不合法則拋出索引越界異常
checkPositionIndex(index);
// 判斷要添加的是否是最后一個索引位置
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 將元素e添加到鏈表最后
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
// 如果當前鏈表還沒有元素，則將當前元素賦值為first
if (l == null)
first = newNode;
else
l.next = newNode;
// 維護size
size++;
// 用來記錄LinkedList結(jié)構(gòu)性變化的次數(shù)
modCount++;
}
/**
* 將元素e插入到指定的index索引位置
*/
void linkBefore(E e, Node<E> succ) {
// 獲取原本index索引位置的元素的前節(jié)點
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
size++;
// 用來記錄LinkedList結(jié)構(gòu)性變化的次數(shù)
modCount++;
}
/**
* 返回指定元素索引處的(非空)節(jié)點
*/
Node<E> node(int index) {
// 它對index與集合長度的一半做比較项玛，來確定是在集合的前半段還是后半段進行查找貌笨，
// 從而達到節(jié)省一半的時間。
// size>>1相當于size除以2襟沮，這里的意思就是判斷index的位置在前半段還是后半段
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;
}
}
...
}
6锥惋、刪
LinkedList的刪操作有兩種實現(xiàn)，分別是remove(int index)和remove(Object o)开伏，下面我們來分析其兩種實現(xiàn)膀跌。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
**
* 刪除索引為index的元素并返回
*
* @param index 要刪除的索引
* @return 返回刪除的元素
* @throws IndexOutOfBoundsException 拋出索引角標越界異常
*/
public E remove(int index) {
// 判斷index是否合法，不合法則拋出索引越界異常
checkElementIndex(index);
return unlink(node(index));
}
/**
* 刪除元素o固灵，并且返回是否有效刪除
*
* @param o 元素將從此列表中刪除(如果存在)
* @return 如果存在該元素將其刪除并返回true捅伤，否則返回false
*/
public boolean remove(Object o) {
// 這里把空和非空進行區(qū)分，空的話用“==”判斷巫玻，非空用“equals”判斷
if (o == null) {
// 從頭節(jié)點開始遍歷檢索
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
// 獲取當前要刪除的節(jié)點丛忆，并將其傳入
unlink(x);
return true;
}
}
} else {
// 從頭節(jié)點開始遍歷檢索
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
// 獲取當前要刪除的節(jié)點，并將其傳入
unlink(x);
return true;
}
}
}
return false;
}
/**
* 斷開非空節(jié)點x的鏈接
*/
E unlink(Node<E> x) {
// 獲取當前節(jié)點的元素
final E element = x.item;
// 獲取當前節(jié)點的下一個節(jié)點
final Node<E> next = x.next;
// 獲取當前節(jié)點的上一個節(jié)點
final Node<E> prev = x.prev;
// 判斷當前節(jié)點的上一個節(jié)點是否為null仍秤，如果為null則代表x是頭結(jié)點
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 判斷當前節(jié)點的下一個節(jié)點是否為null熄诡，如果為null則代表x是尾結(jié)點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 將節(jié)點x置空
x.item = null;
// 維護size
size--;
// 用來記錄LinkedList結(jié)構(gòu)性變化的次數(shù)
modCount++;
return element;
}
...
}
7、改
LinkedList的改操作有一種實現(xiàn)诗力，對應的是set(int index, E element)凰浮，下面我們來分析這種實現(xiàn)。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 修改索引角標為index的元素值
*
* @param index 要修改的索引坐標
* @param element 修改后存儲的元素值
* @return 返回修改前的元素值
* @throws IndexOutOfBoundsException 拋出索引角標越界異常
*/
public E set(int index, E element) {
// 判斷index是否合法，不合法則拋出索引越界異常
checkElementIndex(index);
// 獲取索引為index的節(jié)點
Node<E> x = node(index);
// 獲取節(jié)點x的值
E oldVal = x.item;
// 將元素element賦值給節(jié)點x的item
x.item = element;
// 返回原本節(jié)點x的值
return oldVal;
}
...
}
8袜茧、查
LinkedList的查操作有一種實現(xiàn)菜拓，對應的是get(int index)，下面我們來分析這種實現(xiàn)惫周。
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 查找索引角標為index的元素值
*
* @param index 要修改的索引坐標
* @return 返回查找到的索引為index的元素值
* @throws IndexOutOfBoundsException 拋出索引角標越界異常
*/
public E get(int index) {
// 判斷index是否合法尘惧，不合法則拋出索引越界異常
checkElementIndex(index);
return node(index).item;
}
...
}
四、隊列
1递递、LinkedList源碼分析為什么會牽扯到Queue喷橙？
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
}
從上面的代碼中可以看到LinkedList實現(xiàn)了Deque，那么Deque又是什么呢登舞？不急咱們慢慢分析贰逾。
public interface Deque<E> extends Queue<E> { ... }
由此看出代碼中的Deque是Queue的一個子接口，它繼承了Queue菠秒。我們都知道隊列的特性是：先進先出疙剑，而Queue中的方法就是體現(xiàn)了這種特性。
public interface Queue<E> extends Collection<E> {
...
// 添加隊尾元素
boolean offer(E e);
// 刪除對頭元素
E poll();
// 獲取對頭元素
E peek();
...
}
那么我們再從上述幾個方法中再來看看LinkedList是如何實現(xiàn)的践叠。
2言缤、LinkedList對Queue的增操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 將元素e添加到列表的末尾
*
* @param e 將要添加的元素
* @return 返回true標識添加成功
*/
public boolean offer(E e) {
return add(e);
}
...
}
由上述代碼可以看出，在LinkedList中禁灼，隊列的offer(E e)方法實際上就是調(diào)用了LinkedList的#add(E e)方法管挟，而add(E e)方法已經(jīng)在最前面咱們分析過了，就是在鏈表的尾部添加一個元素弄捕。
3僻孝、LinkedList對Queue的刪操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 刪除隊列對頭的元素
*
* @return 返回對頭元素
*/
public E poll() {
// 頭結(jié)點
final Node<E> f = first;
// 判斷頭結(jié)點是否為null，因為可能還沒存入元素
return (f == null) ? null : unlinkFirst(f);
}
/**
* 刪除原本的頭結(jié)點守谓，刪除后維護好現(xiàn)有的鏈表
*/
private E unlinkFirst(Node<E> f) {
// 在前面已做魯棒性
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // 防止GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
...
}
4穿铆、LinkedList對Queue的查操作
public class LinkedList<E> extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable{
...
/**
* 獲取對頭的元素
*
* @return 返回對頭元素，如果對頭為null斋荞，則返回null荞雏，否則返回隊列頭部的元素
*/
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
...
}
