LinkedList

前言

本文作为我学习 Java 集合 LinkedList 的一个记录与总结，如有疏漏或不足之处欢迎指出共同进步！

一、LinkedList 简介

1.1 LinkedList 概述

LinkedList 是可以动态增长或缩减的索引序列，其底层是基于双向链表实现的
LinkedList 类内部维护了一个双向链表，因此可以完成高效的的插入和删除，但由于顺序存取的原因其查询效率不如 ArrayList ，后者可以通过 index 直接取得相应的值。
LinkedList 与 ArrayList 一样是线程不安全的，并发场景可使用 CopyOnWriteArrayList
LinkedList 实现了 Deque 接口，因此其可以作为栈，队列，双端队列来使用
继承结构：

JAVA 集合之 LinkedListLinkedList

1.2 LinkedList 底层数据结构

LinkedList 的底层数据结构为双向链表，其能存放任何元素 (包括 null)，如下图所示双向链表每个节点由

JAVA 集合之 LinkedListLinkedList

三个成员组成：

ele ：链表节点存储的元素

prev ：当前节点的前一个节点

next：当前节点的下一个节点

此外还有 first 和 last 只想链表的头节点和尾节点，头节点的 prev 指向 null，尾节点的 next 指向 null。

二、LinedList 源码分析

2.1 继承类与接口实现

JAVA 集合之 LinkedListLinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, Serializable

继承类
- LinkedList extends AbstractSequentialList
- AbstractSequentialList extends AbstractList

从整个继承结构中可以看到 LinkedList 相比于 ArrayList 其上面多了一层 AbstractSequentialList，而这个抽象类继承自 AbstractList。从源码中的注释可以发现这个抽象类的作用：

JAVA 集合之 LinkedListLinkedList

这两段话总结下来就是俩点：

这个抽象类实现了一些顺序存取的 List 的通用方法以减少继承类的代码量
这个抽象类的实现与 AbstractList 相反，比如 add()，get() 等方法，因为其为顺序存取结构，而 AbstractList 则是随机存取，如果想要实现顺序存取应该继承此抽象类，而随机存取应该继承 AbstractList
实现接口
- List 接口：LinkedList 实现这个接口的原因应该与 ArrayList 一样属于一个小错误
- Deque 接口：拥有双端队列的各种特性，即 LinkedList 可以看作双端队列的一种实现
- Cloneable 接口：实现了这个接口就可以使用 clone() 方法
- Serializable 接口：实现了这个接口表明该类是可序列化的
- 注意与 ArrayList 不同 LinkedList 没有实现 RandomAccess 这是因为 LinkedList 是顺序存储的结构，因此遍历 LinkedList 应该使用 iterator

2.2 成员属性

// 版本号
private static final long serialVersionUID = 876323262645176354L;
// LinkedList 的 Size
transient int size = 0;
// 双向链表的头节点
transient Node<E> first;
// 双向链表的尾节点
transient Node<E> last;

其中

Node<E>

为内部类，其结构就如 1.2 节中展示的数据结构。

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

2.3 构造方法

JAVA 集合之 LinkedListLinkedList

LinkedList()
```
public LinkedList() {
}
           
```
LinkedList 的空构造，初始化一个空的 LinkedList
LinkedList(Collection<? extends E> c)
```
public LinkedList(Collection<? extends E> c) {
    	// 调用空构造
        this();
    	// 将集合 c 中的元素全部初始化到 LinkedList 中
        addAll(c);
    }
           
```
在这个构造函数中调用了 addAll() 方法其具体内容在下文核心方法一节会具体阐述，其作用是将传入的集合 c中的元素初始化为 LinkedList 的元素

2.4 核心方法

LinkedList 的核心方法有 add()、get()、set()、remove()、indexOf()

2.4.1 add() 方法

JAVA 集合之 LinkedListLinkedList

LinkedList 中共有 6 个 add 方法，其中最后俩个

addFirst()

和

addLast()

需要在初始化时指定类型为 LinkedList 或 Deque 才能使用，其为双端队列的方法，本文着重讲述 List 相关内容，因此不详细阐述这俩个方法。

add(E e)

public boolean add(E e) {
    	// 调用 linkLast 方法将元素连接在链表尾部
        linkLast(e);
        return true;
    }

add(E e)

方法在 LinkedList 最后添加一个元素其内部调用了 linkLast() 方法：

