目錄
基本介紹?
常用方法
源碼解析
1. LinkedList的底層結(jié)構(gòu)，Node雙向鏈表
2. LinkedList的幾個(gè)內(nèi)部變量
3.?getFirst()
4.?removeFirst()
5. addFirst(E e)
6.?contains(Object o)
7. add(E e)
8. remove(Object o)
9. addAll(int index, Collection c)
10. get(int index)
11.?spliterator()
總結(jié)
基本介紹?
LinkedList是實(shí)現(xiàn)了List和Deque接口的雙向鏈表，實(shí)現(xiàn)了所有可選列表的操作，允許存放所有元素（包括null）
LinkedList是非線程安全的，因此在多線程的情況下，需要加同步鎖來(lái)保證線程安全，或者使用Collections.synchronizedList?
常用方法
public LinkedList()
public LinkedList(Collection<? extends E> c)
public E getFirst() 獲取第一個(gè)元素
public E getLast() 獲取最后一個(gè)元素
public boolean add(E e) 添加一個(gè)元素
public void add(int index, E element) 在指定位置插入元素
public void addFirst(E e) 在集合前部增加一個(gè)元素
public void addLast(E e) 在集合尾部增加一個(gè)元素
public boolean addAll(Collection<? extends E> c) 把另一個(gè)集合全部添加到當(dāng)前集合
public boolean addAll(int index, Collection<? extends E> c) 在指定位置把另一個(gè)集合全部添加到當(dāng)前集合
public boolean contains(Object o) 判斷是否包含
public int size() 返回集合大小
public boolean remove(Object o) 根據(jù)指定對(duì)象刪除元素
public E remove(int index) 根據(jù)指定索引刪除元素
public E removeFirst() 刪除第一個(gè)元素
public E removeLast() 刪除最后一個(gè)元素
public E get(int index) 根據(jù)索引獲取元素
public E set(int index, E element) 在指定索引處添加一個(gè)元素（覆蓋原數(shù)據(jù)）
public int indexOf(Object o) 返回指定元素索引
public int lastIndexOf(Object o) 返回指定元素出現(xiàn)的最后一個(gè)索引
源碼解析
1. LinkedList的底層結(jié)構(gòu)，Node雙向鏈表
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;
}
}
2. LinkedList的幾個(gè)內(nèi)部變量
transient int size = 0;
// 標(biāo)記鏈表第一個(gè)元素
transient Node<E> first;
// 標(biāo)記鏈表最后一個(gè)元素
transient Node<E> last;
// 鏈表結(jié)構(gòu)修改的次數(shù)
protected transient int modCount = 0;3.?getFirst()
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}這個(gè)方法比較簡(jiǎn)單，其實(shí)就是取鏈表的first節(jié)點(diǎn)，getLast()方法類似，不再贅述
4.?removeFirst()
public E removeFirst() {
// 拿到first節(jié)點(diǎn)
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
final E element = f.item;
final Node<E> next = f.next;
// 把需要?jiǎng)h除的節(jié)點(diǎn)的值置為空，并且把其引用也置為空
f.item = null;
f.next = null; // help GC
// 把next節(jié)點(diǎn)置為first節(jié)點(diǎn)
first = next;
// 如果next節(jié)點(diǎn)為空，說(shuō)明整個(gè)鏈表為空
if (next == null)
// 則把last節(jié)點(diǎn)也置為空
last = null;
else
// 把next節(jié)點(diǎn)的前置引用置為空，因?yàn)閜rev節(jié)點(diǎn)已經(jīng)刪除，next節(jié)點(diǎn)已經(jīng)為頭節(jié)點(diǎn)
// 此時(shí)原來(lái)的first節(jié)點(diǎn)的引用已經(jīng)全部置空，下一次GC時(shí)會(huì)把這個(gè)節(jié)點(diǎn)回收
next.prev = null;
// 容器的size - 1
size--;
modCount++;
return element;
}removceLast()方法類似，只是反過(guò)來(lái)將最后一個(gè)元素置空。
5. addFirst(E e)
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
// 實(shí)例化一個(gè)Node節(jié)點(diǎn)，設(shè)置前置節(jié)點(diǎn)為null，原來(lái)的first節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)
final Node<E> newNode = new Node<>(null, e, f);
// 把鏈表的first節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)
first = newNode;
// 如果當(dāng)前鏈表為空
if (f == null)
// 則將last節(jié)點(diǎn)也置為新實(shí)例化的節(jié)點(diǎn)
last = newNode;
else
// 否則，將原有的first節(jié)點(diǎn)的前置節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)
f.prev = newNode;
size++;
modCount++;
}addLast() 也類似，不再詳細(xì)說(shuō)明了
6.?contains(Object o)
public boolean contains(Object o) {
return indexOf(o) != -1;
}
public int indexOf(Object o) {
int index = 0;
// 判斷元素是否為空
if (o == null) {
// 循環(huán)找到對(duì)應(yīng)元素，找到第一個(gè)相同元素則返回當(dāng)前索引
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null)
return index;
index++;
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item))
return index;
index++;
}
}
return -1;
}7. add(E e)
public boolean add(E e) {
// 將元素添加到鏈表的最后一位
linkLast(e);
return true;
}
void linkLast(E e) {
final Node<E> l = last;
// 實(shí)例化一個(gè)Node節(jié)點(diǎn)，將原來(lái)的last節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)，后置節(jié)點(diǎn)置為null
final Node<E> newNode = new Node<>(l, e, null);
// 將last節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)
last = newNode;
// 如果原先的last節(jié)點(diǎn)為空，說(shuō)明之前鏈表為空
if (l == null)
// 將first節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)
first = newNode;
else
// 否則將之前l(fā)ast節(jié)點(diǎn)的next節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)
l.next = newNode;
size++;
modCount++;
}8. remove(Object o)
public boolean remove(Object o) {
// 跟其他方法很類似，先判斷元素是否為null
if (o == null) {
// 循環(huán)找到對(duì)應(yīng)元素，并執(zhí)行unlink方法
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果前置節(jié)點(diǎn)為空，說(shuō)明當(dāng)前待刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)
if (prev == null) {
// 把first節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)
first = next;
} else {
// 否則就把當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)的next節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)
prev.next = next;
// 把待刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)置為null
x.prev = null;
}
// 如果待刪除節(jié)點(diǎn)的next節(jié)點(diǎn)為null，說(shuō)明當(dāng)前節(jié)點(diǎn)是最后一個(gè)節(jié)點(diǎn)
if (next == null) {
// 將當(dāng)前鏈表的last節(jié)點(diǎn)置為待刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)
last = prev;
} else {
// 把當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)的前置節(jié)點(diǎn)置為當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)
next.prev = prev;
// 當(dāng)前節(jié)點(diǎn)的next節(jié)點(diǎn)置為null
// 此時(shí)待刪除節(jié)點(diǎn)的引用關(guān)系已經(jīng)全部置空
x.next = null;
}
// 把當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)置為null
x.item = null;
size--;
modCount++;
return element;
}
9. addAll(int index, Collection<? extends E> c)
/**
* 在索引位置插入新的集合
*
* @Param index 索引
* @Param c 需要添加的集合
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 校驗(yàn)index是否超出范圍
checkPositionIndex(index);
// 將集合轉(zhuǎn)成數(shù)組
Object[] a = c.toArray();
int numNew = a.length;
// 如果需要添加的集合為空，直接return false
if (numNew == 0)
return false;
Node<E> pred, succ;
// 如果索引位置等于當(dāng)前集合的size，說(shuō)明要將新的集合添加在鏈表的尾部
if (index == size) {
succ = null;
pred = last;
} else {
// 把當(dāng)前索引的元素賦值給succ
succ = node(index);
// 當(dāng)前索引的前置節(jié)點(diǎn)賦值給pred
pred = succ.prev;
}
// 循環(huán)數(shù)組
for (Object o : a) {
Node<E> newNode = new Node<>(pred, e, null);
// 如果pred為null，則將新node對(duì)象賦值給first
if (pred == null)
first = newNode;
else
pred.next = newNode;
// 把pred置為當(dāng)前元素，繼續(xù)添加下一個(gè)元素
pred = newNode;
}
// 如果是在隊(duì)尾添加元素
if (succ == null) {
// 則將鏈表的last節(jié)點(diǎn)置為pred，因?yàn)樯厦嬖谘h(huán)末尾會(huì)將pred = newNode，此時(shí)pred就是最后一個(gè)元素
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
// 如果超出范圍就拋出IndexOutOfBoundsException
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
10. get(int index)
public E get(int index) {
// 校驗(yàn)索引是否越界，如果越界則拋異常
checkElementIndex(index);
// 返回當(dāng)前節(jié)點(diǎn)的元素
return node(index).item;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
Node<E> node(int index) {
// 判斷索引是靠近前半部分還是后半部分
if (index < (size >> 1)) {
// 如果索引靠前，則從頭開(kāi)始遍歷，直到當(dāng)前索引
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
// 然后返回當(dāng)前索引對(duì)應(yīng)的node
return x;
} else {
Node<E> x = last;
// 如果索引靠后，則從末尾開(kāi)始向前遍歷
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}11.?spliterator()
LinkedList中還有spliterator拆分器，該拆分器是后期綁定的，并且使用與鏈接列表相同的元素快速失效。后期綁定拆分器綁定到元素源意味著在第一次遍歷、第一次拆分或第一次查詢估計(jì)大小時(shí)鏈接列表，而不是在創(chuàng)建拆分器時(shí)。它可以和 Java 8 中的 Streams 一起使用。此外，它還可以單獨(dú)和批量遍歷元素。Spliterator 是遍歷元素的更好方法，因?yàn)樗鼘?duì)元素提供了更多的控制。
這個(gè)拆分器感覺(jué)在我平時(shí)的工作中用的也不多，就不做解析了，如果大家想看看這個(gè)方法的解析的話給我留言，我再單獨(dú)寫(xiě)一篇這個(gè)的解析。
總結(jié)
1. LinkedList底層是由雙向鏈表實(shí)現(xiàn)的
2. LinkedList插入和刪除比較快，因?yàn)檎２迦攵际遣迦腈湵淼淖詈笠粋€(gè)元素，只需要改變前置節(jié)點(diǎn)的next指向和當(dāng)前節(jié)點(diǎn)的前置指向即可，不需要想ArrayList一樣移動(dòng)數(shù)組
3. LinkedList如果按照索引查詢會(huì)很慢，因?yàn)樗枰獜念^或從尾開(kāi)始逐個(gè)遍歷直到對(duì)應(yīng)索引位置，不支持隨機(jī)訪問(wèn)
4. LinkedList是非線程安全的
5.?LinkedList元素允許為null，允許重復(fù)元素文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-608155.html
6.?LinkedList是基于雙向鏈表實(shí)現(xiàn)的，所以不存在容量不足的情況，不需要擴(kuò)容文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-608155.html
到了這里，關(guān)于Java集合之LinkedList的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
