LinkedList原理及用法详解(6大用法）

LinkedList原理及用法详解(6大用法）-mikechen

LinkedList简介

LinkedList 是 Java 集合中比较常用的数据结构，与 ArrayList 一样，实现了 List 接口，只不过 ArrayList 是基于数组实现的，而 LinkedList 是基于链表实现的。

LinkedList继承于AbstractSequentialList，并且实现了Deque接口。

LinkedList原理及用法详解(6大用法）-mikechen

LinkedList数据结构

LinkedList 的数据结构是一个双向链表，它有两个成员变量：first 和 last，分别指向双向队列的头和尾。

Node<E> first;
Node<E> last;

LinkedList原理及用法详解(6大用法）-mikechen

这里“双向”的含义是相对单链表而言的，双向链表的节点不仅有后继，还有前驱。LinkedList 中双向链表的节点是一个个的 Node，它是 LinkedList 的一个静态内部类。其定义如下。Node 是一个泛型类，泛型参数是存放在 LinkedList 中的值的类型。

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构造函数

// 默认构造函数
LinkedList()

// 创建一个LinkedList，保护Collection中的全部元素。
LinkedList(Collection<? extends E> collection)

LinkedList 提供了两个构造方法：LinkedList() 和 LinkedList(Collection<? extends E> c)。

LinkedList() 仅仅构造一个空的列表，没有任何元素，size = 0，first 和 last 都为 null。

LinkedList(Collection<? extends E> collection)构造一个包含指定 Collection 中所有元素的列表，该构造方法首先会调用空的构造方法，然后通过 addAll() 的方式把 Collection 中的所有元素添加进去。

LinkedList属性

LinkedList 提供了以下三个成员变量，size，first，last，源码如下：

 transient int size = 0;
 transient Node<E> first;
 transient Node<E> last;

其中 size 为 LinkedList 的大小，first 和 last 分别为链表的头结点和尾节点。Node 为节点对象。

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;
	}
}

Node 是 LInkedList 的内部类，定义了存储的数据元素，前一个节点和后一个节点，典型的双链表结构。

LinkedList常用方法

1. add(E e)

大家都在说LinkedList插入、删除操作效率比较高，以stringList.add(“猪八戒”)为例来看到底发生了什么？

@Test
public void add() {
    LinkedList xiyouList = new LinkedList();
    xiyouList.add("猪八戒");
}
复制代码

在LinkedList中我们找到add(E e)方法的源码

public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 设置元素e为最后一个元素，这个方法在添加元素到指定位置的时候也会被调用
*/
void linkLast(E e) {
    final Node<E> l = last;
  	// 添加e 到list 的尾部，那么此时的last 则成为e 的前置，那么e 的后置则是null
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
      	// last 为null 意味着是空表，此时e(newNode) 则成为first
        first = newNode;
    else
      	// 否则 e(newNode) 则成为 last 的后置
        l.next = newNode;
  	// 记录当前元素数的多少和记录修改
    size++;
    modCount++;
}
复制代码

针对上面的if-else 两种情况，我们下面分别梳理一下：

情况1：假如xiyouList为空，那么添加进来的node就是first，也是last，这个node的prev和next都为null;

情况2：假如xiyouList不为空，那么添加进来的node就是last，node的prev指向以前的最后一个元素，node的next为null；同时以前的最后一个元素的next.

2. add(int index, E element)

接下来我们看一下add 的一个变体方法 add(int index, E element)，例如xiyouList(1, “猪八戒”)

@Test
public void add() {
    LinkedList xiyou = new LinkedList();
    xiyou.add(1,"猪八戒");
}
复制代码

通过跟踪源代码，可以看到它调用了这个方法

/**
 * Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
 * 在此列表的指定位置插入指定的元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动，然后将要插入的元素进行插入
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
//在指定位置添加一个元素
public void add(int index, E element) {
  	// 检测下标的合法性
    checkPositionIndex(index);
  	// 下标合法之后，则判断是不是添加到集合尾部，index=size 的时候则是添加到集合的尾部
    if (index == size)
        linkLast(element);
  	// 否则则是添加到集合的index 位置(index 不是最后一个位置)
    else
      // 因为不是添加到最后，所以这个里可以得到这个位置当前的元素，node(index) 
        linkBefore(element, node(index));
}
复制代码

checkPositionIndex

我们先看一下，这个检测下标合法性的方法

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
      	// 这个就是如果下标不合法的时候抛出的异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
 * Tells if the argument is the index of a valid position for an iterator or an add operation.
 * 在调用add或者 遍历 方法时候，判断一个下标是否合法
 */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}
复制代码

linkLast

这个时候，其实和add(E element) 方法一样了，因为index=size ,本质上就是添加到链表末尾，前面已经解释过这个方法的代码了，这里就不解释了

/**
 * Links e as last element. 将e 作为last 元素连接起来，其实就是添加到链表末尾
 */
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++;
}
复制代码

