DEV Community

Cover image for Singly Linked List in JavaScript
Anas Nabil
Anas Nabil

Posted on

Singly Linked List in JavaScript

Node Class

class Node {
  constructor(data, next) {
    this.data = data;
    this.next = next;
  }
}
Enter fullscreen mode Exit fullscreen mode

Linked List Initial Setup

class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }
}
Enter fullscreen mode Exit fullscreen mode

Adding a new Node to Start

unshift(data) {
  const newHead = new Node(data, this.head);
  this.length++;
  this.head = newHead;
}

// ✔ Adds new node to start of list by correctly setting head and updating length.
// ✔ Does not overwrite old head.
Enter fullscreen mode Exit fullscreen mode

Getting First Node (Head)

getFirst() {
  return this.head;
}

// ✔ Returns the first node in linked list.
Enter fullscreen mode Exit fullscreen mode

Getting Last Node (Tail)

getLast() {
  let currentNode = this.head;

  while (currentNode && currentNode.next) {
    currentNode = currentNode.next;
  }

  return currentNode;
}

// ✔ Returns the last node in linked list.
// ✔ Does not crash AND returns null on empty list.
Enter fullscreen mode Exit fullscreen mode

Clear Linked List

clear() {
  this.head = null;
  this.length = 0;
}

// ✔ Clears out the linked list and resets length to 0.
Enter fullscreen mode Exit fullscreen mode

Removing and Returning First Node

shift() {
  if (!this.head) {
    return;
  }

  const oldHead = this.head;
  this.head = this.head.next;
  this.length--;

  return oldHead;
}

// ✔ Removes AND returns first node, updates length for linked list w/ one node.
// ✔ Removes the first node and returns it, decreases length of list.
// ✔ Does not crash AND returns null on empty list. Does not decrease length.
Enter fullscreen mode Exit fullscreen mode

Removing and Returning Last Node

pop() {
  if (!this.head) {
    return;
  }

  if (this.length === 1) {
    return this.shift();
  }

  const last = this.getLast();
  let current = this.head;

  while (current.next !== last) {
    current = current.next;
  }

  current.next = null;
  this.length--;

  return last;
}

// ✔ Removes AND returns last node, decreases length.
// ✔ Removes AND returns last node, decreases length on linked-list w/ one node.
// ✔ Returns null on empty list AND does not decrease length.
Enter fullscreen mode Exit fullscreen mode

Adding a new Node to End

push(data) {
  if (!this.head) {
    return this.unshift(data);
  }

  const last = this.getLast();
  last.next = new Node(data, null);
  this.length++;
}

// ✔ Adds to the end of the list and increases length.
// ✔ Adds to end of empty list and increases length without crashing.
Enter fullscreen mode Exit fullscreen mode

Return Node at given Index

get(index) {
  if (index >= this.length || index < 0) {
    return null;
  }

  let counter = 0;
  let current = this.head;

  while (counter < index) {
    current = current.next;
    counter++;
  }

  return current;
}

// ✔ Returns null on negative or out of bounds index.
// ✔ Returns the node at given index.
Enter fullscreen mode Exit fullscreen mode

Update Node at given Index

set(index, data) {
  if (!this.get(index)) {
    return false;
  }

  const node = this.get(index);
  node.data = data;
  return true;
}

// ✔ Returns falsy value on out of bounds or negative index.
// ✔ Updates node and returns true.
Enter fullscreen mode Exit fullscreen mode

Remove Node at given Index

remove(index) {
  if (!this.get(index)) {
    return;
  }

  if (index === 0) {
    return this.shift();
  }

  const nodeToRemove = this.get(index);
  const prevNode = this.get(index - 1);

  prevNode.next = prevNode.next.next;
  this.length--;

  return nodeToRemove;
}

// ✔ Returns falsy value on out of bounds OR negative index.
// ✔ Removes and returns node at given index. Decreases length.
// ✔ Removes node at index 0, decreases length, and returns removed node.
Enter fullscreen mode Exit fullscreen mode

Insert a new Node at given Index

insert(index, data) {
  if (index >= this.length || index < 0) {
    return false;
  }

  if (index === 0) {
    this.unshift(data);
    return true;
  }

  const prevNode = this.get(index - 1);
  const nextNode = this.get(index);

  prevNode.next = new Node(data, nextNode);
  this.length++;

  return true;
}

// ✔ Returns false on index greater than length or negative index.
// ✔ Inserts new node at given index, increases length, and returns true.
// ✔ Inserts node at 0 index correctly, increases length, returns true.
Enter fullscreen mode Exit fullscreen mode

Discussion (0)