LinkedList
1 类图
2 字段和内部类
// 链表的大小
transient int size = 0;
// 指向第一个节点
transient Node<E> first;
// 指向最后一个节点
transient Node<E> last;
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;
}
}
3 构造器
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;
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;
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
4 增
4.1 addFirst
/**
* 添加元素到头部
*/
public void addFirst(E e) {
linkFirst(e);
}
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++;
}
4.2 addLast
// 添加元素到链表尾部
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
4.3 add(int index, E element)
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* Inserts element e before non-null Node succ.
*/
void linkBefore(E e, Node<E> succ) {
// 找到插入位置节点的前置节点prev
// prev->new Node(e)->succ
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++;
}
/**
* Returns the (non-null) Node at the specified element 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;
}
}
5 删
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
E unlink(Node<E> x) {
final E element = x.item;
// 找到对应索引的节点的前置和后置节点
final Node<E> next = x.next;
final Node<E> prev = x.prev;
// 如果前置节点为空，那么头节点=后置节点
// 否则前置节点的next变成后置节点,需要删除节点的前置节点变成空
// prev->delete->next
// prev->next
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
// 如果后置节点为空，那么尾节点=前置节点
// 否则后置节点的prev变成前置节点,需要删除节点的后置节点变成空
// prev->delete->next
// prev->next
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
// 指向的引用置为空
x.item = null;
size--;
modCount++;
return element;
}
6 改
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
7 查
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
8 遍历和迭代器
避免每次调用get(i),这样的性能开销较高
xuexprivate 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();
}
}