linkBefore

因为这个时候，已经知道不是添加在last 的位置了，所以一定是在非空节点之前添加的

/**
 * 在一个非空节点前插入一个元素，succ 是传入的当前位置上已经存在的元素，接下来要做的就是将e 和 succ 连接起来
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
  	// succ 的前置
    final Node<E> pred = succ.prev;
  	// succ 作为e 的后置，succ 的前置作为e 的前置，其实就是将  succ_pree <-> succ <-> succ_next  变成  succ_pree  <-> e <->succ <-> succ_next
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
  	// 如果pree是null ,则e 要代替succ 成为新的first
    if (pred == null)
        first = newNode;
    else
      	// 否则的话，e 成为succ 前置的后置
        pred.next = newNode;
  	// 记录修改
    size++;
    modCount++;
}
复制代码

其实从代码中看到和add(E e)的代码实现没有本质区别，都是通过新建一个Node实体，同时指定其prev和next来实现，不同点在于需要调用node(int index)通过传入的index来定位到要插入的位置，这个也是比较耗时的

其实看到这里，大家也都明白了。

LinkedList插入效率高是相对的，因为它省去了ArrayList插入数据可能的数组扩容和数据元素移动时所造成的开销，但数据扩容和数据元素移动却并不是时时刻刻都在发生的。

3. get(int index)

我们知道随机读取元素不是LinkedList所擅长的，读取效率比起ArrayList也低得多，那么我们来看一下为什么，其实开始之前我们大概都能猜到为什么了，因为我们在类的说明书里，已经解释了一部分了因为它的本质还是遍历操作，其实就是一个O(n) 的操作而不是一个O(1) 的操作

下面我们还是具体看一下

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
复制代码

checkElementIndex 方法就是在检测下标是否合法，而node 方法前面我们已经说过了，就是返回特定位置的节点，所以下面我们看一下具体是怎么检测的

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * Tells if the argument is the index of an existing element.
 */
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}
复制代码

其实就是限定了下标的范围，其实如果你仔细看了add 那一部分的代码的话，你会发现这一部分代码和上面的非常相似，唯一的区别在于目的上，一个是检测插入的位置是否合法，而这个方法是检测获取的位置时是否合法，所以叫isElementIndex而不是叫isPositionIndex，因为目的的不同导致了条件的不同，获取时候index必须小于size,因为size 的地方是空，但是插入的时候则就可以

从上述代码中我们可以看到get(int index)方法是通过node(int index)来实现的，而node它的实现机制是：

