Data Structures and Algorithms in JavaScript: Stack, Queue, Linked List, Doubly Linked List

1. Stack

FIRST in, LAST out. Complexity: O(1) constant time. Associated with push and pop methods.

class Stack {
  constructor() {
    this.items = [];
  }

  // Push element to the stack
  push(element) {
    this.items.push(element)
  }

  // Pop element from the stack
  pop() {
    if (this.isEmpty()) {
      return "Underflow"
    }
    return this.items.pop()
  }

  // Peek at the top element without removing it
  peek() {
    return this.items[this.items.length - 1]
  }

  isEmpty() {
    return this.items.length === 0
  }

  size() {
    return this.items.length
  }

  print() {
    console.log(this.items.join(" "))
  }
}

// Example usage
const stack = new Stack()

stack.push(1)
stack.push(2)
stack.push(3)

console.log("Stack after pushing 1, 2, and 3:")
stack.print() // Output: 1 2 3

console.log("Peek at the top element:", stack.peek()) // Output: 3

console.log("Pop element from the stack:", stack.pop()) // Output: 3
console.log("Stack after popping an element:")
stack.print() // Output: 1 2

2. Queue

FIRST in, FIRST out. Complexity: O(1) constant time. Associated with push and shift methods.

class Queue {
  constructor() {
    this.items = []
  }

  // Enqueue element to the queue
  enqueue(element) {
    this.items.push(element)
  }

  // Dequeue element from the queue
  dequeue() {
    if (this.isEmpty()) {
      return "Underflow"
    }
    return this.items.shift()
  }

  // Peek at the front element without removing it
  front() {
    if (this.isEmpty()) {
      return "Queue is empty"
    }
    return this.items[0]
  }

  isEmpty() {
    return this.items.length === 0
  }

  size() {
    return this.items.length
  }

  print() {
    console.log(this.items.join(" "))
  }
}

// Example usage
const queue = new Queue()

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

console.log("Queue after enqueueing 1, 2, and 3:");
queue.print() // Output: 1 2 3

console.log("Front element of the queue:", queue.front()) // Output: 1

console.log("Dequeue element from the queue:", queue.dequeue()) // Output: 1
console.log("Queue after dequeuing an element:")
queue.print() // Output: 2 3

3. Linked List

Insert/Delete: O(1) constant time, Access/Search/insertAt/DeleteAt: O(n) liner. Usage: cache, undo/redo functionality.

// Linked List as a plain object
const LinkedList = {
  head: {
    value: 1,
    next: {
      value: 2,
      next: {
        value: 3,
        next: null // End of the linked list
      }
    }
  }
} 

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

class LinkedList {
  constructor () {
    this.head = null
    this.size = 0
  }
  
  insertFirst (data) {
    this.head = new Node(data, this.head)
    this.size++
  }
  
  insertLast(data) {
    const newNode = new Node(data)
    this.size++
    
    if (!this.head) {
      this.head = newNode
      return
    }

    let current = this.head

    while (current.next) {
      current = current.next
    }

    current.next = newNode
  }
  
  insertAt(position, data) {
    if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    if (position === 0) {
      this.insertFirst(data)
      return
    }
    
    const newNode = new Node(data)
    
    this.size++
    
    let current = this.head
    let prev = null
    let count = 0
    
    while (count < position) {
      prev = current
      current = current.next
      count++
    }
    
    prev.next = newNode
    newNode.next = current
  }
  
  removeAt(position) {
   if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    this.size--
    
    if (position === 0) {
      this.head = this.head.next
      return
    }
    
    let current = this.head
    let prev = null
    let count = 0
    
    while (count < position) {
      prev = current
      current = current.next
      count++
    }
    
    prev.next = current.next
  }
  
  getAt(position) {
    if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    let current = this.head
    let count = 0
    
    while (current && count < position) {
      current = current.next
      count++
    }
    
    return current.data
  }
  
  print() {
    let current = this.head
    
    while (current) {
     console.log(current.data)
     current = current.next
    }
  }
}

// Example usage:
const linkedList = new LinkedList()

