linkedlist.addfirst()是o(1)头部插入的链表原生操作，因双向链表无需移动元素；而arraylist等动态数组因连续内存限制，头部插入必为o(n)。

LinkedList.addFirst() 本身不是动态数组，而是链表的原生操作——它直接在链表头部插入节点，时间复杂度为 O(1)，无需移动元素。所谓“支持高效头部插入的动态数组链表逻辑”，本质是**用 LinkedList 替代 ArrayList 实现头部频繁插入场景**，而非改造数组。

为什么不能靠“动态数组”实现真正的 O(1) 头部插入

数组（包括 ArrayList）底层是连续内存。在头部插入元素时，必须将原有所有元素向后平移一位，平均时间复杂度为 O(n)。即使扩容策略优化（如倍增），也无法规避数据搬移开销。

而 LinkedList 是双向链表结构，addFirst() 只需新建节点、更新头节点的前后指针，不涉及任何元素位移或批量复制。

如何正确使用 addFirst() 构建头部敏感的数据流逻辑

• 直接初始化 LinkedList： List list = new LinkedList();
• 用 addFirst() 插入新项： list.addFirst("newHead"); —— 立即成为索引 0
• 配合 get(0) 或 removeFirst() 实现栈式行为（LIFO）
• 避免混用基于索引的随机访问（如 get(i)）——链表的 get(i) 是 O(n)，频繁调用会抵消头部插入优势

对比场景：什么情况下该选 LinkedList 而非 ArrayList

• 高频在开头增删（如消息队列前置插播、解析器前缀缓存、逆序构建列表）
• 极少按位置随机读取，或只读首尾（如用 peekFirst()/pollFirst() 做队列）
• 不依赖 ArrayList 特有方法（如 trimToSize、ensureCapacity）
• 能接受稍大的内存开销（每个元素额外存储两个指针）

一个典型实用模式：逆序收集 + 正序处理

比如解析嵌套结构时自底向上构造，每层结果都 addFirst() 到链表，最终自然形成从外到内的顺序：

LinkedList<node> path = new LinkedList();
// 解析过程中逐级向上回溯
path.addFirst(currentNode); // 每次都在最前
// 最终 path.get(0) 就是根节点，path.getLast() 是叶子</node>