算法阅读笔记

Linked List

A linked list stores values in nodes. Each node keeps the value plus a reference to the next node, so the elements do not need to live next to each other in memory.

类型数据结构分类Data Structures深度初级典型复杂度access O(n), head insert O(1)

简短面试回答

先从这个心智模型开始

A linked list stores values in nodes. Each node keeps the value plus a reference to the next node, so the elements do not need to live next to each other in memory.

简单解释

它如何工作，不堆砌不必要的术语

The list starts at a head node. To reach an item, you follow next references one by one.

Insertion at the front is cheap because only a few references change. Random access is expensive because there is no direct index lookup.

执行过程

把算法读成一连串决策

Keep a head reference.

Traverse with current = current.next.

For insertion/deletion, reconnect the surrounding next references carefully.

记住一个小例子

For 10 → 20 → 30, inserting 15 after 10 only changes the links around 10 and 15.

易读的 JavaScript 实现JavaScript

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  head = null;

  prepend(value) {
    this.head = new Node(value, this.head);
  }
}

如何阅读这段代码

不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。

复杂度

access O(n), head insert O(1)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

何时使用

适用场景

Choose it when its dominant operations match your workload.
Compare memory overhead as well as Big-O.

常见错误

通常哪里会出错

Memorizing complexity without understanding representation.
Ignoring worst-case shape or resizing/rebalancing costs.

面试中如何解释

专业回答结构

Contrast it with arrays: linked lists give flexible local insertion/deletion, but lose O(1) index access and usually have worse cache locality.

问题→核心思路→不变量 / 状态→Big-O→权衡

快速面试检查

What problem does Linked List solve?

A linked list stores values in nodes. Each node keeps the value plus a reference to the next node, so the elements do not need to live next to each other in memory.

关于复杂度应该提到什么？

Its typical cost here is access O(n), head insert O(1), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

最常见的错误是什么？

Memorizing complexity without understanding representation.

继续阅读Doubly linked listStackQueue

class Node { constructor(value, next = null) { this.value = value; this.next = next; } } class LinkedList { head = null; prepend(value) { this.head = new Node(value, this.head); } }