概念

LinkedList实现了List接口和Deque接口，也就是说它既可以作为一个顺序容器，也可以作为一个队列，还可以用它来当做栈来使用，兼职就是全能王者。当然，只是说能这样，不考虑性能的话。底层使用双向无环链表实现。

（其实这玩意儿没有什么好讲的，平时用得也很少，学过数据结构都知道，所以下文只会简单的叙述一下）

源码实现

底层数据结构

transient int size = 0;

/**
 * Pointer to first node.
 */
transient Node<E> first;

/**
 * Pointer to last node.
 */
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;
    }
}

链表还能怎么实现，是吧。

如果非要挑什么重点的话，就是不同方法的时间复杂度了，使用的时候，不确定的话可以自己点进源码看一下。但是基本上遵循链表的特性的。

ArrayList 和 LinkedList 的比较

数据结构直接的比较无非就是 CRUD 嘛。

空间复杂度：LinkedList 的节点对象身上多了一些属性，比如说 next 和 next，相比 ArrayList 而言，空间消耗更大一些。

时间复杂度：

​ 新增：两者效率差不多的，但是 ArrayList 涉及到扩容，短时间内进行大量元素新增操作的话，LinkedList 的效率是要高于ArrayList 的。

​ 删除：LinkedList 节点的删除操作时间复杂度是常数级别的，ArrayList 可能会涉及到元素移动，平均效率不如LinkedList 。

​ 查询：理论上两者是一样的，不过由于ArrayList 底层采用数组存储，数组在内存中是连续的内存块，遍历的时候可以很好的利用缓存的局部性原理，提高数据的访问效率。在加上数组可以根据索引取值，而链表只能通过指针去寻址。所以，在查询方面，ArrayList 应该是效率比LinkedList 要高的。

（以上的说辞都是建立在数据量较大的情况下，数据量小的话，这些操作差异不大的）

---

2024.10.28

writeBy kaiven