Space Complexity: Array of Linked List Nodes (Heads)

Question

Given an array of head nodes to individual linked lists, what is the space complexity of the array? I would conclude that the space complexity would be o(n) given that each node only contains a pointer to the next. However, when I console.log / print the individual node, the entire list is displayed. Is it possible that the space complexity would be o(n * m) where m is the length of each linked list in the array? Here is a small example:

// 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)

This is the result of the console.log:

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

Therefore, when placing Node A in an array: [A] , would the space complexity rise or stay constant?

Answer 1

The space complexity is O(n).

What you are seeing from console.log() is that it chases through a few layers of pointers while printing it because that data tends to be really helpful while debugging. But if you walk through keys/values yourself you'll see that it has a fixed size.