LinkedList介紹
JangGwa帶你再熟悉一下LinkedList颗圣，首先簡單介紹下LinkedList我纪。
1.基于雙向鏈表實現(xiàn)脓匿，鏈表無容量限制遍略。
2.LinkedList是非線程安全的压鉴。
3.實現(xiàn)了List接口崖咨，實現(xiàn)了get(int location)、remove(int location)等根據(jù)索引值來獲取油吭、刪除節(jié)點的函數(shù)击蹲。
4.實現(xiàn)了Deque接口，可以將LinkedList當做雙端隊列使用上鞠。
5.實現(xiàn)了Cloneable接口际邻，能被克隆。
6.實現(xiàn)了Serializable接口芍阎，支持序列化世曾。
LinkedList源碼解析
LinkedList繼承了AbstractSequentialList并實現(xiàn)了List,Deque, Cloneable, java.io.Serializable 接口，上面做了相應的介紹就不再闡述了谴咸。關鍵我們看兩個重要的屬性header和size轮听。
header:雙向鏈表的表頭，它是雙向鏈表節(jié)點所對應的類Entry的實例岭佳。Entry中包含成員變量： previous, next, element血巍。其中，previous是該節(jié)點的上一個節(jié)點珊随，next是該節(jié)點的下一個節(jié)點述寡，element是該節(jié)點所包含的值舀锨。
size:雙向鏈表中節(jié)點的個數(shù)
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
// 鏈表的表頭，表頭不包含任何數(shù)據(jù)田篇。Entry是個鏈表類數(shù)據(jù)結(jié)構礁鲁。
private transient Entry<E> header = new Entry<E>(null, null, null);
// LinkedList中元素個數(shù)
private transient int size = 0;
// 默認構造函數(shù)：創(chuàng)建一個空的鏈表
public LinkedList() {
header.next = header.previous = header;
}
// 包含“集合”的構造函數(shù):創(chuàng)建一個包含“集合”的LinkedList
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
雙向鏈表的節(jié)點所對應的數(shù)據(jù)結(jié)構。
private static class Entry<E> {
// 當前節(jié)點所包含的值
E element;
// 下一個節(jié)點
Entry<E> next;
// 上一個節(jié)點
Entry<E> previous;
Entry(E element, Entry<E> next, Entry<E> previous) {
this.element = element;
this.next = next;
this.previous = previous;
}
}
獲取鏈表指定位置節(jié)點
將index與長度size的一半比較螟炫，如果index<size/2波附，就只從位置0往后遍歷到位置index處，而如果index>size/2昼钻，就只從位置size往前遍歷到位置index處掸屡。
private Entry<E> entry(int index) {
if (index < 0 || index >= size)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
Entry<E> e = header;
// 獲取index處的節(jié)點。
// 若index < 雙向鏈表長度的1/2,則從前先后查找;
// 否則然评，從后向前查找仅财。
if (index < (size >> 1)) {
for (int i = 0; i <= index; i++)
e = e.next;
} else {
for (int i = size; i > index; i--)
e = e.previous;
}
return e;
}
get()和set()
// 返回LinkedList指定位置的元素
public E get(int index) {
return entry(index).element;
}
// 設置index位置對應的節(jié)點的值為element
public E set(int index, E element) {
Entry<E> e = entry(index);
E oldVal = e.element;
e.element = element;
return oldVal;
}
添加
// 將e添加到當前節(jié)點的前面
public void add(E e) {
checkForComodification();
lastReturned = header;
addBefore(e, next);
nextIndex++;
expectedModCount++;
}
// 將元素添加到LinkedList的起始位置
public void addFirst(E e) {
addBefore(e, header.next);
}
// 將元素添加到LinkedList的結(jié)束位置
public void addLast(E e) {
addBefore(e, header);
}
// 將元素(E)添加到LinkedList中
public boolean add(E e) {
// 將節(jié)點(節(jié)點數(shù)據(jù)是e)添加到表頭(header)之前。
// 即沾瓦，將節(jié)點添加到雙向鏈表的末端满着。
addBefore(e, header);
return true;
}
刪除
// 從LinkedList中刪除元素(o)
public boolean remove(Object o) {
if (o==null) {
// 若o為null的刪除情況
for (Entry<E> e = header.next; e != header; e = e.next) {
if (e.element==null) {
remove(e);
return true;
}
}
} else {
// 若o不為null的刪除情況
for (Entry<E> e = header.next; e != header; e = e.next) {
if (o.equals(e.element)) {
remove(e);
return true;
}
}
}
return false;
}
// 將節(jié)點從鏈表中刪除
private E remove(Entry<E> e) {
if (e == header)
throw new NoSuchElementException();
E result = e.element;
e.previous.next = e.next;
e.next.previous = e.previous;
e.next = e.previous = null;
e.element = null;
size--;
modCount++;
return result;
}
清空LinkedList
// 清空雙向鏈表
public void clear() {
Entry<E> e = header.next;
// 從表頭開始，逐個向后遍歷贯莺；對遍歷到的節(jié)點執(zhí)行一下操作：
// (01) 設置前一個節(jié)點為null
// (02) 設置當前節(jié)點的內(nèi)容為null
// (03) 設置后一個節(jié)點為“新的當前節(jié)點”
while (e != header) {
Entry<E> next = e.next;
e.next = e.previous = null;
e.element = null;
e = next;
}
header.next = header.previous = header;
// 設置大小為0
size = 0;
modCount++;
}
克隆
public Object clone() {
LinkedList<E> clone = null;
// 克隆一個LinkedList克隆對象
try {
clone = (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
// 新建LinkedList表頭節(jié)點
clone.header = new Entry<E>(null, null, null);
clone.header.next = clone.header.previous = clone.header;
clone.size = 0;
clone.modCount = 0;
// 將鏈表中所有節(jié)點的數(shù)據(jù)都添加到克隆對象中
for (Entry<E> e = header.next; e != header; e = e.next)
clone.add(e.element);
return clone;
}
總結(jié)
- LinkedList的實現(xiàn)是基于雙向循環(huán)鏈表的风喇。有一個重要的內(nèi)部類:Entry，是雙向鏈表節(jié)點所對應的數(shù)據(jù)結(jié)構缕探。
- 不存在容量不足的問題魂莫。
- LinkedList是基于鏈表實現(xiàn)的，因此插入刪除效率高爹耗，查找效率低耙考。
- LinkedList的克隆函數(shù)，即是將全部元素克隆到一個新的LinkedList對象中潭兽。
- LinkedList實現(xiàn)java.io.Serializable倦始。當寫入到輸出流時，先寫入“容量”山卦，再依次寫入“每一個節(jié)點保護的值”鞋邑；當讀出輸入流時，先讀取“容量”账蓉，再依次讀取“每一個元素”枚碗。
