数据结构与算法 - 基础：LinkedList

LinkedList 是一种线性数据结构，不同于数组，它采用链式存储方式，由一系列节点（Node）组成，每个节点包含数据部分（data）和指向下一个节点的指针（next pointer）。根据指针的方向和连接方式，链表可以分为以下几种类型：

1. 单向链表（Singly Linked List）：每个节点只有一个指针指向下一个节点。访问链表中的元素需要从头节点开始，逐个跟随 next 指针前进。

2. 双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向前一个节点（previous pointer），一个指向后一个节点（next pointer）。这使得双向链表可以在两个方向上遍历。

LinkedList 数据结构的特点和操作包括：

• 动态存储：链表可以根据需要动态地增加或减少节点，无需预先设定固定的容量，与数组相比更灵活。

• 插入和删除操作：在链表的任何位置插入或删除一个节点相对容易，只需修改相应节点的指针即可。插入和删除操作的时间复杂度通常为 O(1)（在已知节点的情况下），但是在链表的特定位置（如未知位置或中间位置）插入或删除元素时，需要从头或指定位置开始遍历，时间复杂度为 O(n)。

• 访问操作：访问链表中的元素需从头节点开始，通过遍历的方式逐个查找，访问指定位置的元素时间复杂度为 O(n)。

• 空间开销：每个节点都需要额外的空间存储指针，因此相比于数组，链表在存储相同数量数据时可能占用更多内存。

• 应用场景：LinkedList 在需要频繁插入和删除元素的场景下较为适用，例如实现队列、栈、deque（双端队列）等数据结构，或是在LRU缓存淘汰策略等需要高效插入和删除操作的地方。

在Java中，java.util.LinkedList 类实现了 List 接口，并且可以作为堆栈、队列或双端队列使用。它既是线性表又是Deque（双端队列），也就是说，可以从两端添加或移除元素，而且支持快速的首尾元素访问。同时，LinkedList 类是非同步的，所以在多线程环境下使用时，如果没有外部同步措施，可能会引发线程安全问题。