Wanna see something cool? Check out Angular Spotify 🎧

TypeScript data structure: Singly linked list

Linked List

In computer science, a linked list is a linear collection of data elements, in which linear order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality as compared to linked lists.

Linked List

Singly Linked List

I implemented without the tail pointer.

Operation	Description	Big O
pushFront(value)	Adds an item to the front of the list	O(1)
popFront()	Remove front item and return its value	O(1)
front()	Get value of the front item	O(1)
pushBack(value)	Adds an item to the end of the list	O(n)
popBack()	Remove front item and return its value	O(n)
back()	Get value of the end item	O(n)
reverse()	Reverses the list	O(n)
has(value)	Return boolean if the list has a value	O(n)
remove(value)	Removes the first item in the list with this value	O(n)
isEmpty	Returns true if empty	O(1)
size	Returns number of data elements in list	O(1)

This is my notebook when implementing the reverse operation.

Singly Linked List Reverse

Completed Source code

You can find the source code in my TS data structure repo

trungk18/typescript-data-structures/tree/master/data-structures/linked-list

import { Comparator } from '../model/comparator'

export class Node<T> {
  constructor(public val: T, public next?: Node<T>) {}
}

export class LinkedList<T> {
  private _head: Node<T>;
  private _count: number;
  get head() {
    return this._head;
  }

  constructor(private _comparatorFunction = new Comparator<T>()) {
    this._head = null;
    this._count = 0;
  }

  /**
   * Returns true if empty
   */
  get isEmpty(): boolean {
    return this.size === 0;
  }

  /**
   * Returns number of data elements in list
   */
  get size(): number {
    return this._count;
  }

  /**
   * Adds an item to the front of the list
   * Time complexity: O(1)
   */
  pushFront(value: T): LinkedList<T> {
    this._count++;
    let node = new Node(value);
    node.next = this._head;
    this._head = node;
    return this;
  }

  /**
   * Remove front item and return its value
   * Time complexity: O(1)
   */
  popFront(): T {
    if (!this._head) {
      return undefined;
    }
    this._count--;
    let val = this._head.val;
    this._head = this._head.next;
    return val;
  }

  /**
   * Get value of the front item
   * Time complexity: O(1)
   */
  front(): T {
    if (!this._head) {
      return undefined;
    }
    return this._head.val;
  }

  /**
   * Adds an item to the end of the list
   * Time complexity: O(n)
   */
  pushBack(value: T): LinkedList<T> {
    let newNode = new Node(value);
    this._count++;
    if (!this._head) {
      this._head = newNode;
      return this;
    }
    let curr = this._head;
    while (curr.next) {
      curr = curr.next;
    }
    curr.next = newNode;
    return this;
  }

  /**
   * Remove front item and return its value
   * Time complexity: O(n)
   */
  popBack(): T {
    if (!this._head) {
      return undefined;
    }
    if (this.size === 1) {
      let val = this._head.val;
      this._head = null;
      this._count--;
      return val;
    }
    let curr = this._head;
    while (curr.next.next) {
      curr = curr.next;
    }
    let val = curr.next.val;
    curr.next = null;
    this._count--;
    return val;
  }

  /**
   * Get value of the end item
   * Time complexity: O(n)
   */
  back(): T {
    if (!this._head) {
      return undefined;
    }
    let curr = this._head;
    while (curr.next) {
      curr = curr.next;
    }
    return curr.val;
  }

  /**
   * Reverses the list
   * Time complexity: O(n)
   */
  reverse(): LinkedList<T> {
    let curr = this._head;
    let prev = null;
    let next = null;
    while (curr) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    this._head = prev;
    return this;
  }

  /**
   * Return boolean if the list has a value
   * Time complexity: O(n)
   */
  has(value: T): boolean {
    if (!this._head) {
      return undefined;
    }
    let curr = this._head;
    while (curr) {
      let hasValue = this._comparatorFunction.equal(value, curr.val);
      if (hasValue) {
        return true;
      }
      curr = curr.next;
    }
    return false;
  }

  /**
   * Removes the first item in the list with this value
   * Return true if delete success.
   * Time complexity: O(n)
   */
  remove(value: T): boolean {
    if (!this.head) {
      return false;
    }
    if (this._comparatorFunction.equal(this.head.val, value)) {
      this._head = this._head.next;
      this._count--;
      return true;
    }
    let curr = this._head;
    while (curr.next) {
      if (this._comparatorFunction.equal(curr.next.val, value)) {
        curr.next = curr.next?.next;
        this._count--;
        return true;
      }
      curr = curr.next;
    }
    return false;
  }

  print(): string {
    let arr = [];
    let curr = this._head;
    while (curr) {
      arr.push(curr.val);
      curr = curr.next;
    }
    return arr.join(' -> ');
  }

  clear(): void {
    this._head = null;
    this._count = 0;
  }
}