Space 复杂性：链表节点数组（头）

Question

给定单个链表的头节点数组，数组的 space 复杂度是多少？我会得出结论，space 复杂度将是 o(n)，因为每个节点只包含指向下一个节点的指针。但是，当我 console.log / 打印单个节点时，会显示整个列表。 space 复杂度是否可能为 o(n * m)，其中 m 是数组中每个链表的长度？这是一个小例子：

// JavaScript (ES6)

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

  const A = new Node('a')
  const B = new Node('b')
  const C = new Node('c')
  const D = new Node('d')

  A.next = B
  B.next = C
  C.next = D

  console.log(a)

这是 console.log 的结果：

{
    value: "a",
    next: {
        value: "b",
        next: {
            value: "c",
            next: {
                value: "d",
                next: null
            }
        }
    }
}

因此，当将 Node A 放入数组中时： [A] ，space 复杂度会增加还是保持不变？

Answer 1

space 复杂度为 O(n)。

您从 console.log() 中看到的是，它在打印时追逐几层指针，因为该数据在调试时往往非常有用。但是，如果您自己遍历 keys/values，您会发现它具有固定大小。

Space 复杂性：链表节点数组（头）

Space Complexity: Array of Linked List Nodes (Heads)

javascript

arrays

algorithm

linked-list

space-complexity