原文鏈接http://zhhll.icu/2021/01/04/java%E5%9F%BA%E7%A1%80/%E9%9B%86%E5%90%88/LinkedList%E8%AF%A6%E8%A7%A3/
LinkedList詳解
LinkedList是List介面的一個主要的實作類之一，以java8為例來了解一下LinkedList的原始碼實作
繼承關系
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
繼承了AbstractSequentialList，實作了List介面、Deque介面、Cloneable介面、Serializable介面
關鍵變數
/**
* 鏈表的長度
*/
transient int size = 0;
/**
* 頭節點
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* 尾結點
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
// 這里用到了一個內部類Node，看到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;
}
}
構造器
// 無參默認構造器
public LinkedList() {
}
/**
* 傳入一個集合作為引數
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
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;
// index == size時表示是從鏈表尾部添加元素，所以前置節點為當前鏈表的尾結點
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);
// 前置節點為null，表示這是頭節點
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
// succ == null,說明是從尾部添加的，將最后一個節點賦給尾結點
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
// 獲取index位置的節點
Node<E> node(int index) {
// assert isElementIndex(index);
// index小于鏈表長度的一半，從鏈表頭部開始遍歷
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // index不小于鏈表長度的一半，從鏈表尾部開始遍歷
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
add方法
// 邏輯比較簡單，與上邊addAll類似，一通插
public void add(int index, E element) {
checkPositionIndex(index);
// index == size表示在鏈表尾部添加
if (index == size)
linkLast(element);
else // 否則在中間插入 先找到index所在位置的節點
linkBefore(element, node(index));
}
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++;
modCount++;
}
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++;
}
remove方法
LinkedList的remove方法比較
public E remove(int index) {
// 檢測該索引位置是否符合要求 index >= 0 && index < size
checkElementIndex(index);
return unlink(node(index));
}
// 找到當前索引位置的節點
Node<E> node(int index) {
// assert isElementIndex(index);
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;
}
}
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;
// 前驅節點為null，表示為頭節點，頭節點指向后繼節點即可
if (prev == null) {
first = next;
} else {
// 前驅節點的后繼節點指向該元素的后繼節點
prev.next = next;
x.prev = null;
}
// 后繼節點為null，表示為尾節點，尾節點指向前驅節點即可
if (next == null) {
last = prev;
} else {
// 后繼節點的前驅節點指向該元素的前驅節點
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
迭代器
LinkedList使用的迭代器是其父類AbstractSequentialList中的iterator方法
// AbstractSequentialList類方法
public Iterator<E> iterator() {
return listIterator();
}
// LinkedList類方法
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
// 與ArrayList的迭代器不同的是，ArrayList的迭代器實作的是Iterator介面 而LinkedList為ListIterator介面，相當于ArrayList的listIterator()方法
// Iterator只能向前遍歷，ListIterator可以向前也可以向后
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
由于本身的博客百度沒有收錄，博客地址http://zhhll.icu
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/252919.html
標籤：其他