转载

基于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;
}
复制代码

原文 https://juejin.im/post/5ebf47835188255b0166af26

正文到此结束

所属分类：编程技术 Java

本文标签： 线程 http LinkedList final 索引 https list 集合类 node 空间 id 时间 Java集合源码代码 IO zab java 数据 queue equals 安全删除 ArrayList
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

基于jdk12的LinkedList源码阅读分析

二、源码阅读部分

1.声明部分：

2.get方法：

3.add方法：

4.remove方法：

三、写在最后

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流