linkedlist的node包含item、next、prev三个字段，构成双向链表；add(e e)为o(1)，get(int index)和add(int index, e e)因需遍历定位均为o(n)。
LinkedList 的 Node 结构长什么样
Java 中 LinkedList 内部不是用数组，而是靠一连串 Node 对象串联起来的。每个 Node 有三个字段：item（存实际元素）、next（指向后一个节点）、prev（指向前一个节点）。它不是单向链表，next 和 prev 都非空（首尾除外），所以能往前、往后双向遍历。
你可以把它想象成一串扣环：每个环都连着前一个和后一个，断掉中间某个环，只要记得前后两个环的位置，就能重新接上——这正是 remove() 或 add(int index, E e) 能在 O(1) 完成（前提是已有目标 Node 引用）的原因。
为什么 get(int index) 是 O(n)，但 add(E e) 是 O(1)
关键看操作是否依赖索引定位。在 LinkedList 中：
-
add(E e)默认加到末尾，直接用last指针，改两处引用（last.next = newNode、newNode.prev = last），O(1) -
get(int index)必须从头（或尾）开始顺着next或prev走过去，最坏走 n/2 步，所以是 O(n) -
add(int index, E e)先要node(index)找到位置，这步就是 O(n)，之后插入本身仍是 O(1)
别被“链表插入快”误导——没现成节点引用时，找位置的成本占主导。
遍历时用 for-each 还是 while + listIterator()？
二者底层都调用 listIterator()，但行为有差异：
- 用
for (E e : list)：安全、简洁，内部用Iterator，只支持正向遍历，且无法在遍历中修改结构（否则抛ConcurrentModificationException） - 用
ListIterator：可双向（hasPrevious()/previous()）、可增删（add()/set()/remove()），但要注意：每次调用next()或previous()后才能调用set()或remove()，否则抛IllegalStateException
listIterator() 返回的是当前状态的快照式迭代器，不反映后续其他线程对链表的修改（fail-fast）。
容易误以为“链表适合随机访问”的坑
有人看到“双向”就以为能像数组一样靠下标快速跳转，其实不能。JDK 的 node(int index) 实现会判断 index 更靠近头还是尾，再决定从 first 还是 last 开始遍历，但仍是线性扫描：
Node<e> node(int index) {
if (index > 1)) {
Node<e> x = first;
for (int i = 0; i x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}</e></e>
这个优化只省了一半时间，复杂度仍是 O(n)。真需要高频随机访问，别硬扛 LinkedList，换 ArrayList 或带索引的结构。