void linkLast(E e) {
    	// 将尾部指针 last 赋给临时变量 l
        final Node<E> l = last;
    	// 创建一个新的 node 其 pre 指向 l，元素值为 e，next 指向 null
        final Node<E> newNode = new Node<>(l, e, null);
    	// 尾指针指向新节点
        last = newNode;
        if (l == null)
            // 若链表原来为空那么将头指针也指向此节点
            first = newNode;
        else
            // 如果不为空则将原来的尾部节点指向新节点
            l.next = newNode;
        size++;
    	// modCount 表示 LinkedList 中添加或删除的次数
        modCount++;
    }

从 linkLast 可以看到在调用

add()

方法后会创建一个新节点并连接到原来链表的最尾部，此过程只需要创建一个新的 node 对象并修改若干指针，相比于 ArrayList 的数组复制 LinkedList 在添加元素方面更加高效。

add(int index, E e)

public void add(int index, E element) {
    	// 判断 index >= 0 && index <= size
        checkPositionIndex(index);
		// 如果 index == size 直接在链表尾部添加元素
        if (index == size)
            linkLast(element);
        else
            // 调用 linkBefore() 方法在指定 index 处插入元素
            linkBefore(element, node(index));
    }

add(int index, E e) 方法中核心的语句就是

linkBefore(element, node(index))

其中调用了

node()

方法来获取 index 位置上的节点，然后调用

linkBefore()

来在此节点之前插入元素，接下来看一下源码：

Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

node()

的代码很简单先判断 index 距离那一端更近，然后遍历找到 index 所对应的那个 node 节点，从这就可以看到底层为双向链表的一个好处，可以一定程度上的减少遍历花销的时间。

void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
    	// 取得 index 所指节点的前一个节点
        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++;
    }

linkBefore()

此方法就是执行了链表插入的一些基本操作，取得 index 节点的前一个节点，将前一个节点的 next 指向新节点，将新节点的 next 指向 index 节点。

addAll(Collection c)

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

方法中调用了另一个

addAll(int index, Collection c)

方法，参照上面两个

add()

方法的关系可以猜到此方法的作用就是在 LinkedList 按顺序依次添加集合 c 中的所有元素，因此我们重点看下其调用的

addAll()

方法。

addAll(int index, Collection c)

public boolean addAll(int index, Collection<? extends E> c) {
        // 确保索引不越界
    	checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
    	// 如果 index == size 直接在末尾添加
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            // 在中间插入，先取得 index 对应的 node 节点，即其前一个节点
            succ = node(index);
            pred = succ.prev;
        }
		// 遍历集合 c 中的元素并插入到链表中
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }

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

        size += numNew;
        modCount++;
        return true;
    }

整体代码比较简单，其作用就是在 index 处插入集合 c 中的全部元素，基本都为链表的基本操作。

add()

方法总结：

从四个 add() 方法可以看到，LinkedList 由于底层使用双向链表实现在在添加新元素时只需要创建新节点并修改若干指针即可，因此其修改效率很高。
因为 LinkedList 只能顺序存取，因此在需要遍历整个链表的场合会先判断距离 first 和 last 那一端更近，以此来减少遍历的时间。

2.4.2 get() 方法

JAVA 集合之 LinkedListLinkedList

与

add()

方法相同，

get()

方法中

getFirst()

和

getLast()

都是实现的 Deque 接口的方法本文中不再详细叙述。

get(int index)
```
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
           
```
这个方法很简单其中调用的方法之前也详细的讲过，通过 node() 方法取得 index 对应的节点后返回其元素值。

2.4.3 set() 方法

set(int index, E e)

public E set(int index, E element) {
    checkElementIndex(index);
    // 通过 node() 方法来的到 index 所对应的那个节点
    Node<E> x = node(index);
    E oldVal = x.item;
    // 设置节点中新的元素值
    x.item = element;
    return oldVal;
}

set()

方法核心依然是

node()

方法，其通过

node()

方法得到 index 所对应的节点，然后新的元素值赋值给节点的 item 属性。

2.4.4 remove() 方法

remove(Object o)

