How To Create A Singly Linked List In JavaScript

Linked Lists are relatively common and simple data structures that allow us to ’link’/chain data together. Linked Lists are useful for insertion/deletion (time complexity of O(1)), but are unfortunately not incredibly efficient when it comes to access and search (time complexity of O(n)).

The core idea behind a linked list is that you have nodes that contain two pieces of information:

The pointer is what chains the pieces of data together and creates the linked list.

There are two main types of Linked Lists, singly linked lists, and doubly linked lists. We will go over the singly linked list below and will tackle the doubly linked list in a later article.

function LinkedList() {
  let Node = function (element) {
    this.element = element;
    this.next = null;
  };
  let head = null;
  let length = 0;
  this.append = function (element) {
    let node = new Node(element);
    let current;
    if (!head) {
      head = node;
    } else {
      current = head;
      while (current.next) {
        current = current.next;
      }
      current.next = node;
    }
    length++;
  };
  this.removeAt = function (position) {
    if (position > -1 && position < length) {
      let current = head,
        previous,
        index = 0;
      if (position === 0) {
        head = current.next;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
      }
      length--;
      return current.element;
    } else {
      return null;
    }
  };
  this.insert = function (position, element) {
    let node = new Node(element);
    if (position >= 0 && position <= length) {
      let current = head,
        previous,
        index = 0;
      if (position === 0) {
        node.next = current;
        head = node;
      } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        previous.next = node;
        node.next = current;
      }
      length++;
      return true;
    } else {
      return false;
    }
  };
  this.toString = function () {
    let current = head;
    let string = '';
    while (current) {
      string += current.element + (current.next ? 'n' : '');
      current = current.next;
    }
    return string;
  };
  this.indexOf = function (element) {
    let current = head;
    let index = 0;
    while (current) {
      if (current.element === element) return index;
      index++;
      current = current.next;
    }
    return -1;
  };
  this.remove = function (element) {
    let index = this.indexOf(element);
    return this.removeAt(index);
  };
  this.size = function () {
    return length;
  };
  this.head = function () {
    return head;
  };
  this.isEmpty = function () {
    return length === 0;
  };
}