死磕Java之聊聊LinkedList源码(基于JDK1.8)
生活随笔
收集整理的這篇文章主要介紹了
死磕Java之聊聊LinkedList源码(基于JDK1.8)
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
工作快一年了，近期打算研究一下JDK的源碼，也就因此有了死磕java系列
LinkedList 是一個(gè)繼承于AbstractSequentialList的雙向鏈表，鏈表不需要capacity的設(shè)定，它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。
LinkedList 實(shí)現(xiàn) List 接口，能對(duì)它進(jìn)行隊(duì)列操作，提供了相關(guān)的添加、刪除、修改、遍歷等功能。
LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用。
LinkedList 實(shí)現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能克隆。
LinkedList 實(shí)現(xiàn)java.io.Serializable接口，這意味著LinkedList支持序列化，能通過(guò)序列化去傳輸，包括網(wǎng)絡(luò)傳輸與本地文件序列化。
LinkedList 是非同步的，如若要在并發(fā)情況下使用建議選取java.util.concurrent包下的集合類型。
LinkedList的UML圖
LinkedList的成員變量及其含義
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0;
/**
* 指向頭指針的節(jié)點(diǎn).
* transient關(guān)鍵字掃盲，在實(shí)現(xiàn)Serilizable接口后，
* 將不需要序列化的屬性前添加關(guān)鍵字transient，
* 序列化對(duì)象的時(shí)候，這個(gè)屬性就不會(huì)序列化到指定的目的地中
*/
transient Node<E> first;
/**
* 指向尾節(jié)點(diǎn)。
*/
transient Node<E> last;
/**
* 構(gòu)造方法的空實(shí)現(xiàn)。
*/
public LinkedList() {
}
/**
* 按照集合迭代器返回的順序構(gòu)造包含指定集合元素的列表。
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* 鏈表的節(jié)點(diǎn)，私有實(shí)現(xiàn)。
*/
private static class Node<E> {
E item;
Node<E> next; // 鏈表的后繼節(jié)點(diǎn)
Node<E> prev; // 鏈表的前驅(qū)節(jié)點(diǎn)
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
}
聊聊LinkedList的主要方法實(shí)現(xiàn)
我們主要看研究一下下面的幾個(gè)方法，LinkedList其他方法都是通過(guò)調(diào)用這幾個(gè)方法來(lái)實(shí)現(xiàn)功能，包括LinkedList的雙端隊(duì)列的方法也是。
/**
* 在鏈表頭部插入元素.
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
/**
* 在鏈表尾部插入元素.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
// 鏈表防止并發(fā)下被修改的快速失敗策略
modCount++;
}
/**
* 在指定節(jié)點(diǎn)前面插入元素.
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
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++;
modCount++;
}
/**
* 移除鏈表的頭部元素.
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC 將元素置為空，讓jvm在gc時(shí)回收資源
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
/**
* 移除鏈表的尾部元素.
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
/**
* 移除某一個(gè)節(jié)點(diǎn)元素.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
/**
* 通過(guò)indexOf方法來(lái)定位給定的元素，若LinkedList中存在元素則返回該元素對(duì)應(yīng)的index，
* 反之返回-1.
*/
public boolean contains(Object o) {
return indexOf(o) != -1;
}
/**
* 在鏈表尾部追加元素.
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 移除鏈表中的指定元素，分兩種情況進(jìn)行處理，當(dāng)元素為空時(shí)與元素不為空時(shí)，時(shí)間復(fù)雜度為O(n).
*/
public boolean remove(Object o) {
if (o == null) {
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;
}
/**
* 將一個(gè)集合的所有元素追加到鏈表的尾部.
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* 將指定集合中的所有元素插入到該列表中，從指定位置開(kāi)始。將當(dāng)前在該位置的元素（如果有的話）
* 和任何后續(xù)元素向右移動(dòng)（增加它們的索引）。新元素將以指定集合的迭代器返回的順序出現(xiàn)在列表中。
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
/**
* 清空鏈表.
*/
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}
// Positional Access Operations 以下是位置訪問(wèn)操作
/**
* 獲取鏈表中對(duì)應(yīng)索引的節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(n)
*/
public E get(int index) {
// 檢查index是否越界
checkElementIndex(index);
return node(index).item;
}
/**
* 更新對(duì)應(yīng)index的元素，并返回舊值，時(shí)間復(fù)雜度為O(n).
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
/**
* 在指定索引添加元素，時(shí)間復(fù)雜度為O(1).
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* 移除指定索引的元素，時(shí)間復(fù)雜度為O(1).
*/
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
/**
* 查找指定index位置的元素.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
// 在查找對(duì)應(yīng)index位置的元素的時(shí)候，java開(kāi)發(fā)人員做了一層優(yōu)化
// 當(dāng)index大于size的一半時(shí)從前向后查
// 當(dāng)index小于size的一半時(shí)從后向前查
// 這樣的話時(shí)間復(fù)雜度就變成了index/2
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;
}
}
// Search Operations
/**
* 查找指定元素的index，從前向后查
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
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;
}
/**
* 查找指定元素的index，從后向前查
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
動(dòng)手實(shí)現(xiàn)LinkedList
由于代碼過(guò)長(zhǎng)，故不在此處一一貼出來(lái)，感興趣的小伙伴可以到我的github查看[github]: https://github.com/haifeiWu/interview-collect/tree/master/src/main/java/com/haifeiwu/interview/structure/list
小結(jié)
與ArrayList相比，LinkedList的長(zhǎng)處在于當(dāng)頻繁的增加或者刪除元素時(shí)效率會(huì)很高，但是LinkedList空間占用比較大，是一種典型的用空間換時(shí)間方案，在我們平時(shí)做代碼優(yōu)化時(shí)這也不失是種折中的方案。
LinkedList并發(fā)插入時(shí)節(jié)點(diǎn)覆蓋的問(wèn)題，就是當(dāng)多個(gè)線程同時(shí)獲取到相同的尾節(jié)點(diǎn)的時(shí)候，然后多個(gè)線程同時(shí)在此尾節(jié)點(diǎn)后面插入數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)數(shù)據(jù)覆蓋的問(wèn)題，因此在并發(fā)量大的情況下應(yīng)該使用java的加鎖機(jī)制，或者采用java.util.concurrent包下的集合類型。
總結(jié)
以上是生活随笔為你收集整理的死磕Java之聊聊LinkedList源码(基于JDK1.8)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 美国出现罕见绿色天空：人眼所见一片翠绿
- 下一篇： 负优化？三星手机应用更新 删除货币汇率转