【集合】LinkedList

LinkedList

【集合】LinkedList

java.util.Deque 接口，提供双端队列的功能，LinkedList 支持快速的在头尾添加元素和读取元素，所以很容易实现该特性。
继承了 java.util.AbstractSequentialList 抽象类，它是 AbstractList 的子类，实现了只能连续访问“数据存储”，基于迭代器顺序遍历后，从而实现后续的操作。例如 #get(int index) 、 #add(int index, E element) 等等随机操作的方法。

数据结构

// 链表大小
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() {
}

public LinkedList(Collection<? extends E> c) {
    this();
    // 添加 c 到链表中
    addAll(c);
}

添加元素

未指定位置（尾插）

public boolean add(E e) {
    // <X> 添加末尾
    linkLast(e);
    return true;
}

void linkLast(E e) {
    // <1> 记录原 last 节点
    final Node<E> l = last;
    // <2> 创建新节点
    // 第一个参数表示，newNode 的前一个节点为 l 。
    // 第二个参数表示，e 为元素。
    // 第三个参数表示，newNode 的后一个节点为 null 。
    final Node<E> newNode = new Node<>(l, e, null);
    // <3> last 指向新节点
    last = newNode;
    // <4.1> 如果原 last 为 null，说明之前是空链表，first 也为空，则 first 也指向新节点
    if (l == null)
        first = newNode;
    // <4.2> 如果原 last 非 null ，说明 first 也非空，则原 last 的 next 指向新节点。
    else
        l.next = newNode;
    // <5> 增加链表大小
    size++;
    // <6> 增加数组修改次数
    modCount++;
}

指定位置

public void add(int index, E element) {
    // 校验不要超过范围
    checkPositionIndex(index);

    // 如果刚好等于链表大小，直接添加到尾部即可
    if (index == size)
        linkLast(element);
    // 添加到第 index 的节点的前面
    else
        linkBefore(element, node(index));
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    // 如果 index 小于 size 的一半，就正序遍历，获得第 index 个节点
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    // 如果 index 大于 size 的一半，就倒序遍历，获得第 index 个节点
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // 获得 succ 的前一个节点
    final Node<E> pred = succ.prev;
    // 创建新的节点 newNode
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 设置 succ 的前一个节点为新节点
    succ.prev = newNode;
    // 如果 pred 为 null ，说明 first 也为空，则 first 也指向新节点
    if (pred == null)
        first = newNode;
    // 如果 pred 非 null ，说明 first 也为空，则 pred 也指向新节点
    else
        pred.next = newNode;
    // 增加链表大小
    size++;
    // 增加数组修改次数
    modCount++;
}

其他方法

public void addFirst(E e)
public void addLast(E e)
public boolean offerFirst(E e)
public boolean offerLast(E e)
public void push(E e)

public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)

链表扩容

LinkedList 不存在扩容的需求，因为通过 Node 的前后指向即可。

删除元素

指定索引

public E remove(int index) {
    checkElementIndex(index);
    // 获得第 index 的 Node 节点，然后进行移除。
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    // <1> 获得 x 的前后节点 prev、next
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // <2> 将 prev 的 next 指向下一个节点
    if (prev == null) { // <2.1> 如果 prev 为空，说明 first 被移除，则直接将 first 指向 next
        first = next;
    } else { // <2.2> 如果 prev 非空
        prev.next = next; // prev 的 next 指向 next
        x.prev = null; // x 的 pre 指向 null
    }

    // <3> 将 next 的 prev 指向上一个节点
    if (next == null) { // <3.1> 如果 next 为空，说明 last 被移除，则直接将 last 指向 prev
        last = prev;
    } else { // <3.2> 如果 next 非空
        next.prev = prev; // next 的 prev 指向 prev
        x.next = null; // x 的 next 指向 null
    }

    // <4> 将 x 的 item 设置为 null ，帮助 GC
    x.item = null;
    // <5> 减少链表大小
    size--;
    // <6> 增加数组的修改次数
    modCount++;
    return element;
}

指定元素

public boolean remove(Object o) {
    if (o == null) { // o 为 null 的情况
        // 顺序遍历，找到 null 的元素后，进行移除
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 顺序遍历，找到等于 o 的元素后，进行移除
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

其他方法

public E remove()
public E removeFirst()
public E removeLast()
public boolean removeFirstOccurrence(Object o)
public boolean removeLastOccurrence(Object o)
public E poll()
public E pollFirst()
public E pollLast()
public E pop()
public boolean removeAll(Collection<?> c)
public boolean retainAll(Collection<?> c)

查找

查找指定元素索引

public int indexOf(Object o) {
    int index = 0;
    if (o == null) { // 如果 o 为 null 的情况
        // 顺序遍历，如果 item 为 null 的节点，进行返回
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index; // 找到
            index++;
        }
    } else { // 如果 o 非 null 的情况
        // 顺序遍历，如果 item 为 o 的节点，进行返回
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index; // 找到
            index++;
        }
    }
    // 未找到
    return -1;
}

查找指定位置的元素

public E get(int index) {
    checkElementIndex(index);
    // 基于 node(int index) 方法实现
    return node(index).item;
}

其他

public boolean contains(Object o)
public int lastIndexOf(Object o)
public E peek()
public E peekFirst()
public E peekLast()
public E element()
public E getFirst()
public E getLast()

清空

public void clear() {
    // 顺序遍历链表，设置每个节点前后指向为 null
    // 通过这样的方式，帮助 GC
    for (Node<E> x = first; x != null; ) {
        // 获得下一个节点
        Node<E> next = x.next;
        // 设置 x 的 item、next、prev 为空。
        x.item = null;
        x.next = null;
        x.prev = null;
        // 设置 x 为下一个节点
        x = next;
    }
    // 清空 first 和 last 指向
    first = last = null;
    // 设置链表大小为 0
    size = 0;
    // 增加数组修改次数
    modCount++;
}

