JDK源码解析之LinkedList

 

前言：

    上一篇博客 介绍了我们最常用的一种集合类型ArrayList，看完源码之后，我们知道，其底层是基于数组来实现的。

    今天介绍一下另外一种List，底层是基于链表来实现的。

    从网络上截一个图（如有侵权，请联系作者），简单表示下链表结构

    可以看到，证个链表有head和tail元素，每一个元素都有element（当前元素值）、pre（指向上一个元素）、next（指向下一个元素）

    通过这种结构，可以遍历获取每一个节点

 

1.LinkedList结构、成员变量分析

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable
{
    transient int size = 0;

    // 头元素
    transient Node first;

    // 尾元素
    transient Node last;

// Node
private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

    由上可知：我们的链表是双端双向链表，可以从头操作，也可以从尾开始操作，可以向前操作，也可以向后操作

    注意：还有一点需要说明的是ArrayList实现了RandomAccess接口，而LinkedList则没有实现这个接口？这个接口是一个空接口，那这个接口有什么作用呢？

    笔者是看到Collections.binarySearch()方法的时候才对这方面有疑惑，更多内容可参考网友的一篇博客：https://blog.csdn.net/weixin_39148512/article/details/79234817 

 

2.构造方法

// 空参构造方法
public LinkedList() {
}

// 集合构造
public LinkedList(Collection