LinkedList

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

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

  // Insert node at the beginning of the list
  unshift(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
    if (!this.tail) {
      this.tail = newNode;
    }
    this.size++;
  }

  // Insert node at the end of the list
  push(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }
    this.tail = newNode;
    this.size++;
  }

  // Remove and return the first node in the list
  shift() {
    if (!this.head) {
      return null;
    }
    const removedNode = this.head;
    this.head = this.head.next;
    if (!this.head) {
      this.tail = null;
    }
    this.size--;
    return removedNode.data;
  }

  // Remove and return the last node in the list
  pop() {
    if (!this.head) {
      return null;
    }
    let removedNode;
    if (this.head === this.tail) {
      removedNode = this.head;
      this.head = null;
      this.tail = null;
    } else {
      let current = this.head;
      while (current.next !== this.tail) {
        current = current.next;
      }
      removedNode = this.tail;
      this.tail = current;
      this.tail.next = null;
    }
    this.size--;
    return removedNode.data;
  }

  // Get the node at the given index (0-based)
  get(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current.data;
  }

  // Remove the node at the given index (0-based)
  remove(index) {
    if (index < 0 || index >= this.size) {
      return null;
    }
    let removedNode;
    if (index === 0) {
      removedNode = this.head;
      this.head = this.head.next;
      if (!this.head) {
        this.tail = null;
      }
    } else {
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
        current = current.next;
      }
      removedNode = current.next;
      current.next = current.next.next;
      if (!current.next) {
        this.tail = current;
      }
    }
    this.size--;
    return removedNode.data;
  }

  // Return the current size of the list
  getSize() {
    return this.size;
  }

  // Check if the list is empty
  isEmpty() {
    return this.size === 0;
  }
}

This implementation includes methods for inserting and removing nodes at the beginning and end of the list, as well as getting and removing nodes at specific indices. The implementation also includes methods for getting the size of the list and checking if it's empty.

Examples that use this LinkedList implentation:

• Least Recently Used Algorithm (LRU)
• Implementing Hashes