Data Structures Implementations in TypeScript

This is a TypeScript project that implements data structures such as linked lists, stacks, queues, hash tables, binary search trees, and heaps.

Singly linked list

A singly linked list stores values in nodes. Each node holds a value and a link to the next node. This allows an item to be added at the front without moving existing items, as an array might need to do.

head → [A | next] → [B | next] → [C | null]

head is the only pointer kept by the list. Each node knows only its next node. Following those links is called traversal. To reach C, traversal must pass through A and B; there is no direct jump to the third node. An empty list has head = null.

Adding a new head only changes two links. The new node points to the old head, and head points to the new node. The singly linked list does exactly that:

public addFirst(data: T): void {
  const node = new Node(data);

  node.setNext(this.head);
  this.head = node;

  this.size++;
}

addFirst and removeFirst change only the head links. Their work does not depend on the number of nodes. But this list has no tail pointer. To add at the end, addLast walks from the head to the last node. Finding or removing a value also needs a search.

Removal needs care. To remove B from A → B → C, the list changes A.next to C. The code therefore searches for the node before the one being removed. If the target is the head, removeFirst moves head to the next node. The list also updates size when a node is added or removed.

The list supports addBefore, addAfter, removeBefore, and removeAfter. Changing links near known neighboring nodes is quick, but these methods receive a value and must first find it. Each node also needs space for its value and next link.

Where it is useful: A singly linked list fits a sequence that is usually read from front to back and often changes at the front. For example, new tasks can be added at the head and processed from that same end. It is less suitable when an item must be reached quickly by position or when the last item changes often.

Time complexity

The list uses O(n) space for n nodes.

Doubly linked list

The slow end operation creates a new question: what if items must also be added and removed at the end? A doubly linked list gives each node two links, next and previous. It also keeps a tail pointer.

head → [A] ⇄ [B] ⇄ [C] ← tail

For every pair of neighboring nodes, the links must agree: if A.next is B, then B.previous should be A. The first node has no previous node, and the last node has no next node. When the list is empty, both head and tail are null.

The doubly linked list can reach the last node without walking from the head:

public addLast(data: T): void {
  if (this.isEmpty()) {
    return this.addFirst(data);
  }

  const node = new Node(data);
  const currentTail = this.tail;

  if (currentTail) currentTail.setNext(node);
  node.setPrevious(currentTail);

  this.tail = node;
  this.size++;
}

The tail pointer gives addLast, getLast, and removeLast direct access to the end. Finding a value still needs a walk through the list, because there is no index for direct access. Each node also uses more memory because it stores a second link.

For example, removing C from A ⇄ B ⇄ C changes tail to B and clears B.next. Inserting between A and B must update links on both sides of the new node. The extra link makes end operations fast, but it also gives each change more pointers to keep consistent.

Shared linked-list behavior

Both linked lists need operations such as find, toArray, getFirst, and getSize. Writing the same logic in both classes would create duplicate code. An abstract class can hold the shared behavior while each concrete list manages its own links.

The base LinkedList class holds head and size. Its find method walks through nodes using getNext():

public find(data: T): T | null {
  if (!this.head) throw new EmptyLinkedList();

  let current = this.head;

  while (current) {
    if (this.compare(current.getData(), data)) return current.getData();
    current = current.getNext() as Node;
  }

  return null;
}

The classes use TypeScript generics so the same code can store different value types. For primitive values, comparison uses ===. Objects must provide an equals method through the HasEqualMethod interface. This gives the shared code one way to compare values. A search still follows nodes one by one.

The shared base does not decide how a node is attached or removed. SinglyLinkedList and DoublyLinkedList inherit common operations, then provide their own methods for changing links. Both also implement the same LinkedListInterface, so their public operations have the same names even though their nodes differ.

Where it is useful: A doubly linked list fits a sequence that needs movement in both directions or frequent changes at both ends. A browser history is one example of forward and backward movement. A double-ended queue is another use when items are added or removed at either end. The extra link is useful only when that behavior matters.

Time complexity

The list uses O(n) space, with two links per node instead of one.

Stack

A linked list can be used for a narrower rule: the last item added must be the first item removed. This is a stack, also called last in, first out or LIFO. A stack fits actions such as undo history or nested function calls.

push(A), push(B), push(C)
pop() → C
pop() → B

