LinkedLiST
特点
- 集合底层实现的数据结构为双向链表
- 集合中元素允许为null
- 允许存入重复的数据
- 元素存放顺序为存入顺序
LinkedList.jpg
继承关系
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
成员变量
// 链表节点个数
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;
}
}
方法
addAll()
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;
}
add()
public boolean add(E e) {
linkLast(e);
return true;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
// 在链表末尾添加一个节点
void linkLast(E e) {
// add之前的未节点
final Node<E> l = last;
// 构建新的未节点，并将新节点 prev 指针指向 之前的未节点
final Node<E> newNode = new Node<>(l, e, null);
// last 索引指向末节点
last = newNode;
// 如果之前链表为空则新节点也作为头节点
if (l == null)
first = newNode;
// 否则将之前的未节点的 next 指针指向新节点
else
l.next = newNode;
size++;
modCount++;
}
// 添加一个元素在链表的头节点位置
private void linkFirst(E e) {
// add之前的头节点
final Node<E> f = first;
// 以添加的元素为节点值构建新的头节点 并将 next 指针指向 之前的头节点
final Node<E> newNode = new Node<>(null, e, f);
// first 索引指向将新的节点
first = newNode;
// 如果添加之前链表空则新的节点也作为未节点
if (f == null)
last = newNode;
else
// 否则将之前的头节点的 prev 指针指向新节点
f.prev = newNode;
size++;
modCount++;
}
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
// 获取prev节点
final Node<E> pred = succ.prev;
// 构建新节点, prev 节点为 pred，next 节点为 succ
final Node<E> newNode = new Node<>(pred, e, succ);
// 原节点的 prev 指向新节点
succ.prev = newNode;
// 如果 pred 为空即头节点出插入了一个节点，则将新的节点赋值给 first 索引
if (pred == null)
first = newNode;
else
// 否则 pred 的下一个节点改为新节点
pred.next = newNode;
size++;
modCount++;
}
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;
}
}
