JavaScript Data Structures: Singly Linked List: Recap

#webdev #tutorial #beginners #javascript

Intro

Last time, we added the last method, remove.

I hope you learned something about the concept of a Singly Linked List and tried your best to implement it on your own. If you want to get notified about new stuff, subscribe :)

Most of the time it deepens my knowledge if I go over it again. And again.

Final Implementation (Short version)

Our Singly Linked List has these methods:

get a specific node
update a specific node
add a node to the end
remove a node from the end
add a node to the beginning
remove a node from the beginning
add a node at a specific index
remove a node at a specific index

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

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

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

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

      return currentNode;
    }
  }

  // update a specific node
  set(index, value) {
    const currentNode = this.get(index);

    if (currentNode) {
      currentNode.value = value;
      return currentNode;
    } else {
      return null;
    }
  }

  // add to the end
  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;
  }

  // remove from the end
  pop() {
    if (!this.length) {
      return null;
    } else {
      let nodeToRemove = this.head;
      let secondToLastNode = this.head;

      while (nodeToRemove.next) {
        secondToLastNode = nodeToRemove;
        nodeToRemove = nodeToRemove.next;
      }

      secondToLastNode.next = null;
      this.tail = secondToLastNode;
      this.length -= 1;

      if (!this.length) {
        this.head = null;
        this.tail = null;
      }

      return nodeToRemove;
    }
  }

  // add to the beginning
  unshift(value) {
    const newNode = new Node(value);

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

    this.head = newNode;
    this.length += 1;

    return newNode;
  }

  // remove from the beginning
  shift() {
    if (!this.length) {
      return null;
    } else {
      const nodeToRemove = this.head;
      this.head = this.head.next;
      this.length -= 1;

      if (!this.length) {
        this.tail = null;
      }

      return nodeToRemove;
    }
  }

  // add at a specific index
  insert(index, value) {
    if (index < 0 || index > this.length) {
      return null;
    } else if (index === 0) {
      return this.unshift(value);
    } else if (index === this.length) {
      return this.push(value);
    } else {
      const preNewNode = this.get(index - 1);
      const newNode = new Node(value);
      newNode.next = preNewNode.next;
      preNewNode.next = newNode;
      this.length += 1;

      return newNode;
    }
  }

  // remove from a specific index
  remove(index) {
    if (index < 0 || index >= this.length) {
      return null;
    } else if (index === 0) {
      return this.shift();
    } else if (index === this.length - 1) {
      return this.pop();
    } else {
      const preNodeToRemove = this.get(index - 1);
      const nodeToRemove = preNodeToRemove.next;
      preNodeToRemove.next = nodeToRemove.next;
      this.length -= 1;

      return nodeToRemove;
    }
  }
}