Only the top item is available for removal. A stack cannot remove A while B and C remain above it through its normal pop operation. This rule is the point of the structure: callers do not need to decide which position to remove.

The stack keeps a pointer to its top node. push links a new node to the old top; pop moves the top pointer back:

push(data: T): void {
  const node = new Node(data);

  if (this.top) node.setPrevious(this.top);

  this.top = node;
  this.size++;
}

pop(): T {
  if (!this.top) throw new EmptyStack();

  const top = this.top;
  this.top = this.top.getPrevios();
  this.size--;

  return top.getData();
}

push, pop, and peek touch only the top node. Converting the whole stack to an array must visit every node.

peek reads the top without removing it. pop throws EmptyStack when there is no top node, while peek returns null in that case. The stack stores one node for each item.

Where it is useful: A stack fits work that must be undone in reverse order. An editor can push each action and pop the most recent one during undo. It also fits parsing nested brackets: each opening bracket is pushed, and each closing bracket checks the latest opening bracket.

Time complexity

A stack with n nodes uses O(n) space. toArray also creates an O(n) result array.

Simple queue

A stack gives the newest item first. A task line often needs the opposite rule: the first item added should be the first removed. This is a queue, also called first in, first out or FIFO.

enqueue(A), enqueue(B), enqueue(C)
dequeue() → A
dequeue() → B

front points to the next item to remove. back points to the next free position. The active items are in the range from front up to, but not including, back. The number of active items is therefore back - front.

The simple queue uses an array with front and back positions. Adding writes at back. Removing reads at front and moves front forward:

enqueue(data: T): void {
  if (this.back === this.queue.length) {
    const queue = [...this.queue];
    queue.length = this.queue.length * 2;
    this.queue = queue;
  }

  this.queue[this.back++] = data;
}

dequeue(): T {
  if (this.isEmpty()) throw new NoSuchElement();

  const removed = this.queue[this.front];
  this.queue[this.front++] = undefined as unknown as T;

  if (this.isEmpty()) {
    this.front = 0;
    this.back = 0;
  }

  return removed;
}

Most additions and removals change just one array position. When the array is full, an addition copies it into a larger array. Doubling the capacity spreads that occasional copy across later additions; this is called amortized cost.

There is still wasted space. After several removals, empty positions exist at the front, but back keeps moving toward the end. If the queue is not empty, those old positions are not reused. The array can grow even when it has empty slots.

array: [ -, -, C, D, - ]
         0  1  2  3  4
front = 2, back = 4

If E is added, it goes to index 4. Another addition then grows the array, even though indexes 0 and 1 are empty. When the last item is removed, this implementation resets both positions to 0. peek reads the front item and rear reads the last item without moving either pointer.

Where it is useful: A simple queue fits work that must be handled in arrival order, such as a short batch of jobs waiting for one worker. This implementation works best when the queue becomes empty often enough for its positions to reset. A long-lived queue with many additions and removals benefits more from reusing empty positions.

Time complexity

Because capacity doubles, enqueue has amortized O(1) time over many calls. The queue holds an array of c slots, so its allocated space is O(c).

Circular queue

A circular queue treats the array as a ring. When back reaches the end, it returns to position 0. Removed positions at the front can then hold new items.

capacity: 5
front:    3
back:     1

indexes:  0   1   2   3   4
values:  [E,  -,  -,  C,  D]

The live items above are C, D, and E in that order. The next insertion goes at index 1. The position after the last array slot is treated as position 0; no items must be shifted just to wrap around.

The circular queue wraps back when it reaches the last array position:

this.queue[this.back] = data;

if (this.back < this.getCapacity() - 1) this.back++;
else this.back = 0;

When the queue is full, it creates a larger array and copies the live items in queue order. Normal additions and removals only change one position. This implementation leaves one array position unused so front === back can mean that the queue is empty.

The unused position matters. If every position could be filled, front === back could mean either empty or full after wrapping. Here, the queue grows when its size reaches capacity - 1. During growth, it copies the live items starting at the old front, then sets front to 0 and back to the number of copied items. This removes the wrap in the new array.

Where it is useful: A circular queue fits a long-running stream of items, such as events waiting to be handled. Items can be removed from the front while new ones reuse positions at the back. The array can serve many rounds of additions and removals before it needs to grow.

Time complexity

