空间复杂度：链接列表节点数组（头）

给定单个链表的头节点数组，数组的空间复杂度是多少？我会得出结论，假设每个节点只包含一个指向下一个的指针，空间复杂度将是o（n）。但是，当我console.log /打印单个节点时，会显示整个列表。有可能空间复杂度为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]，将空间复杂度的上升或保持恒定？

来源

2017-02-27 Loschtreality

空间复杂度为O(n)。

你从console.log()看到的是它在打印时追逐了几层指针，因为这些数据在调试时往往是非常有用的。但是如果你自己通过键/值，你会发现它有一个固定的大小。

来源

2017-02-27 22:55:35 btilly

空间复杂度：链接列表节点数组（头）

回答

相关问题