linkedList.insertFirst(1)
linkedList.insertLast(2)
linkedList.insertLast(3)
console.log("\nPrint:")
linkedList.print() // 1, 2, 3
linkedList.insertAt(1, 5)
console.log("\nAfter Insert at position 1:")
linkedList.print() // 1, 5, 2, 3
linkedList.removeAt(2)
console.log("\nAfter Remove at position 2:")
linkedList.print() // 1, 5, 3

console.log("Data at position 0:", linkedList.getAt(0))

4. Doubly Linked List

Insert/Delete: O(1) constant time, Access/Search/insertAt/DeleteAt: O(n) liner.

// Doubly Linked List as a plain object
const doublyLinkedList = {
  head: {
    data: 1,
    next: {
      data: 2,
      next: {
        data: 3,
        next: null,
        prev: {POINTER -> 2}
      },
      prev: {POINTER -> 1}
    },
    prev: null
  },
  tail: {
    data: 3,
    next: null,
    prev: {
      data: 2,
      next: {POINTER -> 3},
      prev: {
        data: 1,
        next: {POINTER -> 2},
        prev: null
      }
    }
  }
}

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

class DoublyLinkedList {
  constructor () {
    this.head = null
    this.tail = null
    this.size = 0
  }
  
  insertFirst (data) {
    const newNode = new Node(data, null, this.head)
    
    this.size++
    
    if (this.head) {
      this.head.prev = newNode 
    } else {
      this.tail = newNode
    }
    
    this.head = newNode
  }
  
  insertLast (data) {
    const newNode = new Node(data, this.tail, null)
    
    this.size++
    
    if (this.tail) {
      this.tail.next = newNode
    } else {
      this.head = newNode
    }
    
    this.tail = newNode
  }
  
  insertAt (position, data) {
    if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    if (position === 0) {
      this.insertFirst(data)
      return
    }
    
    this.size++
    
    const newNode = new Node(data)
    
    let current = this.head
    let count = 0
    
    while (current && count < position) {
      current = current.next
      count++
    }
    
    newNode.prev = current.prev
    newNode.next = current
    current.prev.next = newNode
    current.prev = newNode
    
  }
  
  removeAt (position, data) {
    if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    if (!this.head) {
      console.log('The list is empty')
      return
    }
    
    this.size--
    
    if (position === 0) {
      if (this.head === this.tail) {
        this.head = null
        this.tail = null
      } else {
        this.head = this.head.next
        this.head.prev = null
      }
    }
    
    let current = this.head
    let count = 0
    
    while (current && count < position) {
      current = current.next
      count++
    }
    
    if (current === this.tail) {
      this.tail = this.tail.prev
      this.tail.next = null
    } else {
      current.prev.next = current.next
      current.next.prev = current.prev
    }
  }
  
  getAt (position) {
    if (position < 0 || position > this.size) {
      console.log('Invalid position')
      return
    }
    
    let current = this.head
    let count = 0
    
    while (current && count < position) {
      current = current.next
      count++
    }
    
    return current.data
  }
  
  print () {
    let current = this.head
    while (current) {
      console.log(current.data)
      current = current.next
    }
  }
  
  printTail () {
    let current = this.tail
    while (current) {
      console.log(current.data)
      current = current.prev
    }
  }
}

// Example usage:
const doublyLinkedList = new DoublyLinkedList()

doublyLinkedList.insertFirst(1)
doublyLinkedList.insertLast(2)
doublyLinkedList.insertLast(3)

console.log("Forward:")
doublyLinkedList.print() // 1, 2, 3

console.log("\nBackward:")
doublyLinkedList.printTail() // 3, 2, 1

doublyLinkedList.insertAt(1, 10)
console.log("\nAfter Insert at position 1:")
doublyLinkedList.print() // 1, 10, 2, 3

doublyLinkedList.removeAt(2)
console.log("\nAfter Remove at position 2:")
doublyLinkedList.print() // 1, 10, 3

console.log("Data at position 0:", doublyLinkedList.getAt(0))