Java集合源码:(二) LinkedList源码解析(JDK8)

集合整体架构文章:

罗政:JAVA 集合整体架构


LinkedList 底层是双向链表,它的增删只需要移动指针即可,故 时间效率较高 不需要批量扩容 也不需要预留空间 ,所以 空间效率 ArrayList

缺点就是需要 随机访问 元素时, 时间效率很低 ,虽然底层在根据下标查询Node的时候,会根据index判断目标Node在前半段还是后半段,然后决定是 顺序还是逆序查询 以提升时间效率 。不过随着n的增大,总体时间效率依然很低。


源码分析


成员变量

transient int size = 0;   // 当前元素个数
transient Node<E> first;  // 链表的头结点
transient Node<E> last;   // 链表的尾节点

//  链表的 每个节点
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;
	}
}

构造函数

 public LinkedList() {
  // 空空如也
 }

addFirst源码

public void addFirst(E e) {
    linkFirst(e);
}

private void linkFirst(E e) {
        // 全局的头结点指针
	final Node<E> f = first;
        // 构造新节点,元素填充为e , 新节点的next指向原来的头结点 ,也就是头部添加
	final Node<E> newNode = new Node<>(null, e, f);
	first = newNode;  // 让first指向新节点
	if (f == null) // 第一次的话 f为空。
		last = newNode;  //让 全局last尾指针也指向这个新节点
	else
		f.prev = newNode; // 让原来的头节点的prev指向这个新节点
	size++;  //元素值 ++
	modCount++;  // 修改次数 ,跟ArrayList 一样
}

我们来画个图来理解,当第一次addFirst 元素e后 ,链表变成这样:

https://pic3.zhimg.com/v2-44c6d92fd13dbff590dd980b092e0d2e_b.jpg

然后又addFrist 元素g 后, 链表成这样:

也就是添加到链表的表头,为什么会有first,last指针,文章后面在讲。

getFirst()源码

    public E getFirst() {
        // 直接取头结点得出结果
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

看到没有,为什么要有first,就是便于找到链表的头结点。(last节点也是一个道理)

removeFirst() 源码

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    private E unlinkFirst(Node<E> f) {  // f 是 first头结点
        // 把元素取出来,给方法返回
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;  // first 节点指向next
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--; // 元素个数size减减
        modCount++;
        return element;
    }

removeFirst 就是把first节点置为null回收,然后把first指向原来first的next节点。


E get(int index) 源码

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
  Node<E> node(int index) {
        // assert isElementIndex(index);
        if (index < (size >> 1)) {// index 在0 到 size/2 之间
            Node<E> x = first; // 离first 节点近,所以利用first从前往后找
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { // index 大于了一半
            Node<E> x = last;  // 离last近,利用last 从后往前找
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

>> : 右移运算符,num >> 1,相当于num除以2 高位补0。

这个骚操作还是可以的 : 把链表折成两半,如果要找的index在前半段就拿fisrt正序遍历,否则就拿last反序遍历。


public void add(int index, E element) 源码

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);//  把e 节点放到链表的尾部last
        else
            linkBefore(element, node(index)); // 把element 链到 指定index位置节点 的前一个节点
    }
    Node<E> node(int index) {  // 折半找 index 下标的节点
        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;
        }
    }
    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++;
    }
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

可见add 的复杂度就在于 折半找index 位置 节点 的复杂度。


总结 LinkedList 和 ArrayList

LinkedList 本质是个链表,所以通过Iterator来插入和移除操作的耗时,都是个恒量,但如果要获取某个位置的元素,则要做指针遍历( 注意是折半,很多网站博客都是直接O(n) )。因此,get操作的耗时会跟List长度有关。


对于ArrayList来说,得益于快速随机访问的特性,获取任意位置元素的耗时,是常量的。但是,如果是add或者remove操作,要分两种情况,如果是在尾部做add,也就是执行add方法(没有index参数),此时不需要移动其他元素,耗时是O(1),但如果不是在尾部做add,也就是执行add(int index, E element) ,这时候在插入新元素的同时,也要移动该位置后面的所有元素,以为新元素腾出位置,此时耗时是O(n-index)。另外,当List长度超过初始化容量时,会自动生成一个新的array(长度是之前的1.5倍),此时会将旧的array移动到新的array上,这种情况下的耗时是O(n)。

注意: 两者都是线程不安全的!!!多线程情况下千万别用!!


强烈推荐一个 进阶 JAVA架构师 的博客

https://pic2.zhimg.com/v2-1e8deea0c94dab83067a8eca4007734d_ipico.jpg

支付宝打赏 微信打赏

如果文章对您有帮助,您可以鼓励一下作者