Later on, when we remove nodes at the beginning or end, we'll need to account for the switch in this.head
and this.tail
.
Complexity for Final Solution
Since we have a reference to both head and tail nodes, the time complexities for both append and prepend are O(1)
constant time complexity. Without a tail pointer, for append()
we would have to iterate through the entire list in O(n)
time where the list is length n
. Each linked list node takes up a constant amount of space, for O(1)
space complexity.