Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
因为表述方便问题，有时使用前驱&后继节点，有时使用前驱&后继指针，事实上对象保存的就是对象的地址，也就是指针。
1.LinkedList继承关系
LinkedList.png
2.LinkedList的数据结构
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;
}
}
LinkedList继承自AbstractSequentialList并实现了List接口，底层是双向链表数据结构；LinkedList同时实现了Deque接口，可用作双向队列。
3.LinkedList性能分析
1.LinkedList是基于链表实现的，不存在容量不足的问题，所以没有扩容方法，也就没有因扩容带来的性能问题。
2.LinkedList查找元素时，根据index的大小需要从开始或从结尾遍历到index位置，其时间复杂度为O(n)。
3.LinkedList新增/删除元素时，不存在数据的移动，只需要修改前驱节点与后继节点的指向，不考虑查找的情况下，其时间复杂度为O(1)。
总结(对比ArrayList)：
- LinkedList在查找数据时需要遍历链表，性能较差；而新增或删除只需要修改指针的指向，具有较好的性能，所以LinkedList常用于查询较少，新增/删除较多的场景。
- ArrayList具有较好的查询性能，而新增/删除都可能引起大量元素的移动，性能较差，所以ArrayList适用于查询较多，新增/删除较少的场景。
- LinkedList需要额外的内存空间保存指针(前向指针(前向节点)/后继指针(后继节点))信息，如果对内存有较高要求，可以考虑其他方案。
- 尽量不要使用for循环遍历LinkedList，应该使用迭代器，因为LinkedList每访问一个数据都要遍历链表一次(具体看源码分析)。
4.LinkedList源码分析
1.成员变量分析
// 链表的大小
transient int size = 0;
// 第一个节点(头结点)
transient Node<E> first;
// 最后一个节点(尾结点)
transient Node<E> last;
2.构造方法分析
// .. 没啥好说的
public LinkedList() {
}
public LinkedList(Collection<extends E> c) {
this();
addAll(c);
}
3.核心方法分析
3.1新增元素
1.从链表尾部新增一个节点
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 从链表尾部添加一个新节点
*/
void linkLast(E e) {
// 定义一个临时变量保存最后一个节点
final Node<E> l = last;
// 创建一个新的节点，l == 上一个节点 ； null == 下一个节点(最后一个节点的下一个节点为null)
final Node<E> newNode = new Node<>(l, e, null);
// 将新建的节点置为最后一个节点
last = newNode;
if (l == null)
// 如果 l == null表示之前一个节点都没有，新增节点之后first也指向新节点
first = newNode;
else
// 否则，之前的最后一个节点的后继指针指向新建的节点
l.next = newNode;
// 链表大小+1
size++;
// 修改次数+1
modCount++;
}
2.指定位置新增节点
/**
* 指定位置新增元素
*/
public void add(int index, E element) {
// 检查是否越界
checkPositionIndex(index);
if (index == size)
// 链表最后新增节点
linkLast(element);
else
// 查找指定下标节点，在指定下标之前新增节点
linkBefore(element, node(index));
}
/**
* 查找节点的方法
* 这是LinkedList一个很重要的方法，LinkedList很多方法都要依赖此方法查找对应的节点
*/
Node<E> node(int index) {
// 判断index的大小，决定要从头开始遍历链表的一半还是从尾部开始遍历链表的一半
if (index < (size >> 1)) {
// 顺序遍历查找第index个节点并返回
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;
}
}
/**
* 指定位置插入新的节点
*/
void linkBefore(E e, Node<E> succ) {
// succ：指定位置节点
// pred保存指定位置节点的前向指针
final Node<E> pred = succ.prev;
// 创建一个新的节点
final Node<E> newNode = new Node<>(pred, e, succ);
// 指定位置的节点的前向指针指向新建的节点
succ.prev = newNode;
if (pred == null)
// 如果pred == null，表示原来链表为空或者刚好从第一个节点插入新的节点(因为第一个节点没有前向节点，pred = null)
first = newNode;
else
// 否则，指定位置节点的前向节点的后继指针指向新建的节点(有些绕口，自己理解吧)
pred.next = newNode;
size++; // 链表大小+1
modCount++; // 修改次数+1
}
3.批量插入数据
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 {
// 如果是从其他某个位置新增的节点，就将新增的最后的一个节点的后继指针指向指定位置节点(succ)；指定位置节点的前向指针指向新增的最后一个节点
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
3.2查找元素
1.查找数据
public E get(int index) {
// 检查是否越界
checkElementIndex(index);
// 返回指定节点的元素
return node(index).item;
}
关于node方法之前已经说过，这里不再重复，但是再说一遍，该方法很重要！！！
3.3修改元素
1.修改元素
public E set(int index, E element) {
checkElementIndex(index);
// 查找指定位置的Node节点(又是熟悉的node方法)
Node<E> x = node(index);
// 记录节点上的元素
E oldVal = x.item;
// 将旧元素指向新元素
x.item = element;
// 返回旧元素
return oldVal;
}
3.4删除元素
1.根据索引删除
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;
if (prev == null) {
// prev == null表示删除的x是头结点
first = next;
} else {
// 否则，前驱节点的后继指针指向x的后继节点
prev.next = next;
// 将x的前驱节点置为null
x.prev = null;
}
if (next == null) {
// next == null，说明删除的x的尾结点
last = prev;
} else {
// 否则，后继节点的前驱指针指向x的前驱节点
next.prev = prev;
// 将x的后继节点置为null
x.next = null;
}
// 将x节点中的元素item置为null，此时达到删除一个节点的目的
x.item = null;
size--;
modCount++;
// 返回移除的元素
return element;
}
2.根据元素删除
public boolean remove(Object o) {
// 无论o是否为null，最终都是调用unlink(x)方法进行删除
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;
}
3.批量删除
/**
* LinkedList并没有该方法，该方法是定义在其父类AbstractCollection上的
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
boolean modified = false;
// 迭代器
Iterator<?> it = iterator();
while (it.hasNext()) {
// 判断迭代的元素是否包含在容器c中
if (c.contains(it.next())) {
// 真正删除元素的方法
it.remove();
modified = true;
}
}
return modified;
}
/**
* AbstractSequentialList复写父类的方法
*/
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator() {
return listIterator(0);
}
/**
* LinkedList复写父类的方法
*/
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
// ListItr初始化时，将操作计数器modCount赋值给expectedModCount。
// 之后每次调用remove方法都会校验expectedModCount与modCount是否相等，否则会抛出异常。
private int expectedModCount = modCount;
// ...
}
/**
* 调用next方法，迭代到下一个节点
*/
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
// lastReturned的下一个节点
Node<E> lastNext = lastReturned.next;
// 删除lastReturned节点
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
final void checkForComodification() {
// 校验modCount与expectedModCount
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
5.关于LinkedList作为双向队列
前面已经说过LinkedList实现了Deque接口，可以作为双向队列使用
1.从链表头部或尾部新增节点
// 作为双向队列从头部或尾部新增节点
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的前向指针指向新增的节点
f.prev = newNode;
size++;
modCount++;
}
/**
* 从尾部新增节点
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 前面分析过，不再赘述
*/
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++;
}
2.从头部或尾部获取元素
// 过于简单不做分析
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
3.从头部或尾部删除元素
/**
* 从头部删除节点
*/
public E removeFirst() {
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;
// 记录f的下一个节点
final Node<E> next = f.next;
// 置为null，表示删除节点
f.item = null;
f.next = null; // help GC
// 使next成为第一个节点
first = next;
if (next == null)
// 删除的是最后一个节点，则last也置为null
last = null;
else
// 否则next节点的前向指针置为null(头结点的前向指针与尾结点的后继指针为null)
next.prev = null;
size--;
modCount++;
return element;
}
/**
* 从尾部删除节点
* 与从头部删除节点的逻辑类似
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Node<E> l) {
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;
}
6.总结
1.LinkedList是双向链表的数据结构，相比于单链表，在删除一个节点时，不需要像单链表一样一路保存当前节点的前向节点，因为双向链表当前节点本身就已经保存有前向指针，所以删除时双向链表比单向链表效率更高。
2.需要额外的内存空间保存节点信息。
3.对于大数据量来说，相比ArrayList，具有增删快查找慢特性。