LinkedList集合源码分析
文章目录
- LinkedList集合源码分析
- 一、字段分析
- 二、构造函数分析
- 三、方法分析
- 四、总结
- 看到实现了Deque 就要联想到这个数据结构肯定是属于双端队列了。
- Queue 表示队列，Deque表示双端队列。
一、字段分析
- LinkedList 字段很少，就三个。
//表示实际存储的数据个数，即节点个数
transient int size = 0;
//指向最开始的节点
transient Node<E> first;
//指向最末尾的节点
transient Node<E> last;
// Node 是一个静态内部类，从这里也可以看出，LinkedList 是一个双向链表，因为它有一个指向下一个节点
//的 next 和一个指向上一个节点的 prev。
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 对象，字段值都是默认值。
//即 size = 0; first = null, last = null;
public LinkedList() {
}
//使用集合作为参数创建 LinkedList，这个参数 c 得是 Collection 的子类才可以
public LinkedList(Collection<? extends E> c) {
//调用无参构造函数
this();
//将 c 的元素全部添加到LinkedList中,接着往下看
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
//此时的size 为 0
return addAll(size, c);
}
//然后这个方法的参数意义是：index 为要插入节点的位置，需要注意是往 index 这个节点的 后面！！ 插入（尾差法），
//而不是前面插入，这很关键！！记住这点然后去分析。 参数 c 就是被插入的集合了。
public boolean addAll(int index, Collection<? extends E> c) {
//检查index越界，检查逻辑也很简单 index >= 0 && index <= size，下面贴出了源码
checkPositionIndex(index);
//将被插入集合转换为数组
Object[] a = c.toArray();
//被插入集合的长度
int numNew = a.length;
//如果被插入集合是空的，则后面也没有元素可插了，到此为止。
if (numNew == 0)
return false;
//创建了两个变量，用来方便操作链表。
//pred：记录插入位置的上一个节点
//succ：记录插入位置的下一个节点
//熟悉双向链表，想必就知道为啥要这个两个变量了，为了方便连接。比如我们向index 位置插入了节点Node
//则通过 pred.next = node; node.prev = pred; node.next = succ; succ.prev = node,这样双向连接起来。
Node<E> pred, succ;
//处理一特殊情况，就是插入位置后面没有节点了，那就是插入到最末尾，所以下个节点succ为空，上个节点pred为最后那个节点。
if (index == size) {
succ = null;
pred = last;
} else {
//处理一般情况了，这里返回的是index处节点的下一个节点，而不是index 处的节点，在联想我上面说的尾差法，
//succ 的变量意义是记录新插入节点的上一个节点，所以它现在要成为新节点的下一个节点了。
//该处源码看下文，同时贴出了测试结果。
succ = node(index);
//pred 才是index 出那个节点。现在充当新插入节点的上个节点
//效果就是 pred -> <- succ => pred -> <- new -> <- succ
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;
}
//新节点查完了，需要把后面的节点在后面补上
if (succ == null) {
//后面没节点了，新的尾结点变成我们最后插入的节点了。
last = pred;
} else {
//后面还有节点，给连接上。
pred.next = succ;
succ.prev = pred;
}
//更新 size
size += numNew;
//更新版本号，迭代时候用，判断迭代过程中，LinkedList是否被篡改。
modCount++;
//插入成功！！！
return true;
}
//判断 index 是否越界
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
//返回第 index + 1 处的节点
Node<E> node(int index) {
//这里分情况讨论了，因为linkedList 查找元素只能一个一个的遍历，效率低下，为了提高效率，判断这个位置距离头部近，
//还是尾部近，哪边近则从哪边开始遍历查找，从而减少遍历次数，提高效率。
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
//这里从 i = 0，开始的，相当于是从fist开始（即第一个节点），往后数index 下，不就是index + 1 处的节点嘛
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;
}
}
三、方法分析
- 添加元素。LinkedList 添加方法的API还挺多，，核心逻辑都差不多。
//方法名看起来好像是和把 e 和头结点相连、事实上也确实差不多，是用 e 创建新的节点作为头结点，
//而原先的头结点就作为新头结点的下一个节点
private void linkFirst(E e) {
//获取头结点
final Node<E> f = first;
//使用 e 创建新的节点，并且 pre = null， next = f
final Node<E> newNode = new Node<>(null, e, f);
//更新 fist变量 为 新的头结点
first = newNode;
//如果链表原先是没有节点的，那么头结点当然也是尾结点了。
if (f == null)
last = newNode;
else
//否则尾结点不变，并且将老的头结点连接上新的头结点，因为前面效果是 new -> old,这里之后就是 new -> <- old
f.prev = newNode;
//节点个数+1
size++;
//更新版本号，看到这个字段，应该想到一定是用在迭代器中了，并且是用来防止迭代过程中，
//校验集合是否被修改，实时也确实如此。
modCount++;
}
//前面分析了，那这个也一目了然了，使用e 创建新的节点作为尾结点。
void linkLast(E e) {
//获取尾结点
final Node<E> l = last;
//使用e创建新的节点，并且pre = last ， next = null，效果就是 l <- newNode -> null
final Node<E> newNode = new Node<>(l, e, null);
//更新 last 变量，指向新的尾结点
last = newNode;
//如果原先 链表中没有节点，那尾结点也是头结点。
if (l == null)
first = newNode;
else
//否则，将老的尾结点连接上新的尾结点，效果变成 l -> <- newNode -> null
l.next = newNode;
//节点个数 + 1
size++;
//版本 + 1
modCount++;
}
/**
* Inserts element e before non-null Node succ.
*/
//使用 e 创建新的节点，并且将该节点插入到 succ 节点之前。
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//获取 succ 的上个节点
final Node<E> pred = succ.prev;
//使用 e 创建新的节点，并且是 prev = pred, next = succ, 效果就是 pred <- newNode -> succ
final Node<E> newNode = new Node<>(pred, e, succ);
//变成 pred <- newNode -> <- succ
succ.prev = newNode;
//如果succ就是头结点，那么新的节点插到它前面，那么新插入的节点不就是新的头结点了。
if (pred == null)
first = newNode;
else
//succ不是头结点，效果是 pred -> <- newNode -> <- succ
pred.next = newNode;
//节点个数 + 1
size++;
//版本 + 1
modCount++;
}
//所有的添加相关私有方法说完了，我们常调用的api 就是基于这些操作来的。
//向链表中添加新节点，可见该方法是想链表的尾部添加新的节点
public boolean add(E e) {
//上面分析过了，向尾部添加新节点。
linkLast(e);
return true;
}
//向 index 处添加新节点，是向index处节点的尾部添加新的节点，尾差发。
public void add(int index, E element) {
//检查 index 是否越界
checkPositionIndex(index);
//如果index处就是尾结点，那么直接在尾部插入新的节点
if (index == size)
linkLast(element);
else
//处理不是尾结点的情况。node（index） 在构造方法时说过了，是返回 index + 1 出的节点，在index + 1的前面插入，
//不就是往 index 出的后面插入吗，所以是我们分析的没问题，逻辑一致的。
linkBefore(element, node(index));
}
//插入新的头节点
public void addFirst(E e) {
linkFirst(e);
}
//插入新的尾结点
public void addLast(E e) {
linkLast(e);
}
//还有addAll 方法，在构造方法说过了。
//LinkedList 实现了 List 和 Queue 两个接口，前面是属于List集合相关操作的，LinkedList 也可以作为 队列使用，下面分析作为队列
//时相关的添加元素的方法
//向队列尾部添加元素
public boolean offer(E e) {
return add(e);
}
//向队列头部添加元素
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
//向队列尾部添加元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
//向队列头部添加元素
public void push(E e) {
addFirst(e);
}
- 获取元素方法。
//获取第index + 1 个节点，这个方法基本没用过。。
public E get(int index) {
//检查是否越界
checkElementIndex(index);
return node(index).item;
}
//获取头结点 （只是获取不删除），链表为空，则报错
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
//获取头结点 （只是获取不删除），链表为空，则报错
public E element() {
return getFirst();
}
//获取尾结点 （只是获取不删除）链表为空，则报错
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
//获取头结点 （只是获取不删除），支持链表为空，返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
//获取头结点 （获取且删除），支持链表为空，返回null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
-
扩容方法：链表存储数据所需的内存空间不需要连续的，所以并不需要扩容。添加新元素时，直接连接上即可。
-
移除元素方法：
//这个方法名看起来像是将头结点first断开，可是如果是这样的话，为啥要传参数呢，因为直接可以拿到变量 first。
//实时上，该方法作用就是移除 头结点first，并且这里的参数f就是头结点，这是个私有方法，内部调用之前,这个 f 就是
//被赋值 first，并且做了非空的判断，所以到这里的f 必不为空，且f 必为 First。这样简化了方法里的逻辑。不需要做其他额外判断。
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
//获取 节点f 的值
final E element = f.item;
//获取 节点f 的下一个节点
final Node<E> next = f.next;
//将 节点f 的值设为 null
f.item = null;
//将 节点f 和 下一个节点断开， 效果为 f <- next
f.next = null; // help GC
//将 节点f 设置next，这样设置是为了将 prev 和 next 连接，从而剔除掉 节点f。
first = next;
//如果要删除的节点f是尾结点的话，即当前就只有一个节点，被删除了后，last 也要背设置为null 了。
if (next == null)
last = null;
else
//还有其他节点的情况。 next节点 断开了指向 first。
next.prev = null;
//节点数量 -1
size--;
//版本 + 1
modCount++;
//返回被删除的头结点的值
return element;
}
/**
* Unlinks non-null last node l.
*/
//和上面同样的道理，作用：删除尾结点。且这里的 l 就是 last 尾结点。且必不为空。
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
//获取尾结点的值
final E element = l.item;
//获取尾结点 的上一个节点，该节点后续要作为新的尾结点了
final Node<E> prev = l.prev;
//尾结点值设为null
l.item = null;
//尾结点断开指向上个节点
l.prev = null; // help GC
//设置新的尾结点，即prev
last = prev;
//如果链表只有一个节点，那么删除了，头结点也要设置为null了，因为整个链表没有节点了
if (prev == null)
first = null;
else
//不止一个节点的情况。将新的尾结点的next 设置null
prev.next = null;
//节点个数 - 1
size--;
//版本 + 1
modCount++;
//返回要删除的节点值
return element;
}
/**
* Unlinks non-null node x.
*/
//删除节点 x ，且 x 比不为null
E unlink(Node<E> x) {
// assert x != null;
//x 节点的值
final E element = x.item;
//x 节点的上一个节点
final Node<E> next = x.next;
//x 节点的下一个节点
final Node<E> prev = x.prev;
//如果 x 节点就是头结点的话，那么新的头结点就是next了。
if (prev == null) {
first = next;
} else {
//节点x节点不是头结点，所以上个节点指向 x节点 的下一个节点。
//prev -> <- x -><- next => prev-> next 且 prev <- x -> <- next
prev.next = next;
//断开 x节点 指向上个节点, 变成 prev-> next 且 x -> <- next
x.prev = null;
}
//同样的如果删除的 x节点 是尾结点，那么上个 节点prev 就是新的尾结点了。
if (next == null) {
last = prev;
} else {
//x 节点不是尾结点的情况。 变成 prev-> <- next 且 x -> next
next.prev = prev;
//变成 prev-> <- next 且 x -> null ,这样 节点x 就彻底断开了，并且prev 和 next连接上了。
x.next = null;
}
//设置 x节点 的值为null。方便 gc
x.item = null;
//元素个数 - 1
size--;
//版本 + 1
modCount++;
//返回 被删除节点x 的值
return element;
}
//将头结点删除
public E removeFirst() {
//获取头结点
final Node<E> f = first;
//头结点为空则报错
if (f == null)
throw new NoSuchElementException();
//将头结点断开
return unlinkFirst(f);
}
//删除尾结点
public E removeLast() {
//获取尾结点
final Node<E> l = last;
//尾结点为空则报错
if (l == null)
throw new NoSuchElementException();
//将尾结点断开
return unlinkLast(l);
}
//根据对象删除节点
public boolean remove(Object o) {
//从这里也可以看出，LinkedList 是支持存储null和删除null 的。
//如果链表中又重复的值，删除的是靠近头结点的那一个值，而不是都删除
//处理 null 的情况，从头结点开始遍历
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
//断开节点x
unlink(x);
return true;
}
}
} else {
//处理非 null 的前框，从头结点开始遍历
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
//断开节点x
unlink(x);
return true;
}
}
}
//如果没找到这个值，则返回 false，删除失败
return false;
}
//删除 第 index+ 1 个节点
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//最为队列的相关方法 -------------------------------
//删除头结点
public E remove() {
return removeFirst();
}
//获取头结点值并删除，如果链表为空，则返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
//获取尾结点值并删除，如果链表为空，则返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
//获取头结点的值，并删除头结点
public E pop() {
return removeFirst();
}
- 迭代器：LinkedList 只提供了一个 ListItr 迭代器，并提供了迭代过程中操作集合的方法，LinkedList 的迭代器使用非常非常少，一般LinkedList 被用来作为队列，操作头部和尾部，迭代器部分的代码有兴趣的可以自己看看。
四、总结
- LinkedList 使用双向链表来存储元素，不需要连续的内存空间来存储元素，所以不需要扩容。
- 一般作为队列，直接操作头部和尾部。支持存储或删除相同的元素，且支持存储null，存储的元素有序。存在相同多个值是，会删除靠近头结点的值。
- 查找元素只能遍历查找，效率慢O(n)，删除，插入快O（1）。根据元素值查找，只能从头结点开始遍历。如果根据 位置查找，会从距离头结点或尾结点近的一方开始遍历。
- 不是线程安全的。