Doubling gives enqueue amortized O(1) time over many calls. The array uses O(c) space for capacity c; one slot stays unused.

Hash table with linear probing

Lists and queues are good at following an order. They are less useful when a value must be found by a key, such as looking up a user by ID. A hash table turns a key into an array position.

key → hash function → array index → value

The array position is also called a bucket or slot. The hash function must always give the same starting slot for the same key while the table size stays the same. It does not need to give a unique slot to every key; collisions are expected and must be handled.

The first hash table uses a simple hash function. A string key uses its length; a number uses its value. The result is reduced to the table size:

private hash(key: K): number {
  if (typeof key === "string") return key.length % this.table.length;

  return +key % this.table.length;
}

Two keys can choose the same slot. This is a collision. For example, cat and dog have the same length, so they get the same starting slot. This table uses linear probing: it checks the next slot, then the next, until it finds an open one.

table size = 5
hash("cat") = 3
hash("dog") = 3

slot 3: cat
slot 4: dog  ← next open slot

To find dog, get starts at slot 3. It sees cat, then checks slot 4. A search cannot stop just because the first slot has a different key. When the end of the array is reached, probing returns to slot 0.

private probe(hashedIndex: number): number {
  return (hashedIndex + 1) % this.table.length;
}

With few collisions, put and get inspect only a few slots. A long run of occupied slots makes them slower. The simple string hash creates many collisions for equal-length keys. Removing a key rebuilds the table: it visits every slot and inserts the remaining entries again.

Removing one entry by simply leaving an empty slot would break some later searches. If cat were removed from slot 3, a lookup for dog might stop at the new gap before reaching slot 4. The implementation avoids that by rehashing the remaining entries into a new array. Resizing also rehashes entries because changing the table length can change every key’s starting slot. This simple design favors clear collision handling over cheap removal.

Where it is useful: A hash table with linear probing fits a key-to-value lookup when reads and writes need to be fast and collisions stay low. It can hold records by ID, for example. This project’s length-based string hash causes many collisions, so its current version is most useful for learning how probing works rather than for a large set of similar-length keys.

Time complexity

Here n is the table length. A resize also rehashes entries. The array uses O(n) space. The costs with few collisions depend on a hash function that spreads keys well; the project’s string hash often does not.

Hash table with separate chaining

Linear probing searches for another array slot. A different solution is to keep a list at each slot. This is separate chaining. Keys with the same hash stay in the same bucket:

bucket 3 → [cat, value A] → [dog, value B]

The bucket is an array position, and its list holds every pair assigned to that position. The hash function only chooses a bucket. The list then checks full keys to find the requested pair. The KeyValuePair class compares pairs by key, which lets the linked list’s find method search a bucket.

The chained hash table reuses the singly linked list:

put(key: K, data: T): void {
  const hash = this.hash(key);
  const elem = new KeyValuePair<K, T>(key, data);

  this.hashtable[hash].addLast(elem);
}

Looking up a key first chooses a bucket, then searches that bucket’s list. With a good hash and short buckets, lookup needs only a few comparisons. If many keys land in one bucket, lookup has to walk a long list. In this implementation, put uses the list’s addLast, so insertion also walks to the end of its bucket. It does not replace an existing key; another pair is added to the bucket.

For example, writing cat twice adds two pairs to the same list. The first matching pair is returned by get, so a later write does not behave like an update. Removing a key searches its bucket and removes a matching pair. This is a behavior of the current code, not a requirement of separate chaining.

The two hash tables solve collisions in different ways. Linear probing uses empty array slots. Separate chaining lets a bucket hold a list. Both depend on how well the hash function spreads keys. In this project, strings of equal length still share a bucket, so long chains are easy to create.

Where it is useful: Separate chaining fits key-to-value lookup when several keys may map to one bucket and those collisions should be stored together. For example, a lookup table can keep customer IDs in buckets and search the short list for one ID. This implementation does not replace a value when the same key is written again, so it is better read as an example of collision handling than as a complete dictionary.

Time complexity

Here b is the number of pairs in the chosen bucket. Short buckets make these operations close to constant time. If all n pairs share one bucket, b = n and the operations take O(n). The table and its lists use O(c + n) space for c buckets and n pairs.

Binary search tree

