Space Complexity of Linked List by using pointer

Question

I have declared a class Node for creating new node in linked list like this:

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

Then I tried to iterate through the given head linked list and want to create a new linked list like this:

// head: 1 -> 2 -> 3 -> 4 -> 5 -> x

function doSomething(head){
  let linked_list = new Node(head.data);
  let linked_list_ptr = linked_list;
  let head_ptr = head.next;
  
  while(head_ptr !== null){
    linked_list_ptr.next = new Node(head_ptr.data);
    linked_list_ptr = linked_list_ptr.next;
    head_ptr = head_ptr.next;
  }
  
  return linked_list;
}

My question is that what will be the space complexity of this function or code? Because at first I am creating a single node and then using pointer to create new node and iterate through the linked list. I think the time complexity will be O(n) but what about the space complexity?

Answer 1

I think the time complexity will be O(n) ...

That's right.

...but what about the space complexity?

It is also O(𝑛) because your code constructs 𝑛 times a Node instance with the new operator. The first one is created outside the loop, and the other 𝑛−1 are created inside the loop.

The other variables, like head_ptr, linked_list_ptr, linked_list and head are all object references which require O(1) space, so in total the space complexity is O(𝑛).

Side note: the function assumes the list is not empty. You'd need to cover the case where head is null.