經(jīng)常為了面試要記住LinkedList和ArrayList的區(qū)別，比如存取速度的比較命咐。如果不了解他們的實現(xiàn)方式篡九，不看源碼，記住了也是死記硬背醋奠，容易忘記榛臼，沒有太大的意義伊佃。這里講的是LinkedList，暫時不講ArrayList沛善，從源碼了解LinkedList的實現(xiàn)方式以及操作方法的實現(xiàn)航揉，才能更全面了解LinkedList。
LinkedList是基于雙向鏈表的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的金刁，所以必須要知道掌握雙向鏈表這種數(shù)據(jù)結(jié)構(gòu)迷捧，如果對雙向鏈表不了解的話得先去學(xué)一下，比較容易理解的一種數(shù)據(jù)結(jié)構(gòu)胀葱。學(xué)習(xí)了雙向鏈表看LinkedList的源碼會更輕松一些漠秋，從 源碼了解LinkedList的性質(zhì)，才能更加了解LinkedList抵屿，知道在什么場合更加適合使用LinkedList庆锦。別啰嗦了，看源碼：
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Queue<E>, Cloneable, Serializable ｛
....
｝
LinkedList可以指定一個泛型（一般我們都會這么做）轧葛，具有多個實現(xiàn)搂抒，源碼大部分邏輯都是在實現(xiàn)這些接口的方法，從它們的名字我們可以看出除了可以當(dāng)作鏈表來操作外尿扯，它還可以當(dāng)作棧求晶，隊列和雙端隊列來使用。
來看構(gòu)造函數(shù)
//記錄LinkedList的大小衷笋，即LinkedList有多少個節(jié)點（或者說元素）
transient int size = 0;
//一個空的節(jié)點
transient Link<E> voidLink;
/**
* Constructs a new instance of {@code LinkedList} that holds all of the
* elements contained in the specified {@code collection}. The order of the
* elements in this new {@code LinkedList} will be determined by the
* iteration order of {@code collection}.
*
* @param collection
* the collection of elements to add.
*/
//這個帶參數(shù)的構(gòu)造函數(shù)的this()方法是調(diào)用下面的那個構(gòu)造函數(shù)芳杏，之后將參數(shù)collection跟voidLink（一個空節(jié)點，在第二個構(gòu)造函數(shù)里創(chuàng)建出來的）
//鏈接起來辟宗，addAll(collection)后面講解
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
/**
* Constructs a new empty instance of {@code LinkedList}（創(chuàng)建一個空的實例）
*/
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
//創(chuàng)建節(jié)點的靜態(tài)內(nèi)部類
private static final class Link<ET> {
//ET其實就是E這個泛型爵赵，從上面的構(gòu)造函數(shù)可以看出，這個字段就是元素
ET data;
//這兩個字段分別是當(dāng)前節(jié)點的頭和尾泊脐，分布存儲的是前一個節(jié)點和后一個節(jié)點空幻，雙向鏈表數(shù)據(jù)結(jié)構(gòu)的每個節(jié)點都是有這三個東西組成的
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
從第二個構(gòu)造函數(shù)我們知道new出一個LinkedList的時候，這個實例里面只有一個空的節(jié)點voidLink 容客，一般我們會有個add(int location, E object)函數(shù)添加元素到指定位置秕铛，所以接著看add(E object)函數(shù)添加元素到最后一個節(jié)點的后面，addAll(int location, Collection<? extends E> collection)函數(shù)添加Collection到指定位置缩挑，addAll(Collection<? extends E> collection)函數(shù)添加Collection到最后一個節(jié)點的后面但两。addFirst(E object)添加元素到第一個節(jié)點的前面，addLast(E object)添加元素到最后一個節(jié)點后面调煎。這些是所有添加元素的方法镜遣。分別看下他們的邏輯，都是相似的。理解了其中一個其他都好理解悲关。
/**
* Inserts the specified object into this {@code LinkedList} at the
* specified location. The object is inserted before any previous element at
* the specified location. If the location is equal to the size of this
* {@code LinkedList}, the object is added at the end.
*上面的意思就是將指定的object 插入到指定的位置谎僻，之前位置的object 以及它后面的object 的位置的都會加1
*注意最后一句話的意思是如果這個LinkedList的size等于location ，那么意思就是插入到最后一個位置寓辱。不允許location >size,location<0
*
* @param location
* the index at which to insert.
* @param object
* the object to add.
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location > size()}
*/
@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
方法注釋可以了解到大概艘绍，分析代碼才能更細節(jié)的了解，可以看到location 必須大于等于0且小于等于sise秫筏，否則會拋出異常诱鞠，滿足條件后需要創(chuàng)建一個節(jié)點引用，先指向voidLink這個空節(jié)點这敬，因為我們需要借助voidLink和size才能找到一個目標(biāo)節(jié)點航夺，該目標(biāo)節(jié)點起著關(guān)鍵的作用，先看if和else語句崔涂，判斷插入位置區(qū)域鏈表的哪一邊阳掐，如果是左邊的話則進入if條件的for循環(huán)從第一個位置開始找目標(biāo)節(jié)點，首先我們必須知道voidLink.next永遠的是當(dāng)前的第一個節(jié)點冷蚂，等看完了所有添加元素的函數(shù)邏輯的時候就明白了缭保。如果進入else條件，邏輯也是一樣的蝙茶，只是從尾部開始查找目標(biāo)節(jié)點艺骂。找到目標(biāo)節(jié)點之后就很簡單了，把目標(biāo)節(jié)點的前一個節(jié)點的next指向newLink （新插入節(jié)點）隆夯，目標(biāo)節(jié)點的previous 指向newLink 钳恕，這樣就完成了拼接，目標(biāo)節(jié)點的位置被新節(jié)點占據(jù)著吮廉，著目標(biāo)節(jié)點以及后面的節(jié)點的位置都各自加1苞尝，此時我們還要加size+1，modCount+1只是一個統(tǒng)計修改的次數(shù)宦芦。邏輯還是比較簡單的，后面的幾個添加元素的方法都是大同小異的轴脐。
add(E object)在尾部添加節(jié)點调卑，更加簡單目標(biāo)節(jié)點哦度不用找，因為voidLink.previous就是最后一個節(jié)點大咱，跟voidLink.next永遠的是當(dāng)前的第一個節(jié)點永遠是第一個節(jié)點相呼應(yīng)：
/**
* Adds the specified object at the end of this {@code LinkedList}.
*
* @param object
* the object to add.
* @return always true
*/
@Override
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous;
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
其他幾個添加元素的函數(shù)都是按照這種套路執(zhí)行的恬涧，不必每一個都進行分析了，但每個人都有必要去看一遍的碴巾。
與添加對應(yīng)的方法就是刪除了溯捆，remove(int location)，removeFirst()厦瓢，removeLast()提揍，方法名可以看出什么意思了啤月，刪除的套路前半部分也是一樣的，目標(biāo)節(jié)點劳跃，然后根據(jù)目標(biāo)節(jié)點找到他前后的節(jié)點谎仲，讓前一個節(jié)點的next指向后一個節(jié)點，后一個節(jié)點的previous指向前一個節(jié)點刨仑。還有一個remove(Object object)方法收回復(fù)雜一些郑诺，后面單獨講，先看remove(int location)（removeFirst()杉武，removeLast()與removeFirst()辙诞，removeLast()套路相似）
/**
* Removes the object at the specified location from this {@code LinkedList}.
*
* @param location
* the index of the object to remove
* @return the removed object
* @throws IndexOutOfBoundsException
* if {@code location < 0 || location >= size()}
*/
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
if (location < (size / 2)) {
for (int i = 0; i <= location; i++) {
link = link.next;
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> next = link.next;
previous.next = next;
next.previous = previous;
size--;
modCount++;
return link.data;
}
throw new IndexOutOfBoundsException();
}
remove(Object object)源碼
@Override
public boolean remove(Object object) {
return removeFirstOccurrenceImpl(object);
}
private boolean removeFirstOccurrenceImpl(Object o) {
Iterator<E> iter = new LinkIterator<E>(this, 0);
return removeOneOccurrence(o, iter);
}
private boolean removeOneOccurrence(Object o, Iterator<E> iter) {
while (iter.hasNext()) {
E element = iter.next();
if (o == null ? element == null : o.equals(element)) {
iter.remove();
return true;
}
}
return false;
}
從源碼看到的調(diào)用到最后removeOneOccurrence(Object o, Iterator<E> iter)函數(shù)的iter.remove()防止執(zhí)行了移除工作，這個方法里面調(diào)用了LinkIterator的hasNext()轻抱、next()飞涂、remove()三個方法，進去看他們的源碼看下到底做了什么工作
public boolean hasNext() {
return link.next != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
LinkedList.Link<ET> next = link.next;
if (next != list.voidLink) {
lastLink = link = next;
pos++;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public void remove() {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
Link<ET> next = lastLink.next;
Link<ET> previous = lastLink.previous;
next.previous = previous;
previous.next = next;
if (lastLink == link) {
pos--;
}
link = previous;
lastLink = null;
expectedModCount++;
list.size--;
list.modCount++;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
hasNext()判斷當(dāng)前節(jié)點（就是voidLink十拣，從構(gòu)造函數(shù)看出來的）的下一個節(jié)點是否為空封拧，next()返回下一個節(jié)點的data，remove（）方法終于是我們熟悉的背影了夭问，主要邏輯就在這里了泽西。