A hash table helps find one key, but it does not keep keys in sorted order. A binary search tree stores smaller keys to the left of a node and larger keys to the right.

       8
      / \
     3   10
    / \
   1   6

Each node has at most two children. The ordering rule applies to the whole subtree, not only to the two direct children. Every key in the left subtree of 8 must be smaller than 8; every key in the right subtree must be larger. The rule gives each comparison a direction.

To find 6, compare it with 8, go left to 3, then right to 6. The binary search tree uses the same rule when inserting:

private add(node: BinaryTree<KeyValuePair<K, T>>, key: K, data: T): void {
  if (this.isLeftSmaller(key, node.getData().getKey())) {
    const current = node.getLeft();

    current === null
      ? node.setLeft(new BinaryTree(new KeyValuePair(key, data)))
      : this.add(current, key, data);
  } else if (this.isLeftSmaller(node.getData().getKey(), key)) {
    const current = node.getRight();

    current === null
      ? node.setRight(new BinaryTree(new KeyValuePair(key, data)))
      : this.add(current, key, data);
  } else {
    return node.getData().setData(data);
  }
}

If a key already exists, insert replaces its value. min follows left links until no left child remains. max follows right links. These operations follow one path down the tree.

Removal has three main cases. A node with no children can be detached. A node with one child can be replaced by that child. A node with two children needs a replacement key that keeps the order valid. The removal code chooses the smallest node from the right subtree:

const min = this.findMinimum(child.getRight());

this.removeNode(child, min.getData().getKey());
child.setData(min.getData());

An in-order traversal visits the left subtree, then the node, then the right subtree. For the tree above, the key order is:

1, 3, 6, 8, 10

This traversal visits every node. The implementation’s toArray returns values in this key order.

The tree does not rebalance itself. Sorted insertions can make a chain instead of a short, wide tree. Search and insertion then follow a much longer path.

Where it is useful: A binary search tree fits data that must stay in key order. Records keyed by number can be visited from the smallest key to the largest, or checked for the minimum and maximum key. For consistently fast operations on large data, a self-balancing tree would be needed; this implementation can become slow when keys arrive in sorted order.

Time complexity

A balanced tree has h = O(log n). This tree does not rebalance, so sorted insertions can make h = O(n). The nodes use O(n) space; recursive traversal also uses stack space based on the tree height.

Max heap

Sometimes the next item is chosen by priority rather than by arrival time or by exact key. A max heap keeps the largest key at the root. It does not keep every key in full sorted order.

The max heap stores nodes in an array. For an item at index i, its parent is at Math.floor((i - 1) / 2). Its children are at 2 * i + 1 and 2 * i + 2.

array: [9, 7, 8, 2, 4]

       9
      / \
     7   8
    / \
   2   4

The heap has two rules. First, its tree is complete: each level is filled from left to right before the next level begins. Second, every parent key is at least as large as its children’s keys. The second rule puts the largest key at index 0, but it does not sort the rest of the array. For example, 7 and 8 can appear in either child position under 9.

When a new key is added, heapifyUp swaps it with its parent while it is larger:

private heapifyUp(index: number): void {
  while (
    index > 0 &&
    this.heap[this.getParentIndex(index)] != null &&
    this.heap[index].getKey() >
      this.heap[this.getParentIndex(index)].getKey()
  ) {
    let parent = this.getParentIndex(index);
    this.swap(index, parent);
    index = parent;
  }
}

For example, inserting 11 after the array above first places it at the end. It moves above 8, then above 9:

before: [9, 7, 8, 2, 4]
append: [9, 7, 8, 2, 4, 11]
after:  [11, 7, 9, 2, 4, 8]

pull does the reverse kind of repair. It removes the root, moves the last item to index 0, and uses heapifyDown to swap that item with its larger child until the heap rule is restored. A value only moves along one path through the heap. peek reads the largest value at index 0 without moving anything.

Finding a specific key is different from taking the largest one. The heap rule does not say which branch contains that key, so the code scans the array. A max heap is useful when the next highest-priority item matters more than lookup by key.

Where it is useful: A max heap fits a priority queue. A job scheduler can give each job a priority key and repeatedly take the job with the largest key. It is less useful when the main operation is finding any chosen job by its ID, because that still needs a scan.

Time complexity

The array uses O(n) space for n stored items. Growing its capacity can add a copy to an individual insertion.