比较传入的索引参数index与集合长度size/2，如果是index小，那么从第一个顺序循环，直到找到为止；如果index大，那么从最后一个倒序循环，直到找到为止。也就是说越靠近中间的元素，调用get(int index方法遍历的次数越多，效率也就越低，而且随着集合的越来越大，get(int index)执行性能也会指数级降低。

因此在使用LinkedList的时候，我们不建议使用这种方式读取数据，可以使用**getFirst()，getLast()**方法，将直接用到类中的first和last变量。

4. removeFirst()和removeLast()

这里removeFirst()和removeLast()非常相似，会用到类中定义的first和last变量，所以这里我们只说removeFirst，大家可以自行去看removeLast

/**
 * Removes and returns the first element from this list. 移除list 中的第一个元素
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node<E> f = first;
  	// 如果f是null 的话，则抛出异常，这里个人觉得不应该抛出异常，直接返回null 就行了，否则你每次调用这个方法的时候还得判断一下是否是空list
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Unlinks non-null first node f. 取消first 的连接
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
   // help GC，为啥f 不直接赋值成null 呢
    f.item = null;
    f.next = null;
    first = next;
    if (next == null)
        last = null;
    else
      // 因为next 已经成为first 了，应该是没有前置了
        next.prev = null;
    size--;
    modCount++;
    return element;
}
复制代码

5. remove(Object o) 和 remove(int index)

我们看一下remove(Object o) 和 remove(int index)源码

//删除某个对象
public boolean remove(Object o) {
    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;
}
//删除某个位置的元素
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
//删除某节点，并将该节点的上一个节点（如果有）和下一个节点（如果有）关联起来
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}
复制代码

其实实现都非常简单，先找到要删除的节点，remove(Object o)方法遍历整个集合，通过 == 或 equals方法进行判断；remove(int index)通过node(index)方法。

6. LinkedList遍历性能对比

我们主要列举一下三种常用的遍历方式，普通for循环，增强for循环，Iterator迭代器，当然遍历中还有一个问题就是快速失败的问题，但是这里就不再举例子了，因为前面文章已经写了好多了，大家可以自行尝试，也可以参考前面其他集合的文章

public static void main(String[] args) {
    LinkedList<Integer> list = getLinkedList();
    //通过快速随机访问遍历LinkedList
    listByNormalFor(list);
    //通过增强for循环遍历LinkedList
    listByStrengThenFor(list);
    //通过快迭代器遍历LinkedList
    listByIterator(list);
}

/**
 * 构建一个LinkedList集合,包含元素50000个
 * @return
 */
private static LinkedList<Integer> getLinkedList() {
    LinkedList list = new LinkedList();
    for (int i = 0; i < 50000; i++){
        list.add(i);
    }
    return list;
}

/**
 * 通过快速随机访问遍历LinkedList
 */
private static void listByNormalFor(LinkedList<Integer> list) {
    // 记录开始时间
    long start = System.currentTimeMillis();
    int size = list.size();
    for (int i = 0; i < size; i++) {
        list.get(i);
    }
    // 记录用时
    long interval = System.currentTimeMillis() - start;
    System.out.println("listByNormalFor：" + interval + " ms");
}

/**
 * 通过增强for循环遍历LinkedList
 * @param list
 */
public static void listByStrengThenFor(LinkedList<Integer> list){
    // 记录开始时间
    long start = System.currentTimeMillis();
    for (Integer i : list) { }
    // 记录用时
    long interval = System.currentTimeMillis() - start;
    System.out.println("listByStrengThenFor：" + interval + " ms");
}

/**
 * 通过快迭代器遍历LinkedList
 */
private static void listByIterator(LinkedList<Integer> list) {
    // 记录开始时间
    long start = System.currentTimeMillis();
    for(Iterator iter = list.iterator(); iter.hasNext();) {
        iter.next();
    }
    // 记录用时
    long interval = System.currentTimeMillis() - start;
    System.out.println("listByIterator：" + interval + " ms");
}
复制代码

执行结果如下：

listByNormalFor：1067 ms
listByStrengThenFor：3 ms
listByIterator：2 ms
复制代码

通过普通for循环随机访问的方式执行时间远远大于迭代器访问方式，这个我们可以理解，在前面的get(int index)方法中已经有过说明，那么为什么增强for循环能做到迭代器遍历差不多的效率？

通过反编译工具后得到如下代码

public static void listByStrengThenFor(LinkedList<Integer> list)
  {
    long start = System.currentTimeMillis();
    Integer localInteger;
    for (Iterator localIterator = list.iterator(); localIterator.hasNext(); 
         localInteger = (Integer)localIterator.next()) {}
    long interval = System.currentTimeMillis() - start;
    System.out.println("listByStrengThenFor：" + interval + " ms");
}
复制代码

很明显了，增强for循环遍历时也调用了迭代器Iterator，不过多了一个赋值的过程。

还有类似于pollFirst()，pollLast()取值后删除的方法也能达到部分的遍历效果。

陈睿mikechen

10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。

关注「mikechen」公众号，获取更多技术干货！

后台回复【面试】即可获取《史上最全阿里Java面试题总结》，后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》

LinkedList原理及用法详解(6大用法）

LinkedList简介

LinkedList数据结构

LinkedList构造函数

LinkedList属性

LinkedList常用方法

1. add(E e)

2. add(int index, E element)

checkPositionIndex

linkLast

linkBefore

3. get(int index)

4. removeFirst()和removeLast()

5. remove(Object o) 和 remove(int index)

6. LinkedList遍历性能对比

陈睿mikechen

分布式数据层中间件详解：如何实现分库分表+动态数据源+读写分离

Quartz框架详解(看这篇就够了)

最全多线程经典面试题和答案

常见分布式文件存储介绍、选型比较、架构设计

史上最强消息队列MQ万字图文总结！