linked list in js in javascript

In JavaScript, one way to implement a linked list is by using classes.

Here's an example of a simple linked list implementation using a Node class:

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

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

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

  pop() {
    if (!this.head) return null;
    let current = this.head;
    let newTail = current;
    while (current.next) {
      newTail = current;
      current = current.next;
    }
    this.tail = newTail;
    this.tail.next = null;
    this.length--;
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }
    return current;
  }

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let current = this.head;
    let counter = 0;
    while (counter < index) {
      current = current.next;
      counter++;
    }
    return current;
  }

  insert(index, value) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) {
      this.push(value);
      return true;
    }
    if (index === 0) {
      const newNode = new Node(value);
      newNode.next = this.head;
      this.head = newNode;
      this.length++;
      return true;
    }
    const newNode = new Node(value);
    let prev = this.get(index - 1);
    newNode.next = prev.next;
    prev.next = newNode;
    this.length++;
    return true;
  }

  remove(index) {
    if (index < 0 || index >= this.length) return null;
    if (index === this.length - 1) return this.pop();
    if (index === 0) {
      let removed = this.head;
      this.head = removed.next;
      this.length--;
      return removed;
    }
    let prev = this.get(index - 1);
    let removed = prev.next;
    prev.next = removed.next;
    this.length--;
    return removed;
  }
}
1924 chars
93 lines

In the above example, we have created two classes: Node and LinkedList.

The Node class represents a single node in the linked list, with a value and a reference to the next node in the list.

The LinkedList class has the following methods:

  • push: adds a new node to the end of the linked list
  • pop: removes and returns the last node from the linked list
  • get: returns a node at a specified index
  • insert: inserts a new node at a specified index
  • remove: removes and returns a node at a specified index

You can create a new linked list object and start adding nodes to it like this:

index.tsx
const list = new LinkedList();
list.push(10);
list.push(20);
list.push(30);
console.log(list); // LinkedList {head: Node {value: 10, next: Node {value: 20, next: Node {value: 30, next: null}}}, tail: Node {value: 30, next: null}, length: 3}
241 chars
6 lines

Hope that helps!

gistlibby LogSnag