One Pager Cheat Sheet

• We can create a Linked List class to help us append and prepend nodes in O(1) time and space complexity.
• The linked list requires a head and tail reference in order to use prepend and append methods.
• We will append a new LinkedListNode to the list by setting the last node's next attribute to the new node, which will always be the next of the tail and the last node in the chain.
• We can prepend new nodes to a Linked List by creating a new node and setting its next to the current head.
• Translating this into code results in a boldly structured sentence.
• We can achieve O(1) time and space complexity for both append() and prepend() by saving a reference to both the head and tail nodes.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

class MyLinkedList {

  constructor() {

    this.head = null;

    this.tail = null;

  }

​

  prepend(newVal) {

    const currentHead = this.head;

    const newNode = new LinkedListNode(newVal);

    newNode.next = currentHead;

    this.head = newNode;

​

    if (!this.tail) {

      this.tail = newNode;

    }

  }

​

  append(newVal) {

    const newNode = new LinkedListNode(newVal);

    if (!this.head) {

      this.head = newNode;

      this.tail = newNode;

    } else {

      this.tail.next = newNode;

      this.tail = newNode;

    }

  }

​

  toString() {

    const toPrint = [];

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.