public boolean remove(Object o) {
    // 判断传入元素是否为 null
    if (o == null) {
        // 遍历链表寻找相等的元素
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                // remove() 方法的核心 unlink() 其作用为将一个指定的节点从链表中删除
                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;
}

方法的核心就在于

unlink()

方法，老样子查看一下其源码看看到底做了什么。

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;

    if (prev == null) {
        first = next;
    } else {
        // 将当前节点的前一个节点的 next 指向当前节点的后一个节点
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        // 将当前节点的后一个节点的 prev 指向当前节点的前一个节点
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink()

方法的核心就是获得当前节点的前后节点然后通过修改前后节点的链接来将当前节点排除出链表，之后将当前节点的元素值置为 null 让 gc 机制更快的回收节点，如果整个过程不明白可以在纸上画一画图来帮助理解。

set(int index)
```
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
           
```
前文分析了 node() 和 unlink() 方法，那么这个通过 index 来删除指定的元素的方法就不难理解了。

2.4.5 indexOf() 方法

indexOf(Object o)

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

与

remove(Object o)

异曲同工，只不过其是找到节点并将其删除，

indexOf()

是找到节点返回其 index 的值，需要注意的是两者都只能处理找到的第一个满足条件的节点。

三、LinkedList 迭代器

3.1 内部类 ListItr

JAVA 集合之 LinkedListLinkedList

上图为内部类 ListItr 的详细信息，可以看到这个内部类实现了 ListIterator 接口，从这个接口的注释中可以探查目的是为了那种能够从两边变量的 List 类型而提供方法，此外还提供了在迭代过程中用于修改 List 结构的

add()

和

remove()

方法。

JAVA 集合之 LinkedListLinkedList

从其提供的方法可以看到 LinkedList 不仅可以向后迭代，也可以向前迭代方法如下：

public class ArrayTest {
    public static void main(String[] args) {
        LinkedList<Person> list = new LinkedList<Person>();
        list.add(new Person(35, "张三", "男"));
        list.add(new Person(30, "李四", "男"));
        list.add(new Person(29, "王五", "男"));
        list.add(new Person(29, "刘六", "男"));
        // 获取一个类型为 ListIterator 的迭代器，并将初始游标位置设定在 index = size() 处
        ListIterator<Person> iterator = list.listIterator(list.size());
        // 向前迭代 LinkedList
        while(iterator.hasPrevious()){
            System.out.println(iterator.previous());
        }

    }
}
class Person {
    int age;
    String name;
    String sex;

    public Person() {
    }

    public Person(int age, String name, String sex) {
        this.age = age;
        this.name = name;
        this.sex = sex;
    }

}

结果:

JAVA 集合之 LinkedListLinkedList

此外还能看到，迭代器内部提供了

remove()

和

add()

方法因此在迭代过程中可以对 LinkedList 进行结构性的改变，但不能调用 LinkedList 自己的方法，否则会导致 ConcurrentModificationException 异常，详细原因可以查看我有关 ArrayList 的博客。

3.2 内部类 DescendingIterator

LinkedList 还提供了另一个内部类 DescendingIterator，其作用就是在向前迭代 LinkedList 的过程中让用户可以依然使用

next()

而不用使用

previous()

。

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    // 将 hasPrevious 改为 hasNext
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    // 将 previou 改为 next
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

接下来用一个小例子来验证一下：

public static void main(String[] args) {
    LinkedList<Person> list = new LinkedList<Person>();
    list.add(new Person(35, "张三", "男"));
    list.add(new Person(30, "李四", "男"));
    list.add(new Person(29, "王五", "男"));
    list.add(new Person(29, "刘六", "男"));
    Iterator<Person> iterator = list.descendingIterator();
    while(iterator.hasNext()){
        System.out.println(iterator.next());
    }

}

结果：

JAVA 集合之 LinkedListLinkedList

可以看到虽然是用

next()

但是结果是反向遍历的。

四、总结

LinkedList 的本质是一个双向链表，通过内部类 Node 来实现这种结构
LinkedList 能存储任何值，包括 null
LinkedList 不仅实现了 List 接口还实现了 Deque 接口，因此具有双端队列的所有特征，是双端队列的一种实现，可以用作栈，队列，双端队列来使用
LinkedList 不像 ArrayList 那样有一个最大容量，其理论上可以无限扩展
LinkedList 与 ArrayList 相比在改变 List 结构的操作上性能更高，与之相对的是在查询上性能较差。

JAVA 集合之 LinkedListLinkedList

LinkedList

前言

一、LinkedList 简介

1.1 LinkedList 概述

1.2 LinkedList 底层数据结构

二、LinedList 源码分析

2.1 继承类与接口实现

2.2 成员属性

2.3 构造方法

2.4 核心方法

2.4.1 add() 方法

2.4.2 get() 方法

2.4.3 set() 方法

2.4.4 remove() 方法

2.4.5 indexOf() 方法

三、LinkedList 迭代器

3.1 内部类 ListItr

3.2 内部类 DescendingIterator

四、总结

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method