基于jdk12的LinkedList源码阅读分析
LinkedList是Java集合框架中一个重要的实现，底层采用双向链表结构。和ArrayList一样，其也支持null值和重复值。它基于双向链表实现，就不用扩容了，可这也就是说，在维护结点的时候需要额外的空间存储前驱和后继的引用。在链表头部和尾部插入效率比较高，但是在指定位置插入就不太行了，原因是定位需要O（N）的时间复杂度，这也就是说查找的效率也不太行。最后，他是非线程安全集合类。
二、源码阅读部分
1.声明部分：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
复制代码
可以看出它继承了AbstractSequentialList，查看AbstractSequentialList的源码，发现里面实现了增删查，很多都是基于iterator实现的。不用LinkedList自己重新实现了其中的一套方法，此外说一点，一般建议声明明队列的时候： Queue<T> queue = new LinkedList<>();
而且建议用LinkedList实现Stack。因为原生的 Stack<T> stack = new Stack<>();
有很多问题。
2.get方法：
public E get(int index) {
//检查index是否合理
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
// 如果index是小于size的二分之一，这设计的很巧妙
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;
}
}
复制代码
3.add方法：
//单参，在链表尾部插入元素
public boolean add(E e) {
linkLast(e);
return true;
}
//双参，在指定位置加入元素
public void add(int index, E element) {
//老规矩先检查
checkPositionIndex(index);
//如果index就是size，就直接在末尾加
if (index == size)
linkLast(element);
//否则在指定位置之前插
else
linkBefore(element, node(index));
}
/**
* Links e as last element.
* 将e插入最后一位
*/
void linkLast(E e) {
final Node<E> l = last;
//初始化新结点，指明前驱为l，后继为null
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
//如果链表为空，就直接插第一个
if (l == null)
first = newNode;
//前面把last给l了，则直接把新插入的元素插到l的后面
else
l.next = newNode;
//改变了原有数据结构，操作数加一
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
* 在非空结点之前插入e
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//前提就是当前结点不空
final Node<E> pred = succ.prev;
//初始化新结点，指明前驱为pred，后继为当前结点succ
final Node<E> newNode = new Node<>(pred, e, succ);
//让succ的前驱指向新结点
succ.prev = newNode;
//如果pred为空，表明当前元素是第一个元素，或者当前链表为空
if (pred == null)
first = newNode;
//否则，succ的前驱的后继变成了新加入的结点
else
pred.next = newNode;
//改变了原有数据结构，操作数加一
size++;
modCount++;
}
复制代码
按照索引插入的过程大概就是：
- 创建新结点，并指明新结点的前驱和后继
- 将succ的前驱引用指向新结点
- 如果succ的前驱不空，则将succ的前驱的后继指向新结点
4.remove方法：
public boolean remove(Object o) {
//前面说过，LinkedList里面是可以塞空的，所以这就先在里面找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) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//解除链接
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//prev为null表示x第一个元素，直接让first指向x的后继就行
if (prev == null) {
first = next;
} else {
//否则就是x前驱的后继直接赋给x的后继，并让x的前驱引用为null，即释放x与前驱的连接
prev.next = next;
x.prev = null;
}
//next为null表示x为最后一个元素，直接让last指向x的前驱就行
if (next == null) {
last = prev;
} else {
//否则就是x后继的前驱直接赋给x的前驱，并让x的后继引用为null，即释放x与后继的连接
next.prev = prev;
x.next = null;
}
//清除x的数据，方便GC回收
x.item = null;
//改变数据结构
size--;
modCount++;
return element;
}
复制代码
删除的时候断开连接的步骤小结（假设x既不是头也不是尾）：
- 将待删除结点x的前驱的后继指向x的后继
- 将x的前驱引用置空，断开x与前驱的连接
- 将待删除结点x的后继的前驱指向x的前驱
- 将x的后继引用置空，断开x与后继的连接
三、写在最后
最后在讲一下基于LinkedList实现的Queue里面的一些常用方法，方便后续学习：
查看Queue接口，里面有这些方法：
在队尾增加元素： boolean add(E e);
在队尾增加元素： boolean offer(E e); //这个元素内部就是调用add方法，不再赘述
删除元素：
E remove();
//这个是Queue特有的remove
public E remove() {
return removeFirst();
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
复制代码
出队并取得之： E poll();
//出队并且取得队首操作，不赘述了。
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
复制代码
取得队首元素： E element();
取得队首元素： E peek();
public E peek() {
//和上面的区别就是这个peek可以在队空的情况下返回null，上面element()则直接报异常
final Node<E> f = first;
return (f == null) ? null : f.item;
}
复制代码
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
