Learning series of Java Xiaobai collection source code: LinkedList
LinkedList source code learning
Portal: learning series of Java Xiaobai collection source code: ArrayList
This is the LinkedList learning part of the collection source code learning series. If there is any improper description, please comment and correct it in the comment area!
LinkedList inheritance system
LinkedList, like ArrayList, implements the list interface, represents the list structure, and has similar add, remove, clear and other operations. Different from ArrayList, the underlying layer of LinkedList is based on a two-way linked list, which allows the storage of discontinuous addresses, establishes connections through mutual references between nodes, and stores data through nodes.
LinkedList core source code
Since it is node based, let's see how nodes exist in LinkedList:
//Node作为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;
}
}
We found that node, as its internal class, has three attributes, one is the pointer prev to the previous node, the other is the pointer next to the next node, and the stored element value item. Let's take a look at some basic properties of LinkedList:
/*用transient关键字标记的成员变量不参与序列化过程*/
transient int size = 0;//记录节点个数
/**
* first是指向第一个节点的指针。永远只有下面两种情况：
* 1、链表为空，此时first和last同时为空。
* 2、链表不为空，此时第一个节点不为空，第一个节点的prev指针指向空
*/
transient Node<E> first;
/**
* last是指向最后一个节点的指针，同样地，也只有两种情况：
* 1、链表为空，first和last同时为空
* 2、链表不为空，此时最后一个节点不为空，其next指向空
*/
transient Node<E> last;
//需要注意的是，当first和last指向同一节点时，表明链表中只有一个节点。
After understanding the basic properties, let's take a look at its construction method. Since you don't have to care about its storage location, its constructor is also quite simple:
//创建一个空链表
public LinkedList() {
}
//创建一个链表，包含指定传入的所有元素，这些元素按照迭代顺序排列
public LinkedList(Collection<? extends E> c) {
this();
//添加操作
addAll(c);
}
Addall (c) actually calls addall (size, c). Since size = 0 here, it is equivalent to adding one by one from scratch. As for the addall method, we will not mention it for the time being. When we summarize the ordinary addition operations, we will naturally understand all the addition operations.
//把e作为链表的第一个元素
private void linkFirst(E e) {
//建立临时节点指向first
final Node<E> f = first;
//创建存储e的新节点，prev指向null，next指向临时节点
final Node<E> newNode = new Node<>(null,e,f);
//这时newNode变成了第一个节点，将first指向它
first = newNode;
//对原来的first，也就是现在的临时节点f进行判断
if (f == null)
//原来的first为null，说明原来没有节点，现在的newNode
//是唯一的节点，所以让last也只想newNode
last = newNode;
else
//原来链表不为空，让原来头节点的prev指向newNode
f.prev = newNode;
//节点数量加一
size++;
//对列表进行改动，modCount计数加一
modCount++;
}
Accordingly, adding the element as the last element of the linked list is similar to adding the first element, so I won't repeat it. Let's take a look at the addall operation we encountered at the beginning. It feels a little troublesome:
//在指定位置把另一个集合中的所有元素按照迭代顺序添加进来，如果发生改变，返回true
public boolean addAll(int index,Collection<? extends E> c) {
//范围判断
checkPositionIndex(index);
//将集合转换为数组，果传入集合为null，会出现空指针异常
Object[] a = c.toArray();
//传入集合元素个数为0，没有改变原集合，返回false
int numNew = a.length;
if (numNew == 0)
return false;
//创建两个临时节点，暂时表示新表的头和尾
Node<E> pred,succ;
//相当于从原集合的尾部添加
if (index == size) {
//暂时让succ置空
succ = null;
//让pred指向原集合的最后一个节点
pred = last;
} else {
//如果从中间插入，则让succ指向指定索引位置上的节点
succ = node(index);
//让succ的prev指向pred
pred = succ.prev;
}
//增强for循环遍历赋值
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
//创建存储值尾e的新节点，前向指针指向pred，后向指针指向null
Node<E> newNode = new Node<>(pred,null);
//表明原链表为空，此时让first指向新节点
if (pred == null);
first = newNode;
else
//原链表不为空，就让临时节点pred节点向后移动
pred.next = newNode;
//更新新表的头节点为当前新创建的节点
pred = newNode;
}
//这种情况出现在原链表后面插入
if (succ == null) {
//此时pred就是最终链表的last
last = pred;
} else {
//在index处插入的情况
//由于succ是node(index)的临时节点，pred因为遍历也到了插入链表的最后一个节点
//让最后位置的pred和succ建立联系
pred.next = succ;
succ.prev = pred;
}
//新长度为原长+增长
size += numNew;
modCount++;
return true;
}
Let's see how to delete elements in a linked list:
//取消一个非空节点x的连结，并返回它
E unlink(Node<E> x) {
//同样的，在调用这个方法之前，需要确保x不为空
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//明确x与上一节点的联系，更新并删除无用联系
//x为头节点
if (prev == null) {
//让first指向x.next的临时节点next，宣布从下一节点开始才是头
first = next;
} else {
//x不是头节点的情况
//让x.prev的临时节点prev的next指向x.next的临时节点
prev.next = next;
//删除x的前向引用，即让x.prev置空
x.prev = null;
}
//明确x与下一节点的联系，更新并删除无用联系
//x为尾节点
if (next == null) {
//让last指向x.prev的临时节点prev，宣布上一节点是最后的尾
last = prev;
} else {
//x不是尾节点的情况
//让x.next的临时节点next的prev指向x.prev的临时节点
next.prev = prev;
//删除x的后向引用，让x.next置空
x.next = null;
}
//让x存储元素置空，等待GC宠信
x.item = null;
size--;
modCount++;
return element;
}
//移除第一次出现的元素o，找到并移除返回true，否则false
public boolean remove(Object o) {
//传入元素本身就为null
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) {
//删除的元素不为null，比较值的大小
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
Of course, in special cases, the above remove method aims to find the corresponding elements, and only needs to add the corresponding logical judgment to the loop. The following important auxiliary method is to obtain the node at the specified position through traversal: with this method, we can use its front and rear positions to deduce other different methods:
//获得指定位置上的非空节点
Node<E> node(int index) {
//在调用这个方法之前会确保0<=inedx<size
//index和size>>1比较，如果index比size的一半小，从前向后遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
//退出循环的条件，i==indx，此时x为当前节点
return x;
} else {
//从后向前遍历
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
At the same time, indexof and lastIndexOf methods also calculate the index of the first or last occurrence of the specified element through the traversal process summarized above and counting conditions. Here, take indexof as an example:
//返回元素第一次出现的位置，没找到就返回-1
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;
}
In fact, it's the traversal operation we talked about above. It's not bad. With this method, we can easily derive another contains method.
public boolean contains(Object o) {
return indexOf(o) != -1;
}
Then there are the gay methods: get and set.
//获取元素值
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//用新值替换旧值，返回旧值
public E set(int index,E element) {
checkElementIndex(index);
//获取节点
Node<E> x = node(index);
//存取旧值
E oldVal = x.item;
//替换旧值
x.item = element;
//返回旧值
return oldVal;
}
The next step is our clear method, which removes all elements and leaves the table empty. Although the writing method is different, the basic idea remains the same: create nodes, move, delete unwanted ones, or find what you need.
public void clear() {
for (Node<E> x = first; x != null; ) {
//创建临时节点指向当前节点的下一位
Node<E> next = x.next;
//下面就可以安心地把当前节点有关的全部清除
x.item = null;
x.next = null;
x.prev = null;
//x向后移动
x = next;
}
//回到最初的起点
first = last = null;
size = 0;
modCount++;
}
Deque related operations
We also know that LinkedList also inherits the deque interface, allowing us to operate it like a queue. Here are some methods to intercept incomplete data:
Let's select and analyze the differences of several confusing methods, such as the following four:
public E element() {
return getFirst();
}
public E getFirst() {
final Node<E> f = first;
//如果头节点为空，抛出异常
if (f == null)
throw new NoSuchElementException();
return f.item;
}
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
Similar to this are:
If you are interested, you can study it. In short, it is relatively simple.