LinkedList是基于雙向鏈表實現(xiàn)的凑耻，相比與內(nèi)部使用數(shù)組的ArrayList而言LinkedList查詢比較慢（因為鏈表不用在連續(xù)的存儲空間）语淘，添加碉输、刪除效率比較高（因為只需要修改前驅(qū)結(jié)點和后繼結(jié)點的指針可以實現(xiàn))。因此诱鞠，對于添加互例，刪除比較多的情況下奢入，推薦使用LinkedList。本文基于android-23源碼分析媳叨。
源碼分析
LinkedList繼承和實現(xiàn)的接口
public class LinkedList<E> extends AbstractSequentialList<E> implements
List<E>, Deque<E>, Queue<E>, Cloneable, Serializable {}
Cloneable：通過實現(xiàn)clone()方法腥光，能夠?qū)崿F(xiàn)克隆對象关顷；
Serializable：LinkedList支持序列化，和反序列化武福，實現(xiàn)Serializble接口之后能夠進行序列化傳輸议双；
LinkedList的構(gòu)造函數(shù)
public LinkedList() {
voidLink = new Link<E>(null, null, null);
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
在LinkedList的構(gòu)造函數(shù)當(dāng)中，會先創(chuàng)建一個Link的對象voidLink結(jié)點捉片，這個Link是LinkedList的一個內(nèi)部類平痰，它維護一個結(jié)點數(shù)據(jù)，前驅(qū)結(jié)點以及后繼結(jié)點伍纫，創(chuàng)建出來的voidLink的pervious和next分別指向當(dāng)前創(chuàng)建的Link對象宗雇。
我們先來看看Link類的定義：
private static final class Link<ET> {
//當(dāng)前節(jié)點數(shù)據(jù)
ET data;
//previous前驅(qū)結(jié)點，next后繼結(jié)點
Link<ET> previous, next;
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
如果在LinkedList的構(gòu)造函數(shù)中傳遞了collection集合變量莹规，那么最后還會調(diào)用addAll方法赔蒲。
添加元素的方法
@Override
public boolean addAll(Collection<? extends E> collection) {
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
Link<E> previous = voidLink.previous;
for (E e : elements) {
//創(chuàng)建newLink結(jié)點
Link<E> newLink = new Link<E>(e, previous, null);
//previous結(jié)點的后繼結(jié)點指向當(dāng)前創(chuàng)建的結(jié)點
previous.next = newLink;
//previous 結(jié)點指向當(dāng)前創(chuàng)建的結(jié)點
previous = newLink;
}
//previous結(jié)點的后繼結(jié)點指向LinkedList的當(dāng)前結(jié)點
previous.next = voidLink;
//當(dāng)前結(jié)點的前驅(qū)結(jié)點指向previous結(jié)點
voidLink.previous = previous;
//當(dāng)前的數(shù)量增加
size += adding;
//當(dāng)前修改的標記增加
modCount++;
return true;
}
在addAll的方法中，先拿到需要添加的元素的集合访惜，然后循環(huán)遍歷嘹履，在遍歷的過程中不斷創(chuàng)建新的結(jié)點，然后將前一個結(jié)點的后繼結(jié)點指向當(dāng)前創(chuàng)建的結(jié)點债热，然后將前一個結(jié)點指向當(dāng)前創(chuàng)建的結(jié)點，循環(huán)完了之后幼苛，將前一個結(jié)點的后繼結(jié)點指向LinkedList中的當(dāng)前結(jié)點窒篱，然后將當(dāng)前結(jié)點的前驅(qū)結(jié)點指向前一個結(jié)點，修改size和modCount的值舶沿，完成添加工作墙杯。
現(xiàn)在我們看看其他的add方法：
@Override
public boolean add(E object) {
return addLastImpl(object);
}
public void addLast(E object) {
addLastImpl(object);
}
private boolean addLastImpl(E object) {
//LinkedList的voidLink的前驅(qū)結(jié)點
Link<E> oldLast = voidLink.previous;
//創(chuàng)建一個newLink結(jié)點，newLink的前驅(qū)結(jié)點指向oldLast括荡，后繼結(jié)點指向voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//voidLink的前驅(qū)結(jié)點指向newLink
voidLink.previous = newLink;
//oldLast的后繼結(jié)點指向newLink
oldLast.next = newLink;
size++;
modCount++;
return true;
}
oldLast結(jié)點指向voidLink結(jié)點的前驅(qū)結(jié)點高镐，創(chuàng)建一個newLink結(jié)點，newLink的前驅(qū)結(jié)點指向oldLast畸冲，后繼結(jié)點指向voidLink嫉髓，然后將voidLink的前驅(qū)結(jié)點指向newLink，oldLast的后繼結(jié)點指向newLink邑闲，這樣操作過后算行，就將新創(chuàng)建的newLink結(jié)點插入到oldLast和voidLink中間。
public void addFirst(E object) {
addFirstImpl(object);
}
private boolean addFirstImpl(E object) {
//oldFirst指向voidLink的后繼結(jié)點
Link<E> oldFirst = voidLink.next;
//創(chuàng)建newLink結(jié)點
Link<E> newLink = new Link<E>(object, voidLink, oldFirst);
//voidLink的后繼結(jié)點指向newLink結(jié)點
voidLink.next = newLink;
//oldFirst的前驅(qū)結(jié)點指向newLink結(jié)點
oldFirst.previous = newLink;
size++;
modCount++;
return true;
}
首先oldFirst指向voidLink的后繼結(jié)點苫耸，然后創(chuàng)建newLink結(jié)點州邢，voidLink的后繼結(jié)點指向newLink結(jié)點，最后oldFirst的前驅(qū)結(jié)點指向newLink結(jié)點褪子，并且修改size量淌，modCount的值骗村。
public void addLast(E object) {
addLastImpl(object);
}
private boolean addLastImpl(E object) {
//oldLast結(jié)點指向voidLink的前驅(qū)結(jié)點
Link<E> oldLast = voidLink.previous;
//創(chuàng)建newLink結(jié)點，前驅(qū)結(jié)點為oldLast呀枢，后繼結(jié)點為voidLink
Link<E> newLink = new Link<E>(object, oldLast, voidLink);
//
voidLink.previous = newLink;
oldLast.next = newLink;
size++;
modCount++;
return true;
}
@Override
public boolean addAll(int location, Collection<? extends E> collection) {
if (location < 0 || location > size) {
throw new IndexOutOfBoundsException();
}
int adding = collection.size();
if (adding == 0) {
return false;
}
Collection<? extends E> elements = (collection == this) ?
new ArrayList<E>(collection) : collection;
//previous 指向voidLink
Link<E> previous = voidLink;
if (location < (size / 2)) {
for (int i = 0; i < location; i++) {
//將previous結(jié)點指向previous的后繼結(jié)點
previous = previous.next;
}
} else {
for (int i = size; i >= location; i--) {
//將previous結(jié)點指向previous的前驅(qū)結(jié)點
previous = previous.previous;
}
}
//next結(jié)點指向previous的next
Link<E> next = previous.next;
//通過foreach語法糖循環(huán)遍歷元素的集合
for (E e : elements) {
//創(chuàng)建newLink結(jié)點叙身，前驅(qū)結(jié)點為previous，后繼結(jié)點為null
Link<E> newLink = new Link<E>(e, previous, null);
//previous結(jié)點的后繼結(jié)點指向newLink
previous.next = newLink;
//previous指向newLink
previous = newLink;
}
//previous結(jié)點的后繼結(jié)點指向next
previous.next = next;
//next結(jié)點的前驅(qū)結(jié)點指向previous
next.previous = previous;
size += adding;
modCount++;
return true;
}
添加的方法硫狞，我們主要就看這些信轿，當(dāng)然還有另外的一些添加元素的方法，
public void push(E e) {
addFirstImpl(e);
}
另外的残吩，我們就不多介紹了财忽，下面我們來看看移除元素的方法
刪除方法
移除第一個元素
public E removeFirst() {
return removeFirstImpl();
}
private E removeFirstImpl() {
//first結(jié)點指向voidLink的后繼結(jié)點
Link<E> first = voidLink.next;
//判斷是否有可移除的結(jié)點
if (first != voidLink) {
//next結(jié)點指向first的后繼結(jié)點
Link<E> next = first.next;
//voidLink的后繼結(jié)點指向next
voidLink.next = next;
//next結(jié)點的前驅(qū)結(jié)點指向voidLink
next.previous = voidLink;
size--;
modCount++;
return first.data;
}
throw new NoSuchElementException();
}
通過location移除元素
@Override
public E remove(int location) {
if (location >= 0 && location < size) {
Link<E> link = voidLink;
//通過location找到link結(jié)點
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（int location）的時候，先判斷location是否越界泣侮，如果沒有越界則繼續(xù)往下執(zhí)行即彪，通過循環(huán)找到link結(jié)點，然后分別拿到link結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點活尊，讓他們分別修改應(yīng)用的指向隶校，從而達到從鏈表中刪除結(jié)點的目的。
@Override
public void clear() {
if (size > 0) {
size = 0;
//重置voidLink結(jié)點的前驅(qū)結(jié)點蛹锰，后繼結(jié)點指向
voidLink.next = voidLink;
voidLink.previous = voidLink;
//修改modCount變量
modCount++;
}
}
clear方法會重置voidLink結(jié)點的前驅(qū)結(jié)點深胳，后繼結(jié)點指向。
獲取元素
@Override
public E get(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;
}
}
return link.data;
}
throw new IndexOutOfBoundsException();
}
相比較ArrayList這類可以使用index下標獲取元素的數(shù)組來說铜犬，LinkedList通過location來獲取元素舞终，它需要循環(huán)遍歷，這種隨機的獲取元素的方法效率比較低癣猾。
LinkedList的Iterator
先來看看ReverseLinkIterator：
private class ReverseLinkIterator<ET> implements Iterator<ET> {
private int expectedModCount;
private final LinkedList<ET> list;
private Link<ET> link;
private boolean canRemove;
ReverseLinkIterator(LinkedList<ET> linkedList) {
list = linkedList;
expectedModCount = list.modCount;
link = list.voidLink;
canRemove = false;
}
public boolean hasNext() {
return link.previous != list.voidLink;
}
public ET next() {
if (expectedModCount == list.modCount) {
if (hasNext()) {
link = link.previous;
canRemove = true;
return link.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public void remove() {
if (expectedModCount == list.modCount) {
if (canRemove) {
Link<ET> next = link.previous;
Link<ET> previous = link.next;
next.next = previous;
previous.previous = next;
link = previous;
list.size--;
list.modCount++;
expectedModCount++;
canRemove = false;
return;
}
throw new IllegalStateException();
}
throw new ConcurrentModificationException();
}
}
private static final class LinkIterator<ET> implements ListIterator<ET> {
int pos, expectedModCount;
final LinkedList<ET> list;
Link<ET> link, lastLink;
LinkIterator(LinkedList<ET> object, int location) {
list = object;
expectedModCount = list.modCount;
if (location >= 0 && location <= list.size) {
// pos ends up as -1 if list is empty, it ranges from -1 to
// list.size - 1
// if link == voidLink then pos must == -1
link = list.voidLink;
if (location < list.size / 2) {
for (pos = -1; pos + 1 < location; pos++) {
link = link.next;
}
} else {
for (pos = list.size; pos >= location; pos--) {
link = link.previous;
}
}
} else {
throw new IndexOutOfBoundsException();
}
}
public void add(ET object) {
if (expectedModCount == list.modCount) {
Link<ET> next = link.next;
Link<ET> newLink = new Link<ET>(object, link, next);
link.next = newLink;
next.previous = newLink;
link = newLink;
lastLink = null;
pos++;
expectedModCount++;
list.size++;
list.modCount++;
} else {
throw new ConcurrentModificationException();
}
}
public boolean hasNext() {
return link.next != list.voidLink;
}
public boolean hasPrevious() {
return link != 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 int nextIndex() {
return pos + 1;
}
public ET previous() {
if (expectedModCount == list.modCount) {
if (link != list.voidLink) {
lastLink = link;
link = link.previous;
pos--;
return lastLink.data;
}
throw new NoSuchElementException();
}
throw new ConcurrentModificationException();
}
public int previousIndex() {
return pos;
}
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();
}
}
public void set(ET object) {
if (expectedModCount == list.modCount) {
if (lastLink != null) {
lastLink.data = object;
} else {
throw new IllegalStateException();
}
} else {
throw new ConcurrentModificationException();
}
}
}
