AlgoDaily - Implement a Linked List - Complexity For Final Solution

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.

xxxxxxxxxx
    'PASSED: Prepending 15, appending 5, prepending 7, appending 19 should equal `7 -> 15 -> 5 -> 19`'
 
var assert = require('assert');
​
class MyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
​
  prepend(value) {
    // prepend a value
  }
​
  append(value) {
    // append a value
  }
​
  toString() {
    // helper method
    const toPrint = [];
    let currNode = this.head;
​
    while (currNode) {
      toPrint.push(currNode.val);
      currNode = currNode.next;
    }
​
    return toPrint.join(' -> ');

OUTPUT

Results will appear here.