Linked Lists

Getting started

Linked lists create an ordered structure of values by storing a current value and pointing to the next. Folks typically start out with these by learning how to reverse them which I solved here. There are two classes involved: a ListNode class and the LinkedList class itself. The node helps as a constructor to define the links between nodes while the list details all of the basic functionality like adding, removing, counting the size, and printing. Additionally, there may be methods that allow for more granular updates like insertion or removal from a specific index.

Functionality

I'll start with the basics of constructing each node, then the entire linked list class.

ListNode

class ListNode<T> {
  value: T
  next: ListNode<T> | null
  constructor(value: T, next?: ListNode<T> | null) {
    this.value = value
    this.next = next === undefined ? null : next
  }
}

With this class, a linked list can already be constructed as shown below. Note that the list is built in this way from the deepest part outward so the array must be iterated over in reverse to make the list retain the array's order. 3 is added first, 1 is added last.

let arr = [1, 2, 3]
let list = null

for (let i = arr.length - 1; i >= 0; i--) {
  list = new ListNode(val, list)
}

console.log(list)
// Output:
// {
//   value: 1,
//   next: {
//     value: 2,
//     next: {
//       value: 3
//       next: null
//     }
//   }
// }

LinkedList

Up next is the list with some common list operations as methods. These include finding values, printing values, returning the list's length, and insert/delete operations. Note that references to new ListNode() are referring to the class presented previously.

Doubly Linked List

When I got to the LRU cache problem, I realized I would need to use a doubly linked list for all of the operations to be O(1) which is required. For each node's access, O(1) is achieved by mapping all nodes which is possible via the constraint that there can only be one key in the cache at any given time. However, the operation that necessitates a doubly linked list is that, if you only had a singly linked list, you would need to traverse the list in worst case O(n) time to find the previous node whenever that node needs to be changed. Previous nodes would be changed when a node is inserted or deleted because the previous node's next pointer must be updated.

Realizing this, I went through the process of learning the ins and outs of doubly linked lists for the first time by creating one for Leetcode's 707. Design Linked List question. It wasn't too difficult, as the only additional things to handel are prev and keeping track of the tail.

class LinkedList<T> {
  head: ListNode<T> | null
  size: number
  constructor() {
    this.head = null
    this.size = 0
  }

  length = (): void => console.log(this.size)

  print = (): void => {
    let listString = ''
    let curr = this.head
    while (curr) {
      listString += curr.value + ' '
      curr = curr.next
    }
    console.log(listString)
  }

  find = (value: T): number => {
    let index = 0
    let curr = this.head
    while (curr) {
      if (curr.value === value) {
        return index
      }
      index++
      curr = curr.next
    }
    return -1
  }

  append = (newValue: T) => {
    let newNode = new ListNode(newValue)
    if (this.head === null) {
      this.head = newNode
    } else {
      let curr: ListNode<T> | null = this.head
      while (curr.next) {
        curr = curr.next
      }
      curr.next = newNode
    }
    this.size++
  }

  insert = (value: T, index: number): void => {
    if (index < 0 || index > this.size) {
      console.error('Index not in range')
    } else {
      let newNode = new ListNode(value)
      if (index === 0) {
        newNode.next = this.head
        this.head = newNode
      } else {
        let prev
        let curr = this.head
        let i = 0
        while (i < index) {
          prev = curr
          curr = curr?.next || null
          i++
        }
        newNode.next = curr
        prev!.next = newNode
      }
      this.size++
    }
  }

  deleteAt = (index: number) => {
    if (index < 0 || index > this.size) {
      console.error('Index not in range')
    } else {
      if (index === 0) {
        this.head = this.head!.next
      } else {
        let prev
        let curr = this.head
        let i = 0
        while (i < index) {
          prev = curr
          curr = curr!.next
          i++
        }
        prev!.next = curr!.next
        this.size--
        return curr!.value
      }
    }
  }

  // Makes the most sense when values are simple like numbers or strings.
  // Comparing objects would be trickier, but a use-case dependent example
  // is if objects represent people in line and it is known ahead of time
  // which key is to be used for the search such as the person's name.
  deleteValue = (value: T): T | -1 => {
    let prev
    let curr = this.head
    while (curr) {
      if (curr.value === value) {
        if (prev === null) {
          this.head = curr.next
        } else {
          prev!.next = curr.next
        }
        this.size--
        return curr.value
      }
      prev = curr
      curr = curr.next
    }
    return -1
  }
}

DoubleListNode

class DoubleListNode<T> {
  val?: number
  next?: DoubleListNode<T> | null
  prev?: DoubleListNode<T> | null
  constructor(val?: number, next?: DoubleListNode<T> | null, prev?: DoubleListNode<T> | null) {
    this.val = val ? val : 0
    this.next = next ? next : null
    this.prev = prev ? prev : null
  }
}

DoublyLinkedList

class DoublyLinkedList<T> {
  head: DoubleListNode<T>
  tail: DoubleListNode<T>
  length: number
  constructor() {
    this.head = new DoubleListNode()
    this.tail = this.head
    this.length = 0
  }

  get(index: number): number {
    if (index >= this.length) return -1

    let curr = this.head.next
    for (let i = 0; i < index; i++) curr = curr.next

    return curr.val
  }

  addAtHead(val: number): void {
    const newNode = new DoubleListNode(val, this.head.next, this.head)
    if (this.head.next) {
      this.head.next.prev = newNode
    } else this.tail = newNode
    this.head.next = newNode
    this.length++
  }

  addAtTail(val: number): void {
    const newNode = new DoubleListNode(val)
    if (!this.head.next) {
      this.head.next = newNode
      newNode.prev = this.head
    } else {
      this.tail.next = newNode
      newNode.prev = this.tail
    }

    this.tail = newNode
    this.length++
  }

  addAtIndex(index: number, val: number): void {
    if (index > this.length) return

    let curr = this.head
    for (let i = 0; i < index; i++) curr = curr.next

    const newNode = new DoubleListNode(val, curr.next, curr)
    if (curr.next) curr.next.prev = newNode
    curr.next = newNode
    if (!newNode.next) this.tail = newNode

    this.length++
  }

  deleteAtIndex(index: number): void {
    if (index >= this.length || !this.length) return

    let curr = this.head
    for (let i = 0; i <= index; i++) curr = curr.next

    curr.prev.next = curr.next
    if (curr.next) curr.next.prev = curr.prev

    if (!curr.next) this.tail = curr.prev

    this.length--
  }
}