迭代器

public Iterator<E> iterator() {
    return listIterator();
}

private class ListItr implements ListIterator<E> {

    // 最后返回的节点
    private Node<E> lastReturned;
    
    // 下一个节点
    private Node<E> next;
    
    /**
     * 下一个访问元素的位置，从下标 0 开始。
     *
     * 主要用于 {@link #nextIndex()} 中，判断是否遍历结束
     */
    private int nextIndex;
    
    /**
     * 创建迭代器时，数组修改次数。
     *
     * 在迭代过程中，如果数组发生了变化，会抛出 ConcurrentModificationException 异常。
     */
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        // 获得下一个节点
        next = (index == size) ? null : node(index);
        // 下一个节点的位置
        nextIndex = index;
    }

    public boolean hasNext() {
        return nextIndex < size;
    }

    public E next() {
        // 校验是否数组发生了变化
        checkForComodification();
        // 如果已经遍历到结尾，抛出 NoSuchElementException 异常
        if (!hasNext())
            throw new NoSuchElementException();

        // lastReturned 指向，记录最后访问节点
        lastReturned = next;
        // next 指向，下一个节点
        next = next.next;
        // 下一个节点的位置 + 1
        nextIndex++;
        // 返回 lastReturned
        return lastReturned.item;
    }

    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    public E previous() {
        // 校验是否数组发生了变化
        checkForComodification();
        // 如果已经遍历到结尾，抛出 NoSuchElementException 异常
        if (!hasPrevious())
            throw new NoSuchElementException();

        // 修改 lastReturned 和 next 的指向。此时，lastReturned 和 next 是相等的。
        lastReturned = next = (next == null) ? last : next.prev;
        // 下一个节点的位置 - 1
        nextIndex--;
        // 返回 lastReturned
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }

    public void remove() {
        // 校验是否数组发生了变化
        checkForComodification();
        // 如果 lastReturned 为空，抛出 IllegalStateException 异常，因为无法移除了。
        if (lastReturned == null)
            throw new IllegalStateException();

        // 获得 lastReturned 的下一个
        Node<E> lastNext = lastReturned.next;
        // 移除 lastReturned 节点
        unlink(lastReturned);
        // 此处，会分成两种情况
        if (next == lastReturned) // 说明发生过调用 `#previous()` 方法的情况，next 指向下一个节点，而 nextIndex 是无需更改的
            next = lastNext;
        else
            nextIndex--; // nextIndex 减一。

        // 设置 lastReturned 为空
        lastReturned = null;
        // 增加数组修改次数
        expectedModCount++;
    }

    public void set(E e) {
        // 如果 lastReturned 为空，抛出 IllegalStateException 异常，因为无法修改了。
        if (lastReturned == null)
            throw new IllegalStateException();
        // 校验是否数组发生了变化
        checkForComodification();
        // 修改 lastReturned 的 item 为 e
        lastReturned.item = e;
    }

    public void add(E e) {
        // 校验是否数组发生了变化
        checkForComodification();
        // 设置 lastReturned 为空
        lastReturned = null;
        // 此处，会分成两种情况
        if (next == null) // 如果 next 已经遍历到尾，则 e 作为新的尾节点，进行插入。算是性能优化
            linkLast(e);
        else // 插入到 next 的前面
            linkBefore(e, next);
        // nextIndex 加一。
        nextIndex++;
        // 增加数组修改次数
        expectedModCount++;
    }

    public void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        // 遍历剩余链表
        while (modCount == expectedModCount && nextIndex < size) {
            // 执行 action 逻辑
            action.accept(next.item);
            // lastReturned 指向 next
            lastReturned = next;
            //  next 指向下一个节点
            next = next.next;
            // nextIndex 加一。
            nextIndex++;
        }
        // 校验是否数组发生了变化
        checkForComodification();
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

}

序列化

序列化

@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException {
    // 写入非静态属性、非 transient 属性
    s.defaultWriteObject();

    // 写入链表大小
    s.writeInt(size);
    
    // 顺序遍历，逐个序列化
    for (Node<E> x = first; x != null; x = x.next)
        s.writeObject(x.item);
}

反序列化

@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    // 读取非静态属性、非 transient 属性
    s.defaultReadObject();

    // 读取 size
    int size = s.readInt();

    // 顺序遍历，逐个反序列化
    for (int i = 0; i < size; i++)
        linkLast((E)s.readObject()); // 添加到链表尾部
}

小结

LinkedList 基于节点实现的双向链表的 List ，每个节点都指向前一个和后一个节点从而形成链表。
LinkedList 提供队列、双端队列、栈的功能。
- 因为 first 节点，所以提供了队列的功能的实现的功能。
- 因为 last 节点，所以提供了栈的功能的实现的功能。
- 因为同时具有 first + last 节点，所以提供了双端队列的功能。
LinkedList 随机访问平均时间复杂度是 O(n) ，查找指定元素的平均时间复杂度是 O(n) 。
LinkedList 添加元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
- 最好时间复杂度发生在头部、或尾部添加的情况。
LinkedList 移除指定位置的元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
- 最好时间复杂度发生在头部、或尾部移除的情况。
LinkedList 移除指定位置的元素的最好时间复杂度是 O(1) ，最坏时间复杂度是 O(n) ，平均时间复杂度是 O(n) 。
- 最好时间复杂度发生在头部移除的情况。

【集合】LinkedList

LinkedList

数据结构

构造方法

添加元素

链表扩容

删除元素

查找

清空

迭代器

序列化

小结

继续阅读

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

数据结构与算法（27）——排序（二）

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

Linux设备模型（中）之上层容器

scala (3) Function 和 Method