JavaScript Data Structures: Singly Linked List: Insert

#beginners #tutorial #javascript #webdev

Intro

Last time, we learned how to update/set a specific node.

Today, we learn how to insert a new node at any specific index.

Current Code

We start with code that has push, unshift and get, because we can reuse these methods.

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

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  unshift(value) {
    const newHead = new Node(value);

    if (!this.length) {
      this.head = newHead;
      this.tail = newHead;
    } else {
      newHead.next = this.head;
      this.head = newHead;
    }

    this.length += 1;

    return newHead;
  }

  get(index) {
    if (index < 0 || index >= this.length) {
      return null;
    } else {
      let count = 0;
      let currentNode = this.head;

      while (count < index) {
        currentNode = currentNode.next;
        count += 1;
      }

      return currentNode;
    }
  }
}

Thoughts

First, we should think about the constraints and possibilities:

If we want to add a node "outside" the List (less than 0 or greater than the length of the current List):

return null

If we want to add a node at the beginning of the List (index is 0):

we can use our unshift method

If we want to add a node at the end of the List:

we can use our push method

All remaining cases:

create a new node
put it between the node before the new node's place and the node, that is currently at this place

Example:

current List: A -> B
desired List: A -> N -> B

Steps:

create new node N
point N's next to B
point A's next to N

Implementation (Short version, DRY)

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

class SinglyLinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
    this.tail = null;
  }

  push(value) {
    const newNode = new Node(value);
    if (!this.length) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.length += 1;
    return newNode;
  }

  unshift(value) {
    const newHead = new Node(value);

    if (!this.length) {
      this.head = newHead;
      this.tail = newHead;
    } else {
      newHead.next = this.head;
      this.head = newHead;
    }

    this.length += 1;

    return newHead;
  }

  get(index) {
    if (index < 0 || index >= this.length) {
      return null;
    } else {
      let count = 0;
      let currentNode = this.head;

      while (count < index) {
        currentNode = currentNode.next;
        count += 1;
      }

      return currentNode;
    }
  }

  insert(index, value) {
    // add a node "outside" the List (=> invalid)
    if (index < 0 || index > this.length) {
      return null;
    } else if (index === 0) {
      // add a node to the beginning of the List
      return this.unshift(value);
    } else if (index === this.length) {
      // add a node to the end of the List
      return this.push(value);
    } else {
      // get the node before the new node's desired place (because it has to point to the new node soon)
      const preDesiredPlace = this.get(index - 1);
      // create a new node
      const newNode = new Node(value);
      // the new node should point to the node, that is currently at the new node's desired place
      newNode.next = preDesiredPlace.next;
      // the node before the new node's desired place should point to the new node
      preDesiredPlace.next = newNode;
      // increase the List's length by 1
      this.length += 1;
      // return the new node
      return newNode;
    }
  }
}

Result

Let's have a look how to use the Singly Linked List's insert method and its results.

const newSLL = new SinglyLinkedList();
console.log(newSLL.insert(0, "A"));
// Node { value: 'A', next: null }

console.log(newSLL.insert(1, "B"));
// Node { value: 'B', next: null }

console.log(newSLL);
// SinglyLinkedList {
//   length: 2,
//   head: Node { value: 'A', next: Node { value: 'B', next: null } },
//   tail: Node { value: 'B', next: null }
// }

console.log(newSLL.insert(1, "N (between A and B)"));
// Node {
//   value: 'N (between A and B)',
//   next: Node { value: 'B', next: null }
// }

console.log(newSLL);
// SinglyLinkedList {
//   length: 3,
//   head: Node {
//     value: 'A',
//     next: Node { value: 'N (between A and B)', next: [Node] }
//   },
//   tail: Node { value: 'B', next: null }
// }