Yazdun - freeCodeCamp.org

How to Work with Queues in TypeScript

Yazdun — Mon, 16 Jun 2025 21:50:21 +0000

A queue is a collection of items arranged in a First-In-First-Out (FIFO) order. This means that the first item added is the first to be removed, much like a supermarket line where customers are served in the order they arrive.

In this hands-on tutorial, you will learn how to implement queues in TypeScript using linked lists.

Here’s what we’ll cover

Prerequisites
Getting started
What are Queues?
What are Linked Lists?
What is a Simple Queue?
What is a Circular Queue?
What is a Double Ended Queue?
What is a Priority Queue?
When to Use Queues (and When to Avoid Them)
Conclusion

Prerequisites

TypeScript: You need to know TypeScript basics, such as interfaces, types, and classes.
Algorithm fundamentals: You need a basic understanding of data structures and algorithms. For example, you should be comfortable analyzing time and space complexity using Big-O notation.
Linked Lists Data Structure: It's important to have a solid understanding of linked lists before starting this tutorial. I wrote a detailed linked list tutorial that you can use to learn about this data structure.

Getting Started

To get started with this tutorial, you’ll use a playground project that’s designed to help you implement queues and follow each step hands-on.

Clone the project from the GitHub repository and code along with the tutorial.

The project structure is as follows:

.
├── index.ts
├── examples
│   ├── 01-linked-list.ts
│   ├── 02-simple-queue.ts
│   ├── 03-circular-queue.ts
│   ├── 04-double-ended-queue.ts
│   └── 05-priority-queue.ts
└── playground
    ├── 01-linked-list.ts
    ├── 02-simple-queue.ts
    ├── 03-circular-queue.ts
    ├── 04-double-ended-queue.ts
    └── 05-priority-queue.ts

Throughout the tutorial, you will use the playground directory to implement and test your code.

The examples directory contains the final version of each implementation. If you get stuck, you can look at these solutions as a last resort!

What Are Queues?

A queue is a data structure that manages items in a first-in, first-out (FIFO) order, where the first item added is the first removed.

For example, imagine a printer handling jobs. If you send three documents to print, the printer processes them in the order they arrive. The first document prints first, then the second, and finally the third.

In programming, queues help manage tasks that need to happen in order, such as:

A web server queues incoming requests to process them one by one.
A chat app queues messages to send them in the order they’re typed.
A navigation app queues locations to explore a map level by level. (Breadth-First Search)

There are four types of queues in a data structure:

Simple Queue: Adds items to the back and removes them from the front in first-in, first-out (FIFO) order.
Circular Queue: It is similar to a simple queue, except the last element is connected to the first.
Double-Ended Queue (Deque): Allows adding or removing items from both front and back, like a bus stop line where people join or leave either end.
Priority Queue: Processes items based on priority, not arrival order. Like a delivery app processes VIP orders before regular ones.

Each of these queues has a set of operations for managing their items. In this tutorial, you will learn about the following common and widely used operations:

enqueue: Adds an item to the back of the queue, like a new customer joining the end of a ticket line.
dequeue: Removes and returns the item at the front of the queue.
getFront: Looks at the item at the front without removing it, like checking who’s first in line.
getRear: Looks at the item at the back without removing it, like seeing who’s last in line.
isEmpty: Checks if the queue has no items.
isFull: Checks if the queue has reached its maximum size.
peek: Same as getFront, views the front item without removing it, like a quick glance at the first task.
size: Returns the number of items in the queue, like counting how many people are in line.

Now that you know about queues and their main operations, let's get into the actual implementation and see how it looks in code.

There are a few different ways to implement queues, but in this tutorial, you will learn about linked list-based queues, which use a linked list to create the queues.

First, let's briefly learn about the linked list data structure and then move on to the queue implementation.

What Are Linked Lists?

A linked list is a method of storing a collection of items where each item, known as a "node," contains two parts: the actual data and a reference (or pointer) to the next item in the list.

Unlike arrays, where all items are stored next to each other in memory, linked lists connect nodes using these references, like a chain.

Linked lists are used to implement queues because they allow efficient insertion at the end and removal from the front, which are the two main operations of a queue.

In a linked list-based queue, you can add a new node at the tail and remove one from the head in constant time (O(1)) without needing to shift elements, as you would in an array.

In this tutorial, you are going to use a specific type of linked list called Circular Doubly Linked List.

A circular doubly linked list is a type of linked list where each node connects to both the next and previous nodes, and the last node loops back to the first one to form a circle.

This means you can move through the list in both directions and never hit a dead end. This makes it easy to go forward or backward through nodes and helps avoid special cases like handling null at the ends.

In a circular doubly linked list, everything is connected in a loop, which simplifies certain queue operations and keeps things efficient.

You can learn more about circular linked lists in my Linked Lists Handbook.

For this tutorial, I’ve already added a circular doubly linked list in src/playground/01-linked-list.ts:

// 📁 src/playground/01-linked-list.ts

/**
 * Node for doubly linked list
 */
export class NodeItem {
  value: T;
  next: NodeItem | null = null;
  prev: NodeItem | null = null;

  constructor(value: T) {
    this.value = value;
  }
}

/**
 * Circular Doubly Linked List
 */
export class LinkedList {
  private head: NodeItem | null = null;
  private tail: NodeItem | null = null;
  private currentSize: number = 0;

  /**
   * Add a new node to the front of the list
   * @param value The value to add
   */
  prepend(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head!.prev = newNode;
      this.tail!.next = newNode;
      this.head = newNode;
    }
    this.currentSize++;
  }

  /**
   * Add a new node to the back of the list
   * @param value The value to add
   */
  append(value: T): void {
    const newNode = new NodeItem(value);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.head!.prev = newNode;
      this.tail = newNode;
    }
    this.currentSize++;
  }

  /**
   * Remove and return the value from the front of the list
   * @returns The value at the head or undefined if empty
   */
  deleteHead(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.head!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = this.head!.next;
      this.head!.prev = this.tail;
      this.tail!.next = this.head;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Remove and return the value from the back of the list
   * @returns The value at the tail or undefined if empty
   */
  deleteTail(): T | undefined {
    if (this.isEmpty()) {
      return undefined;
    }
    const value = this.tail!.value;
    if (this.currentSize === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail!.prev;
      this.tail!.next = this.head;
      this.head!.prev = this.tail;
    }
    this.currentSize--;
    return value;
  }

  /**
   * Get the value at the front without removing it
   * @returns The value at the head or undefined if empty
   */
  getHead(): T | undefined {
    return this.head?.value;
  }

  /**
   * Get the value at the back without removing it
   * @returns The value at the tail or undefined if empty
   */
  getTail(): T | undefined {
    return this.tail?.value;
  }

  /**
   * Check if the list is empty
   * @returns True if the list is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.currentSize === 0;
  }

  /**
   * Get the current size of the list
   * @returns The number of nodes in the list
   */
  size(): number {
    return this.currentSize;
  }
}

In this module, you have a circular doubly linked list with 8 different methods that will make it easier to build queues later in the tutorial:

prepend: Adds a new value to the front of the list.
append: Adds a new value to the end of the list.
deleteHead: Removes and returns the value at the front.
deleteTail: Removes and returns the value at the end.
getHead: Returns the front value without removing it.
getTail: Returns the end value without removing it.
isEmpty: Checks whether the list has no items.
size: Returns the number of items currently in the list.

Now that your linked list is ready, let's begin creating your first queue!

What is a Simple Queue?

A Simple Queue follows the basic FIFO rule: you’ll to add items to the back and remove them from the front.

It’s like a line of customers at a ticket counter, where the first person in line buys a ticket first.

To get started, open src/playground/02-simple-queue.ts, where you will find the placeholder for the Simple Queue with its methods:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue {
  private list: LinkedList;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList();
    this.maxSize = maxSize;
  }

  ...methods
}

At the core of this SimpleQueue class, you're using a circular doubly linked list to store the items, and optionally allowing a maximum size limit to control how big the queue can grow.

private list: LinkedList is where the queue's data is stored. Instead of a simple array, you're using a custom linked list, which makes it efficient to add or remove items from either end. The linked list manages the data structure and allows you to focus on how the queue works.
private maxSize is an optional limit for how many items the queue can hold. If not provided, the queue can grow as large as needed.
Then, the constructor method that runs when you create a new queue. It creates a new, empty linked list to hold the queue items.

Now, let's implement the queue methods.

Open your code editor and update src/playground/02-simple-queue.ts with the following code:

// 📁 src/playground/02-simple-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Simple Queue implemented with a circular doubly linked list
 */
export class SimpleQueue {
  private list: LinkedList;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

As you can see, the linked list greatly simplifies your queue implementation because it acts as the engine behind your queue.

Here's how your Simple Queue works:

isEmpty(): This method checks whether the queue contains any items. It calls the isEmpty() method on the linked list, which internally checks if the current size of the list is zero. If the list has no nodes, it returns true, indicating that the queue is empty. This is a basic utility method often used before attempting to dequeue or inspect the queue.
isFull(): This method determines whether the queue has reached its capacity. It compares the current size of the linked list (via the size() method) to the optional maxSize value. If maxSize is defined and the size is equal to or greater than that limit, it returns true, indicating that no more items can be added. This is useful to prevent overflow in bounded queues.
size(): This method returns the number of items currently stored in the queue. It directly calls the size() method of the linked list, which tracks how many nodes are present. This allows you to monitor queue usage and remaining capacity.
enqueue(): This method adds a new item to the end (rear) of the queue. It first checks whether the queue is full by calling the isFull() method. If it is, the method throws an error. Otherwise, it appends the new item to the internal linked list using the append() method, which adds the new node to the tail of the circular doubly linked list.
dequeue(): This method removes and returns the item at the front of the queue. It calls the deleteHead() method of the linked list, which removes the head node and updates the links of the surrounding nodes to maintain the circular structure. If the queue is empty, it returns undefined.
getFront(): This method returns the value at the front of the queue without removing it. It uses the getHead() method of the linked list to retrieve the value of the head node. This operation does not modify the queue and is useful for previewing the next item to be dequeued.
getRear(): This method returns the value at the rear of the queue without removing it. It uses the getTail() method of the linked list, which returns the value of the tail node. This helps you inspect the most recently added item without altering the queue.
peek(): This method is an alias for getFront(). It returns the item at the front of the queue without removing it. Internally, it calls getFront() to get the head value. This is often used in queue APIs to check the next item in line.

You’ve just implemented your first queue in TypeScript. To make sure that your implementation works correctly, run the following command in your terminal at the root of the project:

npm run test:file 02

If any of the tests fail, use the final example from src/examples/02-simple-queue.ts to debug the issue, and then run the tests again.

If all tests pass, you can proceed to the next section, where you'll implement a Circular Queue.

What is a Circular Queue?

A CircularQueue is a fixed-size queue where the last position connects back to the first. This allows you to reuse space after removing items.

Imagine a buffet line with a limited number of plates: when someone takes a plate from the front, a new one is added at the back, using the same space again.

The CircularQueue is quite similar to the SimpleQueue, but it has a few unique differences.

Let’s modify src/playground/03-circular-queue.ts and add the following code:

// 📁 src/playground/03-circular-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Circular Queue implemented with a circular doubly linked list
 */
export class CircularQueue {
  private list: LinkedList;
  private maxSize: number;

  /**
   * @param maxSize Required maximum size of the circular queue
   */
  constructor(maxSize: number) {
    this.list = new LinkedList();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the rear of the queue
   * @param item The element to add
   */
  enqueue(item: T): void {
    if (this.isFull()) {
      throw new Error("Circular queue is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the queue
   * @returns The element at the front or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

This may look very similar to a SimpleQueue, but there are a few key differences:

Constructor Difference: Unlike the SimpleQueue, the CircularQueue requires a maxSize parameter during instantiation. This enforces a strict upper limit on how many elements can be in the queue at once.

In contrast, SimpleQueue treats maxSize as optional and allows unbounded queues. By making the size mandatory, CircularQueue is better suited for fixed-size buffer scenarios where memory or resource control is important (for example, in real-time systems or caching).
enqueue(): This method is almost identical to the one in SimpleQueue, but the key difference lies in the design intent. In CircularQueue, throwing an error when the queue is full is part of the contract and it assumes that you’re managing a fixed buffer.

The circular nature comes into play conceptually: once full, no more data can enter unless older entries are removed, which mimics a circular overwrite mechanism (though this specific implementation doesn’t auto-overwrite).
isFull(): This method behaves the same as in SimpleQueue when a maxSize is set, but in CircularQueue, it’s always applicable because maxSize is required. The consistent presence of a size limit makes the queue predictable and ideal for bounded use cases like streaming data and rate-limited processing.

Now, let's test the implementation to see if it works:

npm run test:file 03

If any of the tests fail, use the final /examples directory to debug the issue.

If the tests pass, you'll be ready to move on to the next section, where you will learn about double-ended queues.

What is a Double Ended Queue?

A double-ended queue (deque) lets you add or remove items from both the front and the back.

It’s like a line at a bus stop where people can join or leave from either end.

Let’s modify src/playground/04-double-ended-queue.ts and add the following code:

// 📁 src/playground/04-double-ended-queue.ts

import { LinkedList } from "./01-linked-list";

/**
 * Double-Ended Queue (Deque) implemented with a circular doubly linked list
 */
export class Deque {
  private list: LinkedList;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the deque
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the front of the deque
   * @param item The element to add
   */
  enqueueFront(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.prepend(item);
  }

  /**
   * Add an element to the rear of the deque
   * @param item The element to add
   */
  enqueueRear(item: T): void {
    if (this.isFull()) {
      throw new Error("Deque is full");
    }
    this.list.append(item);
  }

  /**
   * Remove and return the element from the front of the deque
   * @returns The element at the front or undefined if empty
   */
  dequeueFront(): T | undefined {
    return this.list.deleteHead();
  }

  /**
   * Remove and return the element from the rear of the deque
   * @returns The element at the rear or undefined if empty
   */
  dequeueRear(): T | undefined {
    return this.list.deleteTail();
  }

  /**
   * Get the element at the front without removing it
   * @returns The element at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead();
  }

  /**
   * Get the element at the rear without removing it
   * @returns The element at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail();
  }

  /**
   * Check if the deque is empty
   * @returns True if the deque is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the deque is full
   * @returns True if the deque is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the front element without removing it
   * @returns The element at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the deque
   * @returns The number of elements in the deque
   */
  size(): number {
    return this.list.size();
  }
}

Now, let's go through the methods:

enqueueFront(): This method allows adding an element to the front of the deque, unlike in SimpleQueue or CircularQueue which only support adding to the rear. Internally, it uses list.prepend(item) to insert the item at the head.

This operation makes the deque suitable for use cases where elements need to be pushed and popped from both ends, like in undo/redo systems or task schedulers.
enqueueRear(): This behaves similarly to SimpleQueue’s enqueue, adding elements to the rear using list.append(item).

The distinction in Deque is that this is just one of two symmetric operations and it gives you full double-ended control.
dequeueFront(): This removes and returns the element from the front of the deque using list.deleteHead().

While similar to the dequeue method in queues, the naming here is explicit to clarify that it's operating on the front and can be paired with a rear counterpart.
dequeueRear(): This is a unique feature to deques, it removes and returns the element at the rear using list.deleteTail(). This complements dequeueFront() and enables LIFO (stack-like) behavior if needed.
Constructor Difference: Like SimpleQueue, the Deque accepts an optional maxSize. This allows for flexible configurations.

You can have unbounded deques when maxSize is not provided, or fixed-size deques when constraints are important. This is in contrast to CircularQueue, which requires a max size.

Once you have completed the implementation, run the following command to test the module:

npm run test:file 04

Now, you're ready to move on to the last section of the tutorial, where you'll learn about the Priority Queue.

What is a Priority Queue?

A priority queue processes items based on their priority, not their order of arrival.

Higher-priority items are removed first, like an emergency room where patients with severe conditions are treated before others.

Let’s modify src/playground/05-priority-queue.ts:

// 📁 src/playground/05-priority-queue.ts

import { LinkedList, NodeItem } from "./01-linked-list";

/**
 * Interface for an element with priority
 */
interface PriorityItem {
  value: T;
  priority: number;
}

/**
 * Priority Queue implemented with a circular doubly linked list
 */
export class PriorityQueue {
  private list: LinkedList>;
  private maxSize?: number;

  /**
   * @param maxSize Optional maximum size of the priority queue
   */
  constructor(maxSize?: number) {
    this.list = new LinkedList>();
    this.maxSize = maxSize;
  }

  /**
   * Add an element to the queue based on its priority
   * Higher priority numbers are dequeued first
   * @param value The value to add
   * @param priority The priority of the value (higher number = higher priority)
   */
  enqueue(value: T, priority: number): void {
    if (this.isFull()) {
      throw new Error("Priority queue is full");
    }

    const newItem: PriorityItem = { value, priority };
    if (this.isEmpty()) {
      this.list.prepend(newItem);
      return;
    }

    let current = this.list["head"];
    let count = 0;
    while (
      current &&
      current.value.priority >= priority &&
      count < this.size()
    ) {
      current = current.next;
      count++;
    }

    if (count === this.size()) {
      this.list.append(newItem);
    } else {
      const newNode = new NodeItem(newItem);
      newNode.next = current;
      newNode.prev = current!.prev;
      if (current!.prev) {
        current!.prev.next = newNode;
      } else {
        this.list["head"] = newNode;
      }
      current!.prev = newNode;
      if (current === this.list["head"]) {
        this.list["head"] = newNode;
      }
      this.list["tail"]!.next = this.list["head"];
      this.list["head"]!.prev = this.list["tail"];
      this.list["currentSize"]++;
    }
  }

  /**
   * Remove and return the element with the highest priority from the queue
   * @returns The value with the highest priority or undefined if empty
   */
  dequeue(): T | undefined {
    return this.list.deleteHead()?.value;
  }

  /**
   * Get the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  getFront(): T | undefined {
    return this.list.getHead()?.value;
  }

  /**
   * Get the element with the lowest priority without removing it
   * @returns The value at the rear or undefined if empty
   */
  getRear(): T | undefined {
    return this.list.getTail()?.value;
  }

  /**
   * Check if the queue is empty
   * @returns True if the queue is empty, false otherwise
   */
  isEmpty(): boolean {
    return this.list.isEmpty();
  }

  /**
   * Check if the queue is full
   * @returns True if the queue is full, false otherwise
   */
  isFull(): boolean {
    return this.maxSize !== undefined && this.list.size() >= this.maxSize;
  }

  /**
   * Peek at the element with the highest priority without removing it
   * @returns The value at the front or undefined if empty
   */
  peek(): T | undefined {
    return this.getFront();
  }

  /**
   * Get the current size of the queue
   * @returns The number of elements in the queue
   */
  size(): number {
    return this.list.size();
  }
}

Let's understand how the methods work within a Priority Queue:

enqueue(): This method inserts a new element into the queue based on its priority. Unlike other queue types where order is based on insertion time, PriorityQueue uses a sorting mechanism where elements with higher priority values are placed closer to the front.

The method traverses the linked list from the head, searching for the correct position where the new item should be inserted so that the list remains sorted in descending priority order.

It manually adjusts the prev and next pointers to keep the circular doubly linked list intact. This sorting during insertion ensures quick access to the highest priority element later.
dequeue(): This method removes and returns the element with the highest priority, which is always positioned at the front of the list.

Internally, it calls deleteHead() and then returns the value from the PriorityItem node. Because items are sorted during insertion, this operation is always efficient and retrieves the correct item.
getFront(): This retrieves the value at the front of the queue without removing it. Since the list is sorted in descending priority, this value always represents the highest priority item.
getRear(): This returns the value at the rear of the queue, which is the item with the lowest priority. It accesses the last element in the list using getTail() and extracts the value.
isEmpty(): This checks whether the queue contains any elements by delegating to the linked list’s isEmpty() method.
isFull(): This checks whether the queue has reached its maximum allowed size. It compares the current size with maxSize if it's defined.
peek(): This is functionally equivalent to getFront(). It provides a clearer semantic name when users want to examine the highest-priority element without removing it.
size(): This returns the total number of items currently in the priority queue. It's useful for monitoring capacity or debugging.
Key Differences: The priority queue differs from other queue types by enforcing order during insertion based on a numeric priority.

This enables constant-time access to the highest priority element but introduces linear-time insertion complexity due to the need to find the correct place for each new element.

It supports advanced scheduling and load balancing use cases where task urgency or importance matters more than arrival time.

Once you’re done with the implementation, run the following command to test your code:

npm run test:file 05

That’s it, congratulations!

You have successfully completed the tutorial and learned about queues and their different variations. Great job!

Before reaching conclusions, let’s briefly learn about where to use queues and where to avoid them. We’ll also discuss the bottlenecks and issues that queues may create if not used correctly and in the right place.

When to Use Queues (and When to Avoid Them)

Queues are ideal in scenarios where tasks or data must be processed in the exact order they arrive, such as in job scheduling and event handling systems.

For example, when multiple print jobs are sent to a printer, a queue can make sure each document is printed in the order it was submitted.

Similarly, queues are used in operating systems for managing tasks in thread pools or CPU scheduling (for example, Round Robin), where order is crucial.

Queues are also heavily used in asynchronous communication systems such as message brokers like RabbitMQ and Kafka.

In these systems, producers and consumers operate independently: a producer pushes messages into the queue, and a consumer processes them later.

This pattern is extremely useful in microservices architecture or serverless environments, where different parts of a system need to remain loosely coupled and highly scalable.

Similarly, in real-time systems like video streaming or sensor data ingestion, queues help buffer incoming data to avoid data loss and allow for smooth downstream processing.

When to Avoid Queues

Queues are not well-suited for problems that require random access to elements, complex search operations, or sorting.

Since queues typically allow insertion at one end and removal from the other, they’re inefficient for use cases where you frequently need to access elements in the middle or search through all items.

An array, tree, or hash map would serve better in such cases.

Using queues inappropriately can introduce unnecessary complexity and hidden bottlenecks.

For instance, blindly placing a queue between every microservice might decouple components but also make debugging and failure handling more difficult.

Over-queuing can also lead to backpressure problems where queues grow uncontrollably under high load which will increase latency or even crashing the system if not managed properly.

So you should use queues deliberately: when order, buffering, or async processing is required.

Conclusion

Queues are a basic data structure that work well when you need order and async processing.

Queues are useful for handling tasks, streaming data, or coordinating services, and making sure things run smoothly and efficiently.

But they aren't suitable for every problem. It's important to understand their pros and cons to use them correctly and avoid unnecessary complexity.

Thanks for following along with this tutorial. You can follow me on X, where I share more useful tips on data structures and web development.

Happy coding!

How to Code Linked Lists with TypeScript: A Handbook for Developers

Yazdun — Mon, 02 Jun 2025 18:16:03 +0000

A linked list is a data structure where each item, called a node, contains data and a pointer to the next node.

Unlike arrays, which store elements in contiguous memory, linked lists connect nodes that can be scattered across memory.

In this hands-on tutorial, you’ll build linked lists from scratch in TypeScript, starting with a basic singly linked list and progressing to advanced variations like doubly linked lists and circular lists.

Here’s What We’ll Cover

Prerequisites
Getting Started
What are Linked Lists?
What is a Singly Linked List?
What is a Doubly Linked List?
What is a Circular Linked List?
What is a Circular Singly Linked List?
What is a Circular Doubly Linked List?
When to Use Linked Lists (and When to Avoid Them)
Conclusion

Prerequisites

TypeScript: You need to know TypeScript basics, such as interfaces, types, and classes.
Algorithm fundamentals: You need a basic understanding of data structures and algorithms. For example, you should be comfortable analyzing time and space complexity using Big-O notation.

Getting Started

To get started with this tutorial, you’ll use a playground project designed to help you implement linked lists and follow each step hands-on.

Clone the project from the GitHub repository and code along with the tutorial.

The project structure is as follows:

fcc-linked-list/
├── src/
│   ├── examples/
│   │   ├── circular-1.ts
│   │   ├── circular-2.ts
│   │   ├── doubly.ts
│   │   └── singly.ts
│   └── playground/
│       ├── circular-1.ts
│       ├── circular-2.ts
│       ├── doubly.ts
│       └── singly.ts

The examples directory contains the final version of each implementation. If you get stuck, you can look at these solutions as a last resort!

What are Linked Lists?

A linked list is a collection of elements called nodes, where each node contains data and a pointer to the next node, with the last node’s pointer typically pointing to null to mark the end of the list.

Some linked lists have extra pointers to speed up changes anywhere in the list. But finding a node can be slow because you have to follow each pointer one by one and can't jump directly to a node.

Linked lists are the foundation for data structures like queues and stacks. The linked lists you create in this tutorial will support many other data structures.

While linked lists can perform many operations, this tutorial will focus on the following:

prepend: adds a node to the beginning of the list.
append: adds a node to the end of the list.
delete: removes a specific node from the list.
deleteTail: removes the last node in the list.
deleteHead: removes the first node in the list.
insertAt: inserts a node at a specific position.
find: searches for and returns a node in the list.
traverse: visits each node in the list, usually from head to tail, for reading or processing data.

Once you understand these basic operations, you'll be able to implement any operation on your linked lists.

Now that you understand the concept, let's move to the next section and create your first linked list.

What is a Singly Linked List?

In this first section, you'll create the simplest type of linked list, called a Singly Linked List.

It's called "Singly Linked" because each node points to only one other node, which is the next one in the list.

How to Create a Generic Node Structure for a Singly Linked List

To start building a singly linked list, you need a Node structure that holds two main parts:

data: Stores the node’s value.
Next pointer: Links to the next node in the list or null if there’s no next node.

Open src/playground/singly.ts, where you'll find a class named N. Change it to the following code to set up the node structure:

// 📁 src/playground/singly.ts

class N {
  /** Node value */
  public data: T;
  /** Next node reference */
  public next: N | null = null;

  /** Creates a node with given value */
  constructor(value: T) {
    this.data = value;
  }
}

Here’s how the node structure works:

Builds a generic Node: Uses to handle any data type.
Stores the node’s value: Assigns the value to the data property.
Link to the next node: Sets the next pointer to the next node or null if there isn't one.
Initializes the node: Takes a value in the constructor and assigns it to data.

Now, you can use the N class to create nodes in your singly linked list.

How to Implement a Singly Linked List

Let's use the Node class you just created to build your singly linked list.

Open src/playground/singly.ts where you'll find the SinglyLinkedList class with a head pointer and several methods:

// 📁 src/playground/singly.ts

class N {
  /** Node value */
  public data: T;
  /** Next node reference */
  public next: N | null = null;

  /** Creates a node with given value */
  constructor(value: T) {
    this.data = value;
  }
}

/** Singly linked list implementation */
export class SinglyLinkedList {
  /** Head node */
  public head: N | null = null;

  /** Adds node to list start */
  prepend(val: T): void {}

  /** Adds node to list end */
  append(data: T): void {}

  /** Removes head node */
  deleteHead(): void {}

  /** Removes tail node */
  deleteTail(): void {}

  /** Removes first node with given value */
  delete(data: T): void {}

  /** Finds node with given value */
  find(data: T): N | null {
    return null;
  }

  /** Logs all node values */
  traverse(): void {}

  /** Inserts node at given position */
  insertAt(pos: number, data: T): void {}
}

By the end of this section, you'll create each of these methods. But first, let's discuss the head pointer.

What is the `head` Pointer in a Linked List?

The head is the first node in the list, and you begin from head when going through the list.

You follow each node's next pointer until you get to the last node, where next is null.

If head is null, the list is empty.

A non-empty singly linked list needs a head to be valid, or it’s broken.

With this knowledge, you're ready to start working on the operations.

How to Prepend a Node in a Singly Linked List

The goal is to add a new node to the beginning of your singly linked list and update the head pointer to this new node.

Modify the prepend method in your SinglyLinkedList class in src/playground/singly.ts:

// 📁 src/playground/singly.ts

prepend(data: T): void {
  const newNode = new N(data);
  newNode.next = this.head;
  this.head = newNode;
}

The data prop holds the value for the new node. Here’s how prepend works:

Creates a new node with the given data.
Points the new node’s next to the current head.
Sets the head to the new node.

Now, the head points to the new node, and the previous head is the second node in the list.

This runs in O(1) time because you only change a few pointers without looping.

How to Append a Node in a Singly Linked List

The goal is to add a new node to the end of your singly linked list.

Change the append method in your SinglyLinkedList class:

// src/playground/singly.ts

append(data: T): void {
  const newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    return;
  }

  let current = this.head;

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

  current.next = newNode;
}

To add a new node to the end of the list, you first need to find the last node. In a non-empty singly linked list, the last node's next pointer always points to null.

In other words, to find the last node in a non-empty singly linked list, look for the node whose next pointer is null.

To append a new node, you should follow these steps:

Create a new node with the given value.
Check if the head is null. If it is, the list is empty, so set the head to the new node.
If the list has nodes, find the last node by looping through the list.
Start with a new pointer called current at the head.
Keep moving current to the next node until you hit a node with no next node (where next is null).
Link the last node’s next to the new node.

Now, the new node is the last node, and its next points to null.

This runs in O(n) time because you may need to traverse the entire list to find the last node.

How to Delete the `head` of a Singly Linked List

The goal is to delete the head of the list. Go ahead and update the deleteHead method in your SinglyLinkedList class:

// 📁 src/playground/singly.ts

deleteHead(): void {
  if (this.head) {
    this.head = this.head.next;
  }
}

You just need to move the head pointer to the second node in the list. The second node is head.next, so all you have to do is set head to head.next.

And just like that, the old head is deleted!

How to Delete the Last Node of a Singly Linked List

The goal is to delete the last node, called the tail, from your singly linked list.

The tail is the node whose next pointer is null.

Modify the deleteTail method in your SinglyLinkedList class:

// 📁 src/playground/singly.ts

deleteTail(): void {
  if (!this.head) return;

  if (!this.head.next) {
    this.head = null;
    return;
  }

  let current = this.head;

  while (current.next && current.next.next) {
    current = current.next;
  }
  current.next = null;
}

Here’s how deleteTail works:

If the list is empty, it stops the operation because there is no tail to remove.
If the head's next is null, the list has only one node, which serves as both the head and the tail. To empty the list, simply set the head to null.
If the list has more than one node, it finds the node right before the tail. It starts with a pointer called current at the head.
It moves current forward until its next node is the tail. Then, it sets the next pointer of this node to null to make it the tail.
Now, the last node is removed, and the new tail’s next points to null.

This runs in O(n) time because you may need to traverse the entire list to find the node before the tail.

How to Delete a Node from a Singly Linked List

The goal is to remove the first occurrence of a node with a given value from your singly linked list.

Let's start by changing the delete method in your SinglyLinkedList class:

// 📁 src/playground/singly.ts

delete(data: T): void {
  if (!this.head) return;

  if (this.head.data === data) {
    this.head = this.head.next;
    return;
  }

  let current = this.head;

  while (current.next) {
    if (current.next.data === data) {
      current.next = current.next.next;
      return;
    }
    current = current.next;
  }
}

Here’s how delete works:

The data prop is the value to find and remove
If the list is empty, it stops the operation because there is nothing to delete.
It checks if the head node’s value matches data prop. If it does, you don’t need to search further because the head is the node to delete, so it moves the head to head.next to remove the old head.
If the head doesn't match, it creates a new pointer called current starting at the head.
It moves current through the list as long as there is a next node, and checks if the next node's value matches the data prop.
If a match is found, it removes the next node by connecting current’s next to the node after it.
This takes the matched node out of the list because current now points to the node after the one you want to remove.
If no match is found, it keeps moving current to the next node until the end.

This runs in O(n) time because you may need to traverse the entire list to find the node.

How to Find a Node in a Singly Linked List

The goal is to find the first occurrence of a node with the given value.

Modify the find method inside the SinglyLinkedList class:

// 📁 src/playground/singly.ts

find(data: T): N | null {
  if (!this.head) return null;

  let current: N | null = this.head;

  while (current) {
    if (current.data === data) return current;
    current = current.next;
  }

  return null;
}

The data prop is the value you're searching for.

Here's how find works:

If the head is null, it returns null because the list is empty and there are no nodes to find.
It creates a new pointer called current at the head.
It moves current through the list while it exists and checks if its value matches data.
If a match is found, it returns the current node because it holds the value you’re looking for.
If no match is found, it moves current to the next node and keeps checking until the end.
If you reach the end without a match, it returns null.

This runs in O(n) time because you may need to traverse the entire list to find the node.

How to Insert a Node at a Specific Position in a Singly Linked List

The goal is to add a new node at a specific position in your singly linked list.

Modify the insertAt method in your SinglyLinkedList class:

// 📁 src/playground/singly.ts

insertAt(pos: number, data: T): void {
  const newNode = new N(data);
  let current: N | null = this.head;

  if (pos < 0) throw new Error("failed");

  if (pos === 0) {
    newNode.next = this.head;
    this.head = newNode;
    return;
  }

  let idx = 0;

  while (current && idx < pos - 1) {
    current = current.next;
    idx++;
  }

  if (!current) throw new Error("failed");

  newNode.next = current.next;
  current.next = newNode;
}

The pos prop is the position in the list, and data is the value.

Here’s how insertAt works:

It creates a new node with the given value.
If the pos is negative, it stops the operation with an error because it's not valid.
If pos is 0, it inserts the node at the head. It links the new node's next to the current head, makes the new node the head, and stops the operation.
If the position is not 0, then it creates a pointer called current at the head and a counter called idx at 0.
It moves current through the list until you reach the node just before the desired position, increasing idx as you go.
If you reach the end of the list or the position is too large, it stops with an error.
It links the new node's next to the node that is currently after the current node.
It links current’s next to the new node to insert it in the list.

This runs in O(n) time because you may need to traverse the list to find the insertion point.

How to Traverse a Singly Linked List

The goal is to log the values of all nodes in your singly linked list.

Modify the traverse method inside the SinglyLinkedList class:

// 📁 src/playground/singly.ts

traverse(): void {
  let current = this.head;
  while (current) {
    console.log(current.data);
    current = current.next;
  }
}

Here's how traverse works:

It starts by setting the current pointer to head to begin at the start of the list. If head is null, the list is empty.
If there are nodes in the list, it uses a while (current) loop to visit each one. In each loop, it logs current.data to display the node's value, then moves the current pointer to current.next to go to the next node.
This loop continues until current becomes null, meaning you've reached the end of the list.

Overall, the time complexity is O(n) due to traversing the whole list.

How to Test Your Singly Linked List

Congratulations! You've successfully created your singly linked list.

Here's what the final code should look like:

// 📁 src/playground/singly.ts

/** Node for singly linked list */
class N {
  /** Node value */
  public data: T;
  /** Next node reference */
  public next: N | null = null;

  /** Creates a node with given value */
  constructor(value: T) {
    this.data = value;
  }
}

/** Singly linked list implementation */
export class SinglyLinkedList {
  /** Head node */
  public head: N | null = null;

  /** Adds node to list start */
  prepend(data: T): void {
    const newNode = new N(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  /** Adds node to list end */
  append(data: T): void {
    const newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      return;
    }

    let current = this.head;

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

    current.next = newNode;
  }

  /** Removes head node */
  deleteHead(): void {
    if (this.head) {
      this.head = this.head.next;
    }
  }

  /** Removes tail node */
  deleteTail(): void {
    if (!this.head) return;

    if (!this.head.next) {
      this.head = null;
      return;
    }

    let current = this.head;
    while (current.next && current.next.next) {
      current = current.next;
    }

    current.next = null;
  }

  /** Removes first node with given value */
  delete(data: T): void {
    if (!this.head) return;

    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;

    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }

      current = current.next;
    }
  }

  /** Finds node with given value */
  find(data: T): N | null {
    if (!this.head) return null;

    let current: N | null = this.head;

    while (current) {
      if (current.data === data) return current;
      current = current.next;
    }

    return null;
  }

  /** Logs all node values */
  traverse(): void {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  /** Inserts node at given position */
  insertAt(pos: number, data: T): void {
    const newNode = new N(data);
    let current: N | null = this.head;

    if (pos < 0) throw new Error("failed");

    if (pos === 0) {
      newNode.next = this.head;
      this.head = newNode;
      return;
    }

    let idx = 0;

    while (current && idx < pos - 1) {
      current = current.next;
      idx++;
    }

    if (!current) throw new Error("failed");

    newNode.next = current.next;
    current.next = newNode;
  }
}

After you finish the implementation, run the following command to test your singly linked list:

npm run test:file singly

If any tests fail, you can use src/examples/singly.ts to find and fix the issue, and then run the tests again.

That's it! You've successfully built a linked list and learned how to create nodes that point to the next node and perform operations on them.

While singly linked lists are useful, they have a big limitation: each node only points to the next node.

Wouldn't it be great if nodes could also point to the previous node? This would let us do many more operations with our linked list.

That's exactly what you will learn in the next section.

What is a Doubly Linked List?

In this section, you’ll create a Doubly Linked List. It’s called "Doubly Linked" because each node points to both the next and previous nodes in the list.

First, let’s look at the node structure in a doubly linked list, and then you’ll implement the operations in the actual linked list.

How to Create a Generic Node Structure for a Doubly Linked List

The node structure in doubly linked lists is similar to singly linked lists, except it has an additional pointer to point to the previous node.

The Node structure in a doubly linked list consists of three parts:

data: Stores the node’s value.
Next pointer: Links to the next node in the list or null if there’s no next node.
Previous pointer: Links to the previous node in the list or null if there’s no previous node.

Open src/playground/doubly.ts and modify the N class with the following code to set up the node structure:

// 📁 src/playground/doubly.ts

export class N {
  data: T;
  next: N | null;
  prev: N | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

Here’s how the node structure works:

It builds a generic Node: Uses to handle any data type, such as numbers or strings.
It stores the node’s value: Assigns the value to the data property.
It links to the next node: Sets the next pointer to the next node or null if there isn’t one.
It links to the previous node: Sets the prev pointer to the previous node or null if there isn’t one.

Then, the constructor sets the data when you create a new node.

How to Implement a Doubly Linked List

Now that the Node class is ready, you can start building the actual list.

Open src/playground/doubly.ts and take a look at the DoublyLinkedList class:

// 📁 src/playground/doubly.ts

export class N {
  data: T;
  next: N | null;
  prev: N | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

export class DoublyLinkedList {
  /** Head node */
  public head: N | null;
  /** Tail node */
  public tail: N | null;
  /** List length */
  public len: number;

  /** Creates an empty list */
  constructor() {
    this.head = null;
    this.tail = null;
    this.len = 0;
  }

  /** Adds node to list start */
  prepend(data: T): void {}

  /** Adds node to list end */
  append(data: T): void {}

  /** Removes and returns head node data */
  deleteHead(): T | null {
    return null;
  }

  /** Removes and returns tail node data */
  deleteTail(): T | null {
    return null;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    return false;
  }

  /** Finds node at given index */
  find(idx: number): N | null {
    return null;
  }

  /** Returns array of node data */
  traverse(dir: "forward" | "backward" = "forward"): T[] {
    return [];
  }

  /** Inserts node at given index */
  insertAt(idx: number, data: T): boolean {
    return false;
  }
}

This class has two pointers, head and tail, and a variable called len:

head: This always points to the first item in your list.
tail: This always points to the last item in your list.
len: This represents the length of your linked list. Each time you modify the list by adding or removing a node, you need to update len to reflect the correct length.

A valid doubly linked list will always have a head and a tail. If either the head or tail is null, it means the list is empty and has no nodes.

That's why you initially set the head and tail to null. When you create a list, it's empty at first. As you add a node to the list, you update the pointers to point to the new node.

Now, let's move on to the next section and see how you can add a node to your doubly linked list.

How to Prepend a Node in a Doubly Linked List

The goal is to add a new node to the beginning of your doubly linked list and update the head pointer to this new node.

Modify the prepend method in your DoublyLinkedList class located in src/playground/doubly.ts:

// 📁 src/playground/doubly.ts

prepend(data: T): void {
  let newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    let prevHead = this.head;
    newNode.next = prevHead;
    prevHead.prev = newNode;
    this.head = newNode;
  }

  this.len++;
}

The data prop holds the value for the new node. Here’s how prepend works:

It creates a new node with the given data.
If the list is empty (head is null), it sets both the head and tail to the new node.
If the list has nodes, it points the new node’s next to the current head.
It points the current head’s prev to the new node.
It sets the head to the new node.
It increases the list’s length by one.

This runs in O(1) time because you only change a few pointers without looping.

How to Append a Node in a Doubly Linked List

The goal is to add a new node to the end of your doubly linked list and update the tail pointer to this new node.

Modify the append method in your DoublyLinkedList:

// 📁 src/playground/doubly.ts

append(data: T): void {
  let newNode = new N(data);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail!.next = newNode;
    newNode.prev = this.tail;
    this.tail = newNode;
  }

  this.len++;
}

Here’s how append works:

The data prop holds the value for the new node.
It makes a new node with the given data.
It checks if the list is empty ( head is null ), and sets both the head and tail to the new node.
If the list has nodes, it points the current tail’s next to the new node.
It points the new node’s prev to the current tail.
It sets the tail to the new node.
It increases the list’s length by one.

This runs in O(1) time because you only change a few pointers without looping.

How to Delete the Head of a Doubly Linked List

The goal is to remove the first node from your doubly linked list and return its data.

Modify the deleteHead method in your DoublyLinkedList:

// 📁 src/playground/doubly.ts

deleteHead(): T | null {
  if (!this.head) return null;

  let removedItem = this.head;

  if (this.len === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = removedItem.next;
    this.head!.prev = null;
    removedItem.next = null;
  }

  this.len--;

  return removedItem.data;
}

Here’s how deleteHead works:

If the list is empty, it returns null because there’s no node to remove.
It creates a new variable called removedItem and stores the head node in it as the item to be removed.
If the list’s length is 1, it means the list has only one node, which acts as both the head and tail of the list. In this case, it sets both the head and tail to null.
If the list has multiple nodes, it moves the head to the next node.
It sets the new head's prev to null since it’s now the first node.
It clears the removed node’s next pointer.
It decreases the list’s length by one.
It returns the removed node’s data.

This runs in O(1) time because you only change a few pointers without looping.

How to Delete the Last Node of a Doubly Linked List

The goal is to remove the last node from your doubly linked list and return its data.

Modify the deleteTail method in your DoublyLinkedList:

// 📁 src/playground/doubly.ts

deleteTail(): T | null {
  if (!this.tail) return null;

  let removedItem = this.tail;

  if (this.len === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.tail = this.tail.prev;
    this.tail!.next = null;
    removedItem.prev = null;
  }

  this.len--;

  return removedItem.data;
}

Here’s how deleteTail works:

It checks if the list is empty. If the tail is null, it returns null because there’s no node to remove.
It saves the tail node in a variable named removedItem as the node to be removed.
It checks if the list has one node. If the length is 1, it sets both head and tail to null.
If the list has multiple nodes, it moves the tail to the previous node.
It sets the new tail's next to null since it’s now the last node.
It clears the removed node’s prev pointer.
It decreases the list’s length by one.
It returns the removed node’s data.

This runs in O(1) time because you only change a few pointers without looping.

How to Delete a Node from a Doubly Linked List

The goal is to remove the first node with the given value from your doubly linked list and return true if successful.

Modify the delete method in your DoublyLinkedList:

// 📁 src/playground/doubly.ts

delete(data: T): boolean {
  let current = this.head;

  if (!current) return false;

  if (current.data === data) {
    this.head = current.next;
    if (this.head) this.head.prev = null;
    else this.tail = null;
    this.len--;
    return true;
  }

  while (current.next) {
    if (current.next.data === data) {
      let nodeToRemove = current.next;
      current.next = nodeToRemove.next;
      if (current.next) current.next.prev = current;
      else this.tail = current;
      nodeToRemove.next = null;
      nodeToRemove.prev = null;
      this.len--;
      return true;
    }
    current = current.next;
  }

  return false;
}

The data prop is the value to find and remove.

Here’s how delete works:

It checks if the list is empty - if the head is null, returns false because there’s nothing to delete.
It checks if the head node’s value matches data and if it does, moves the head to the next node, sets the new head’s prev to null or clears the tail if empty, decreases the length, and returns true.
If the head doesn’t match, it creates a new pointer called current at the head.
It moves current through the list while a next node exists, checking if the next node’s value matches data.
If a match is found, it skips the next node by linking current’s next to the node after it.
It updates the next node’s prev to current or sets the tail to current if it’s the last node, clears the removed node’s pointers, decreases the length, and returns true.
If no match is found, it moves current to the next node and keeps checking.
If you reach the end without a match, it returns false.

This runs in O(n) time because you may need to traverse the entire list to find the node.

How to Find a Node in a Doubly Linked List

The goal is to find the node at a specific position in your doubly linked list.

Modify the find method in your DoublyLinkedList:

// 📁 src/playground/doubly.ts

find(idx: number): N | null {
  if (idx < 0 || idx >= this.len) return null;

  let current: N | null = this.head;

  if (idx <= this.len / 2) {
    current = this.head;
    for (let i = 0; i < idx; i++) {
      current = current!.next;
    }
  } else {
    current = this.tail;
    for (let i = this.len - 1; i > idx; i--) {
      current = current?.prev ?? null;
    }
  }

  return current;
}

The idx prop is the position in the list, starting at 0.

Here’s how find works:

It checks if the index is valid. If idx is negative or too large, it returns null because no node exists.
It starts a new pointer called current at the head.
It checks if idx is in the first half of the list. If it is, it moves current forward idx times using the next pointer.
If idx is in the second half, it starts current at the tail and moves backward to the position using the prev pointer.
It returns the current node, which is at the given index, or null if the list is empty.

This runs in O(n) time because you may move through half the list to find the node.

How to Traverse a Doubly Linked List

The goal is to return an array of all node data in your doubly linked list, either forward or backward. Modify the traverse method in your DoublyLinkedList class:

// 📁 src/playground/doubly.ts

traverse(dir: "forward" | "backward" = "forward"): T[] {
  const isForward = dir === "forward";
  let current = isForward ? this.head : this.tail;
  const result: T[] = [];

  while (current) {
    result.push(current.data);
    current = isForward ? current.next : current.prev;
  }

  return result;
}

The dir prop sets whether to go forward (from head to tail) or backward (from tail to head).

Here’s how traverse works:

It checks the direction and sets a flag to true if moving forward.
It starts a new pointer called current at the head if forward, or the tail if backward.
It creates an empty array to store the node data.
While current exists, it adds its data to the array.
It moves current to the next node if forward, or the previous node if backward.
It returns the array with all node data.

This runs in O(n) time because you may need to visit every node in the list.

How to Insert a Node at a Specific Position in a Doubly Linked List

The goal is to add a new node at a specific index in your doubly linked list.

Modify the insertAt method in your DoublyLinkedList class:

// 📁 src/playground/doubly.ts

insertAt(idx: number, data: T): boolean {
  if (idx < 0 || idx > this.len) return false;

  if (idx === 0) {
    this.prepend(data);
    return true;
  }

  if (idx === this.len) {
    this.append(data);
    return true;
  }

  let newNode = new N(data);
  let current = this.find(idx);

  if (!current) return false;

  newNode.next = current;
  newNode.prev = current?.prev ?? null;
  current.prev!.next = newNode;
  current.prev = newNode;

  this.len++;

  return true;
}

The idx prop is the position in the list, and data is the value.

Here’s how insertAt works:

It checks if the index is invalid, if idx is negative or greater than the list’s length, returns false.
If the index is 0, you are adding the new node at the beginning. Simply call prepend to add the node at the start and return true.
If the index is equal to the list's length, you are adding the new node to the end of the list. In this case, you can call append to add the node at the end and return true.
If the previous conditions are not met, it creates a new node with the given data.
It finds the node at the given index using the find method and stores it as current.
If no node is found at the index, it returns false.
It points the new node’s next to current.
It points the new node’s prev to current’s previous node.
It points the previous node’s next to the new node.
It points current’s prev to the new node.
It increases the list’s length by one.
It returns true to show the node was successfully inserted.

This runs in O(n) time because finding the index may require traversing the list.

How to Test Your Doubly Linked List

Awesome, what great progress! You've successfully implemented your doubly linked list. Here's what the final implementation should look like:

// 📁 src/playground/doubly.ts
export class N {
  data: T;
  next: N | null;
  prev: N | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

/** Doubly linked list implementation */
export class DoublyLinkedList {
  /** Head node */
  public head: N | null;
  /** Tail node */
  public tail: N | null;
  /** List length */
  public len: number;

  /** Creates an empty list */
  constructor() {
    this.head = null;
    this.tail = null;
    this.len = 0;
  }

  /** Adds node to list start */
  prepend(data: T): void {
    let newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      let prevHead = this.head;
      newNode.next = prevHead;
      prevHead.prev = newNode;
      this.head = newNode;
    }

    this.len++;
  }

  /** Adds node to list end */
  append(data: T): void {
    let newNode = new N(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }

    this.len++;
  }

  /** Removes and returns head node data */
  deleteHead(): T | null {
    if (!this.head) return null;

    let removedItem = this.head;

    if (this.len === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = removedItem.next;
      this.head!.prev = null;
      removedItem.next = null;
    }

    this.len--;

    return removedItem.data;
  }

  /** Removes and returns tail node data */
  deleteTail(): T | null {
    if (!this.tail) return null;

    let removedItem = this.tail;

    if (this.len === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail!.next = null;
      removedItem.prev = null;
    }

    this.len--;

    return removedItem.data;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    let current = this.head;

    if (!current) return false;

    if (current.data === data) {
      this.head = current.next;
      if (this.head) this.head.prev = null;
      else this.tail = null;
      this.len--;
      return true;
    }

    while (current.next) {
      if (current.next.data === data) {
        let nodeToRemove = current.next;
        current.next = nodeToRemove.next;
        if (current.next) current.next.prev = current;
        else this.tail = current;
        nodeToRemove.next = null;
        nodeToRemove.prev = null;
        this.len--;
        return true;
      }
      current = current.next;
    }

    return false;
  }

  /** Finds node at given index */
  find(idx: number): N | null {
    if (idx < 0 || idx >= this.len) return null;

    let current: N | null = this.head;

    if (idx <= this.len / 2) {
      current = this.head;
      for (let i = 0; i < idx; i++) {
        current = current!.next;
      }
    } else {
      current = this.tail;
      for (let i = this.len - 1; i > idx; i--) {
        current = current?.prev ?? null;
      }
    }

    return current;
  }

  /** Returns array of node data */
  traverse(dir: "forward" | "backward" = "forward"): T[] {
    const isForward = dir === "forward";
    let current = isForward ? this.head : this.tail;
    const result: T[] = [];

    while (current) {
      result.push(current.data);
      current = isForward ? current.next : current.prev;
    }

    return result;
  }

  /** Inserts node at given index */
  insertAt(idx: number, data: T): boolean {
    if (idx < 0 || idx > this.len) return false;

    if (idx === 0) {
      this.prepend(data);
      return true;
    }

    if (idx === this.len) {
      this.append(data);
      return true;
    }

    let newNode = new N(data);
    let current = this.find(idx);

    if (!current) return false;

    newNode.next = current;
    newNode.prev = current?.prev ?? null;
    current.prev!.next = newNode;
    current.prev = newNode;

    this.len++;

    return true;
  }
}

Run the following command to make sure that your implementation is correct:

npm run test:file doubly

If the tests run successfully, you're good to go! If any tests fail, check src/examples/doubly.ts, fix the issue, and run the tests again.

You've learned how to implement a linked node with two pointers. Doubly linked lists are useful in many scenarios, but like singly linked lists, they have a limitation you need to consider.

Let's say you have a music playlist, and every time you reach the end, you want to loop back to the first song instead of stopping.

In both singly and doubly linked lists, once you reach the end, there's no way to loop back to the first item because the last node points to null. So, what will you do if you want to create a music playlist using linked lists?

That's what you'll learn in the next section of this tutorial!

What is a Circular Linked List?

So far, you've learned about singly and doubly linked lists, where the last item always points to null.

Sometimes, you need to go back to the first item after reaching the last one. In this case, the tail's next pointer should point to the head instead of null.

This is what a circular linked list is. In circular linked lists, the tail points to the head, letting you keep going through the list without stopping.

In the next 2 sections, you'll learn about two types of circular linked lists:

Circular Singly Linked List: Each node has one pointer to the next node, and the tail always points to the head.
Circular Doubly Linked List: Each node has two pointers to the next and previous nodes. The tail points to the head as its next node, and the head points to the tail as its previous node.

Now, let's dive deeper and learn how to create each of these lists.

What is a Circular Singly Linked List?

In a circular singly linked list, each node has only one pointer that points to the next node in the list. The main difference between a singly linked list and a circular singly linked list is the tail node.

In a circular singly linked list, the tail always points to the head, forming a circle that allows continuous looping through the list.

Now, let's look at the node structure in a circular singly linked list.

How to Create a Generic Node Structure for a Circular Singly Linked List

The Node structure in a circular singly linked list has two parts: the data and a pointer to the next node.

The data property holds the node's value, and next points to the next node in the list.

Open src/playground/circular-1.ts and modify the N class:

/** Node for circular singly linked list */
export class N {
  /** Node data */
  public data: T;
  /** Next node reference */
  public next: N | null;

  /** Creates a node with given data */
  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

Here’s how the node structure works:

It builds a generic Node: Uses to handle any data type, such as numbers or strings.
It stores the node’s value: Assigns the value to the data property.
It links to the next node: Sets the next pointer to the next node, null only during initialization. In a valid circular list, next always connects to a node.
It initializes the node: Takes a value in the constructor and assigns it to data.

In a valid circular linked list, next never stays null.

How to Implement a Circular Singly Linked List

Once you have created your Node structure, you can start implementing the linked list.

To get started, let’s open src/playground/circular-1.ts, where you'll find the CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

export class N {
  data: T;
  next: N | null;
  prev: N | null;

  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

export class CircularSinglyLinkedList {
  /** Head node */
  public head: N | null = null;

  /** Adds node to list start */
  prepend(data: T): void {}

  /** Adds node to list end */
  append(data: T): void {}

  /** Removes head node */
  deleteHead(): void {}

  /** Removes tail node */
  deleteTail(): boolean {
    return false;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    return false;
  }

  /** Finds data at given index */
  find(idx: number): T | null {
    return null;
  }

  /** Returns array of node data */
  traverse(): T[] {
    return [];
  }
}

You will complete each method by the end of this section.

Like in earlier implementations, head will point to the first item in the list. If it's null, the list is empty.

Now, let's go to the first method and learn how to add a node to the start of a circular linked list.

How to Prepend a Node in a Circular Singly Linked List

The goal is to add a new node to the beginning of your circular singly linked list and update the head pointer to this new node.

Modify the prepend method in your CircularSinglyLinkedList class located in src/playground/circular-singly.ts:

// 📁 src/playground/circular-1.ts

prepend(data: T) {
  let newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    newNode.next = newNode;
  } else {
    let last = this.head;

    while (last.next !== this.head) {
      if (!last.next) throw new Error("invalid list");
      last = last.next;
    }

    last.next = newNode;
    newNode.next = this.head;
    this.head = newNode;
  }
}

The data prop holds the value for the new node.

Here’s how prepend works:

It creates a new node with the given value.
Checks if the list is empty. If the head is null, it sets the head to the new node and points its next to itself to form a single-node circle.
If the list has nodes, it finds the last node by moving through the list until it reaches the node whose next points to the head.
It points the last node’s next to the new node.
It points the new node’s next to the current head.
It sets the head to the new node.
Now, the new node is the head, and you’ve maintained the circular structure.

This runs in O(n) time because you may need to traverse the entire list to find the last node.

How to Append a Node in a Circular Singly Linked List

The goal is to add a new node to the end of your circular singly linked list and maintain the circular structure.

Let’s modify the append method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

append(data: T): void {
  let newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    newNode.next = this.head;
  } else {
    let last = this.head;

    while (last.next !== this.head) {
      if (!last.next) throw new Error("invalid list");
      last = last.next;
    }

    last.next = newNode;
    newNode.next = this.head;
  }
}

The data prop holds the value for the new node.

Here’s how append works:

It creates a new node with the given value.
It checks if the list is empty. If the head is null, it sets the head to the new node and points its next to itself to form a single-node circle.
If the list has nodes, it finds the last node by moving through the list until it reaches the node whose next points to the head.
It points the last node’s next to the new node.
It points the new node’s next to the head to keep the list circular.
Now, the new node is at the end, and you’ve maintained the circular structure.
It increases the list’s length by one.

This runs in O(n) time because you may need to traverse the entire list to find the last node.

How to Delete the Head of a Circular Singly Linked List

The goal is to remove the first node from your circular singly linked list and update the head pointer.

Modify the deleteHead method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

deleteHead(): void {
  if (!this.head) return;

  if (this.head.next === this.head) {
    this.head = null;
    return;
  }

  let last = this.head;

  while (last.next !== this.head) {
    if (!last.next) throw new Error("invalid list");
    last = last.next;
  }

  let newHead = this.head.next;
  last.next = newHead;
  this.head = newHead;
}

Here’s how deleteHead works:

It checks if the list is empty and stops the operation if the head is null because there’s no node to remove.
It checks if the list has one node: if the head's next points to itself, it sets the head to null to empty the list.
If the list has multiple nodes, it finds the last node by moving through the list until it reaches the node whose next points to the head.
It sets the current head’s next node as the new head.
It points the tail node’s next to the new head to keep the list circular.
It sets the head to the new head.

This runs in O(n) time because you may need to traverse the entire list to find the last node.

How to Delete the Last Node of a Circular Singly Linked List

The goal is to remove the last node from your circular singly linked list and maintain the circular structure.

Modify the deleteTail method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

deleteTail(): boolean {
  if (!this.head) return false;

  if (this.head.next === this.head) {
    this.head = null;
    return true;
  }

  let current: N = this.head;
  let prev: N | null = null;

  while (current.next !== this.head) {
    prev = current;
    current = current.next!;
  }

  prev!.next = this.head;
  return true;
}

Here’s how deleteTail works:

It checks if the list is empty. If the head is null, it returns false because there’s no node to remove.
It checks if the list has one node. If the head’s next points to itself, it sets the head to null and returns true.
If the list has multiple nodes, it starts a new pointer called current at the head and a prev pointer at null.
It moves current through the list until its next points to the head, keeping prev one node behind.
It points prev’s next to the head to skip the last node and keep the list circular.
It returns true to show the tail was removed.

This runs in O(n) time because you may need to traverse the entire list to find the last node.

How to Delete a Node from a Circular Singly Linked List

The goal is to remove the first node with the given value from your circular singly linked list and return true if successful.

Modify the delete method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

delete(data: T): boolean {
  if (!this.head) return false;

  if (this.head.data === data) {
    this.deleteHead();
    return true;
  }

  let current: N = this.head;
  let prev: N | null = null;

  do {
    if (current.data === data) {
      prev!.next = current.next;
      return true;
    }

    prev = current;
    current = current.next!;
  } while (current !== this.head);

  return false;
}

The data prop is the value to find and remove.

You must use a do-while loop instead of a simple while loop in the method because it ensures you always process the head node's data at least once before checking if you've returned to the head.

In a circular singly linked list, you start at the head and keep moving to the next node until you come back to the head.

A simple while loop might skip the head if checked first, but a do-while loop makes sure the head's data is included.

Here’s how delete works:

It checks if the list is empty. If the head is null, it returns false because there’s nothing to delete.
It checks if the head node’s value matches data. If it does, it calls deleteHead to remove the head and returns true.
If the head doesn’t match, it starts a new pointer called current at the head and a prev pointer at null.
It moves current through the list, keeping prev one node behind, until it circles back to the head.
If current’s value matches data, it links prev’s next to current’s next to skip the matched node.
It returns true if a match is removed, or false if it finds no match after a full loop.

This runs in O(n) time because you may need to traverse the entire list to find the node.

How to Find a Node in a Circular Singly Linked List

The goal is to find the data at a specific index in your circular singly linked list.

Modify the find method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

find(idx: number): T | null {
  if (!this.head || idx < 0) return null;

  let current = this.head;
  let count = 0;

  do {
    if (!current.next) throw new Error("invalid list");

    if (count === idx) {
      return current.data;
    }

    count++;
    current = current.next;
  } while (current !== this.head);

  return null;
}

The idx prop is the position in the list.

Here’s how find works:

It checks if the list is empty or the index is negative. If so, it returns null because no data exists.
It creates a new pointer called current at the head and set a counter to 0.
It moves current through the list, checking each node until it circles back to the head.
If the counter equals idx, it returns the current node’s data.
If not, it increases the counter and moves current to the next node.
If you circle back to the head without finding the index, it returns null.

This runs in O(n) time because you may need to traverse the entire list to find the index.

How to Traverse a Circular Singly Linked List

The goal is to return an array of all node data in your circular singly linked list.

Modify the traverse method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

traverse(): T[] {
  if (!this.head) return [];
  const result: T[] = [];

  let current = this.head;

  do {
    result.push(current.data);
    current = current.next!;
  } while (current !== this.head);

  return result;
}

Here’s how traverse works:

It checks if the list is empty. If the head is null, it returns an empty array.
It creates an empty array to store the node data.
It creates a new pointer called current at the head.
It moves current through the list, adding each node’s data to the array.
It continues moving current to the next node until you circle back to the head.
It returns the array with all node data.

This runs in O(n) time because you need to visit every node in the list.

How to Insert a Node at a Specific Position in a Circular Singly Linked List

The goal is to add a new node at a specific index in your circular singly linked list.

Modify the insertAt method in your CircularSinglyLinkedList class:

// 📁 src/playground/circular-1.ts

insertAt(data: T, idx: number): boolean {
  if (idx < 0) return false;

  if (idx === 0) {
    this.prepend(data);
    return true;
  }

  if (!this.head) {
    if (idx === 0) {
      this.prepend(data);
      return true;
    }
    return false;
  }

  let current: N | null = this.head;
  let prev: N | null = null;
  let count = 0;

  do {
    if (count === idx) {
      const newN = new N(data);
      newN.next = current;
      prev!.next = newN;
      return true;
    }
    prev = current;
    current = current!.next;
    count++;
  } while (current !== this.head);

  if (count === idx) {
    this.append(data);
    return true;
  }

  return false;
}

The data prop is the value, and idx is the position in the list.

Here’s how insertAt works:

If the index is negative, it returns false because it’s invalid.
If the index is 0, it calls prepend to add the node at the start and returns true.
It creates a new pointer called current at the head, a prev pointer at null, and a counter at 0.
It moves current through the list, keeping prev one node behind, until you circle back to the head.
If the counter equals idx, it creates a new node, point its next to current, points prev’s next to the new node, and returns true.
If you circle back to the head and the counter equals idx, it calls append to add the node at the end and returns true.
Finally, if the index is not found, it returns false.

This runs in O(n) time because you may need to traverse the entire list to find the index.

How to Test Your Circular Singly Linked List

Perfect! You are done with the circular singly linked list and now you are ready to test your implementation.

Your final implementation should look something like this:

/** Node for circular singly linked list */
export class N {
  /** Node data */
  public data: T;
  /** Next node reference */
  public next: N | null;

  /** Creates a node with given data */
  constructor(data: T) {
    this.data = data;
    this.next = null;
  }
}

/** Circular singly linked list implementation */
export class CircularSinglyLinkedList {
  /** Head node */
  public head: N | null = null;

  /** Adds node to list start */
  prepend(data: T) {
    let newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      newNode.next = newNode;
    } else {
      let last = this.head;

      while (last.next !== this.head) {
        if (!last.next) throw new Error("invalid list");
        last = last.next;
      }

      last.next = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
  }

  /** Adds node to list end */
  append(data: T): void {
    let newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      newNode.next = this.head;
    } else {
      let last = this.head;

      while (last.next !== this.head) {
        if (!last.next) throw new Error("invalid list");
        last = last.next;
      }

      last.next = newNode;
      newNode.next = this.head;
    }
  }

  /** Removes head node */
  deleteHead(): void {
    if (!this.head) return;

    if (this.head.next === this.head) {
      this.head = null;
      return;
    }

    let last = this.head;

    while (last.next !== this.head) {
      if (!last.next) throw new Error("invalid list");
      last = last.next;
    }

    let newHead = this.head.next;
    last.next = newHead;
    this.head = newHead;
  }

  /** Removes tail node */
  deleteTail(): boolean {
    if (!this.head) return false;

    if (this.head.next === this.head) {
      this.head = null;
      return true;
    }

    let current: N = this.head;
    let prev: N | null = null;

    while (current.next !== this.head) {
      prev = current;
      current = current.next!;
    }

    prev!.next = this.head;
    return true;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    if (!this.head) return false;

    if (this.head.data === data) {
      this.deleteHead();
      return true;
    }

    let current: N = this.head;
    let prev: N | null = null;

    do {
      if (current.data === data) {
        prev!.next = current.next;
        return true;
      }

      prev = current;
      current = current.next!;
    } while (current !== this.head);

    return false;
  }

  /** Finds data at given index */
  find(idx: number): T | null {
    if (!this.head || idx < 0) return null;

    let current = this.head;
    let count = 0;

    do {
      if (!current.next) throw new Error("invalid list");

      if (count === idx) {
        return current.data;
      }

      count++;
      current = current.next;
    } while (current !== this.head);

    return null;
  }

  /** Returns array of node data */
  traverse(): T[] {
    if (!this.head) return [];
    const result: T[] = [];

    let current = this.head;

    do {
      result.push(current.data);
      current = current.next!;
    } while (current !== this.head);

    return result;
  }

  /** Inserts node at given index */
  insertAt(data: T, idx: number): boolean {
    if (idx < 0) return false;

    if (idx === 0) {
      this.prepend(data);
      return true;
    }

    if (!this.head) {
      if (idx === 0) {
        this.prepend(data);
        return true;
      }
      return false;
    }

    let current: N | null = this.head;
    let prev: N | null = null;
    let count = 0;

    do {
      if (count === idx) {
        const newN = new N(data);
        newN.next = current;
        prev!.next = newN;
        return true;
      }
      prev = current;
      current = current!.next;
      count++;
    } while (current !== this.head);

    if (count === idx) {
      this.append(data);
      return true;
    }

    return false;
  }
}

Now, let’s run the following command to test the linked list:

npm run test:file circular-1

If the tests run successfully, you're all set! If any tests fail, check src/examples/circular-1.ts, fix the issue, and run the tests again.

That's it, you've completed your first circular linked list implementation.

In the last section, you'll learn how to create a circular linked list with two pointers instead of one.

What is a Circular Doubly Linked List?

A circular doubly linked list forms a loop where nodes connect to both the next and previous nodes.

The head links back to the tail, and the tail to the head, so you can have endless navigation in either direction.

How to Create a Generic Node Structure for a Circular Doubly Linked List

The Node structure in a circular doubly linked list has three parts: the data, a pointer to the next node, and a pointer to the previous node.

The data property holds the node’s value, next points to the next node, and prev points to the previous node in the list.

Open src/playground/circular-2.ts and modify the N class:

// 📁 src/playground/circular-2.ts

/** Node for circular doubly linked list */
export class N {
  /** Node data */
  public data: T;
  /** Next node reference */
  public next: N | null;
  /** Previous node reference */
  public prev: N | null;

  /** Creates a node with given data */
  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

Here’s how the node structure works:

It builds a generic Node: Uses to handle any data type.
It stores the node’s value: Assigns the value to the data property.
It links to the next node: Sets the next pointer to the next node, null only during initialization. In a valid circular list, next always connects to a node.
It links to the previous node: Sets the prev pointer to the previous node, null only during initialization. In a valid circular list, prev always connects to a node.
It initializes the node: Takes a value in the constructor and assigns it to data.

In a valid circular doubly linked list, next and prev never stay null.

How to Implement a Circular Doubly Linked List

You’ve created the Node structure for your circular doubly linked list. Now, you can start building the linked list itself. To get started, open src/playground/circular-2.ts, where you’ll find the CircularDoublyLinkedList class:

// 📁 src/playground/circular-2.ts

export class N {
  /** Node data */
  public data: T;
  /** Next node reference */
  public next: N | null;
  /** Previous node reference */
  public prev: N | null;

  /** Creates a node with given data */
  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

export class CircularDoublyLinkedList {
  /** Head node */
  public head: N | null;
  /** Tail node */
  public tail: N | null;
  /** List length */
  public len: number;

  /** Creates an empty list */
  constructor() {
    this.head = null;
    this.tail = null;
    this.len = 0;
  }

  /** Adds node to list end */
  append(data: T): void {}

  /** Removes and returns tail node data */
  deleteTail(): T | null {
    return null;
  }

  /** Adds node to list start */
  prepend(data: T): void {}

  /** Removes and returns head node data */
  deleteHead(): T | null {
    return null;
  }

  /** Finds node at given index */
  find(idx: number): N | null {
    return null;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    return false;
  }

  /** Returns array of node data */
  traverse(): T[] {
    return [];
  }

  /** Inserts node at given index */
  insertAt(idx: number, data: T): boolean {
    return false;
  }
}

The head points to the first node and links backward to the tail to form a circular loop. It is null when the list is empty.

The tail points to the last node and links forward to the head to complete the circle. It is also null when empty.

The length, len, tracks the number of nodes. It starts at 0 and changes as you add or remove nodes.

Now, let’s move to the first method and learn how to add a node to the start of a circular doubly linked list.

How to Prepend a Node in a Circular Doubly Linked List

The goal is to add a new node to the beginning of your circular doubly linked list and update the head pointer to this new node.

Modify the prepend method in your CircularDoublyLinkedList class located in src/playground/circular-2.ts:

// 📁 src/playground/circular-2.ts

prepend(data: T): void {
  let newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = newNode;
    newNode.prev = newNode;
  } else {
    newNode.next = this.head;
    newNode.prev = this.tail;
    this.head!.prev = newNode;
    this.tail!.next = newNode;
    this.head = newNode;
  }

  this.len++;
}

The data prop holds the value for the new node.

Here’s how prepend works:

It creates a new node with the given data.
it checks if the list is empty. If the head is null, it sets both head and tail to the new node and links its next and prev to itself to form a single-node circle.
If the list has nodes, it points the new node’s next to the current head and its prev to the current tail.
It points the current head’s prev to the new node.
It points the current tail’s next to the new node to keep the list circular.
It sets the head to the new node.
It increases the list’s length by one.

This runs in O(1) time because you only change a few pointers without looping.

How to Append a Node in a Circular Doubly Linked List

The goal is to add a new node to the end of your circular doubly linked list and update the tail pointer to this new node.

Modify the append method in your CircularDoublyLinkedList class:

// 📁 src/playground/circular-2.ts

append(data: T): void {
  let newNode = new N(data);

  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
    newNode.next = newNode;
    newNode.prev = newNode;
  } else {
    newNode.next = this.head;
    newNode.prev = this.tail;
    this.tail!.next = newNode;
    this.head!.prev = newNode;
    this.tail = newNode;
  }

  this.len++;
}

The data prop holds the value for the new node, like a number or string.

Here’s how append works:

It makes a new node with the given value.
If the list is empty, then it sets both head and tail to the new node, and links its next and prev to itself to form a single-node circle.
If the list has nodes, it points the new node’s next to the head to maintain the circular loop.
It points the new node’s prev to the current tail.
It points the current tail’s next to the new node.
It points the head’s prev to the new node to complete the circle.
It sets the tail to the new node.
It increases the list’s length by one.

This runs in O(1) time because you only change a few pointers without looping.

How to Delete the Last Node of a Circular Doubly Linked List

The goal is to remove the last node from your circular doubly linked list and return its data.

Modify the deleteTail method in your CircularDoublyLinkedList class:

// 📁 src/playground/circular-2.ts

deleteTail(): T | null {
  if (!this.tail) return null;

  let removedItem = this.tail;

  if (this.len === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.tail = this.tail.prev;
    this.tail!.next = this.head;
    this.head!.prev = this.tail;
  }

  removedItem.next = null;
  removedItem.prev = null;
  this.len--;

  return removedItem.data;
}

Here’s how deleteTail works:

If the list is empty, then it returns null because there’s no node to remove.
It declares a variable called removedItem and stores the tail node in it to keep track of the node you want to remove.
It checks if the list has one node. If the length is 1, it sets both head and tail to null.
If the list has multiple nodes, it moves the tail to the previous node.
It points the new tail’s next to the head to keep the circular loop.
It points the head’s prev to the new tail to maintain the circle.
It clears the removed node’s next and prev pointers.
It decreases the list’s length by one.
It returns the removed node’s data.

This runs in O(1) time because you only change a few pointers without looping.

How to Delete the Head of a Circular Doubly Linked List

The goal is to remove the first node from your circular doubly linked list and return its data.

Modify the deleteHead method in your CircularDoublyLinkedList class:

// 📁 src/playground/circular-2.ts

deleteHead(): T | null {
  if (!this.head) return null;

  let removedItem = this.head;

  if (this.len === 1) {
    this.head = null;
    this.tail = null;
  } else {
    this.head = removedItem.next;
    this.head!.prev = this.tail;
    this.tail!.next = this.head;
  }

  this.len--;
  removedItem.next = null;
  removedItem.prev = null;
  return removedItem.data;
}

Here’s how deleteHead works:

If the list is empty then it returns null because there’s no node to remove.
It declares a variable called removedItem and stores the head node in it to keep track of the node you want to remove.
It checks if the list has one node. If the length is 1, it sets both head and tail to null.
If the list has multiple nodes, it moves the head to the next node to make it the new first node.
It points the new head’s prev to the tail to maintain the backward loop in the circular structure.
It points the tail’s next to the new head to keep the forward loop in the circular structure.
It clears the removed node’s next and prev pointers to disconnect it from the list.
It decreases the list’s length by one.
It returns the removed node’s data.

This runs in O(1) time because you only change a few pointers without looping.

How to Find a Node in a Circular Doubly Linked List

The goal is to find the node at a specific index in your circular doubly linked list.

Modify the find method in your CircularDoublyLinkedList class:

// 📁 src/playground/circular-2.ts

find(idx: number): N | null {
  if (!this.head || idx < 0 || idx >= this.len) {
    return null;
  }

  let current = this.head;
  for (let i = 0; i < idx; i++) {
    current = current!.next!;
  }

  return current;
}

The idx prop is the position in the list. Here’s how find works:

It checks if the list is empty or the index is invalid. If the head is null, idx is negative, or idx is too large, it returns null because no node exists.
It creates a new pointer called current at the head.
It moves current forward through the next pointers as many times as the index value.
Once you exit the loop, it returns the current node, which is at the specified index.

This runs in O(n) time because you may need to traverse up to n nodes to reach the index.

How to Traverse a Circular Doubly Linked List

The goal is to return an array of all node data in your circular doubly linked list.

Modify the traverse method in your CircularDoublyLinkedList:

// 📁 src/playground/circular-2.ts

traverse(): T[] {
  if (!this.head) return [];

  let current = this.head;
  const result: T[] = [];

  do {
    if (!current.next) throw new Error("invalid list");

    result.push(current.data);

    current = current.next;
  } while (current !== this.head);

  return result;
}

Here’s how traverse works:

If the list is empty, it returns an empty array.
It creates an empty array to store the node data.
It creates a new pointer called current at the head.
It adds the current node’s data to the array.
It moves current to the next node using the next pointer.
It repeats adding data and moving current until you circle back to the head.
It returns the array with all node data.

This runs in O(n) time because you need to visit every node in the list.

How to Delete a Node from a Circular Doubly Linked List

The goal is to remove the first node with the given value from your circular doubly linked list and return true if successful.

Modify the delete method in your CircularDoublyLinkedList class located in:

// 📁 src/playground/circular-2.ts

delete(data: T): boolean {
  if (!this.head) return false;

  let current = this.head;

  do {
    if (current.data === data) {
      if (this.len === 1) {
        this.head = null;
        this.tail = null;
      } else {
        current.prev!.next = current.next;
        current.next!.prev = current.prev;
        if (current === this.head) {
          this.head = current.next;
        }
        if (current === this.tail) {
          this.tail = current.prev;
        }
      }
      this.len--;
      return true;
    }
    current = current.next!;
  } while (current !== this.head);

  return false;
}

The data prop is the value to find and remove. Here’s how delete works:

If the list is empty, then it returns false because there’s nothing to delete.
It creates a new pointer called current at the head.
It moves current through the list and checks each node’s value until you circle back to the head.
If current’s value matches data, it checks if the list has one node, if so, it sets both head and tail to null since the single node within the list is both the head and the tail.
If the list has multiple nodes, it links the previous node’s next to the next node and the next node’s prev to the previous node to skip current.
If current is the head, it updates the head to the next node. If current is the tail, it updates the tail to the previous node.
It decreases the list’s length by one and returns true.
If no match, it moves current to the next node and continues checking.
If you circle back to the head without a match, it returns false.

This runs in O(n) time because you may need to traverse the entire list to find the node.

How to Insert a Node at a Specific Position in a Circular Doubly Linked List

The goal is to add a new node at a specific index in your circular doubly linked list.

Modify the insertAt method in your CircularDoublyLinkedList:

// 📁 src/playground/circular-2.ts

insertAt(idx: number, data: T): boolean {
  if (idx < 0 || idx > this.len) return false;

  if (idx === 0) {
    this.prepend(data);
    return true;
  }

  if (idx === this.len) {
    this.append(data);
    return true;
  }

  let newNode = new N(data);
  let current = this.find(idx);

  if (!current) return false;

  newNode.next = current;
  newNode.prev = current!.prev;
  current.prev!.next = newNode;
  current.prev = newNode;

  this.len++;
  return true;
}

The idx prop is the position in the list, and data is the value.

Here’s how insertAt works:

If idx is negative or greater than the list’s length, then the idx prop is an invalid index, and you should return false to stop the operation.
If the index is 0, it calls prepend to add the node at the start and returns true.
If the idx equals the list's length, you are adding a new tail. In this case, it calls append to add the node at the end and returns true.
If the above conditions are not met, it creates a new node with the given data.
It finds the node at the given index using the find method and stores it as current.
If no node is found at the idx, it returns false.
It points the new node’s next to current. This sets the new node to precede current in the forward direction of the circular list.
This sets the new node’s prev to current’s prev node. This links the new node to the node before current and keeps the backward link in the circular list intact.
It sets the previous node's next to the new node, so the node before current now links to the new node. This keeps the circular loop intact by making sure the forward chain skips the original predecessor of current and includes the new node.
It sets current's prev to the new node. This completes the insertion by making current link back to the new node and keeping the circular structure with correct two-way links.
It increases the list’s length by one.
It returns true to show the node was inserted.

This runs in O(n) time because finding the index may require traversing the list.

How to Test Your Circular Doubly Linked List

Great job! You’ve completed the circular doubly linked list, and now you’re ready to test your implementation.

Your final implementation should look like this:

// 📁 src/playground/circular-2.ts

/** Node for circular doubly linked list */
export class N {
  /** Node data */
  public data;
  /** Next node reference */
  public next: N | null;
  /** Previous node reference */
  public prev: N | null;

  /** Creates a node with given data */
  constructor(data: T) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

/** Circular doubly linked list implementation */
export class CircularDoublyLinkedList {
  /** Head node */
  public head: N | null;
  /** Tail node */
  public tail: N | null;
  /** List length */
  public len: number;

  /** Creates an empty list */
  constructor() {
    this.head = null;
    this.tail = null;
    this.len = 0;
  }

  /** Adds node to list end */
  append(data: T): void {
    let newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.tail!.next = newNode;
      this.head!.prev = newNode;
      this.tail = newNode;
    }

    this.len++;
  }

  /** Removes and returns tail node data */
  deleteTail(): T | null {
    if (!this.tail) return null;

    let removedItem = this.tail;

    if (this.len === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = this.tail.prev;
      this.tail!.next = this.head;
      this.head!.prev = this.tail;
    }

    removedItem.next = null;
    removedItem.prev = null;
    this.len--;

    return removedItem.data;
  }

  /** Adds node to list start */
  prepend(data: T): void {
    let newNode = new N(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      newNode.next = newNode;
      newNode.prev = newNode;
    } else {
      newNode.next = this.head;
      newNode.prev = this.tail;
      this.head!.prev = newNode;
      this.tail!.next = newNode;
      this.head = newNode;
    }

    this.len++;
  }

  /** Removes and returns head node data */
  deleteHead(): T | null {
    if (!this.head) return null;

    let removedItem = this.head;

    if (this.len === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.head = removedItem.next;
      this.head!.prev = this.tail;
      this.tail!.next = this.head;
    }

    this.len--;
    removedItem.next = null;
    removedItem.prev = null;
    return removedItem.data;
  }

  /** Finds node at given index */
  find(idx: number): N | null {
    if (!this.head || idx < 0 || idx >= this.len) {
      return null;
    }

    let current = this.head;
    for (let i = 0; i < idx; i++) {
      current = current!.next!;
    }

    return current;
  }

  /** Removes first node with given data */
  delete(data: T): boolean {
    if (!this.head) return false;

    let current = this.head;

    do {
      if (current.data === data) {
        if (this.len === 1) {
          this.head = null;
          this.tail = null;
        } else {
          current.prev!.next = current.next;
          current.next!.prev = current.prev;
          if (current === this.head) {
            this.head = current.next;
          }
          if (current === this.tail) {
            this.tail = current.prev;
          }
        }
        this.len--;
        return true;
      }
      current = current.next!;
    } while (current !== this.head);

    return false;
  }

  /** Returns array of node data */
  traverse(): T[] {
    if (!this.head) return [];

    let current = this.head;
    const result: T[] = [];

    do {
      if (!current.next) throw new Error("invalid list");

      result.push(current.data);

      current = current.next;
    } while (current !== this.head);

    return result;
  }

  /** Inserts node at given index */
  insertAt(idx: number, data: T): boolean {
    if (idx < 0 || idx > this.len) return false;

    if (idx === 0) {
      this.prepend(data);
      return true;
    }

    if (idx === this.len) {
      this.append(data);
      return true;
    }

    let newNode = new N(data);
    let current = this.find(idx);

    if (!current) return false;

    newNode.next = current;
    newNode.prev = current!.prev;
    current.prev!.next = newNode;
    current.prev = newNode;

    this.len++;
    return true;
  }
}

Run the following command to test the linked list:

npm run test:file circular-2

If the tests pass successfully, you’re all set! If any tests fail, review src/examples/circular-2.ts, fix the issues, and run the tests again.

When to Use Linked Lists (and When to Avoid Them)

Linked lists are powerful data structures, but they're not always the best choice. So it's important to know when to use them and when to choose an alternative.

Why Use Linked Lists?

Linked lists are great for situations that need dynamic data or flexible navigation.

Their main benefits include:

Dynamic size: Add or remove nodes without resizing, unlike arrays that need reallocation.
Efficient insertions/deletions: Operations like prepend or delete are quick (O(1) at known positions), which is very ideal for frequent updates.
Flexible traversal: Doubly and circular lists allow you to move forward or backward, which makes them helpful for complex navigation patterns.

Real-World Use Cases

You should consider using linked lists in scenarios where the data is frequently updated or requires cyclic or bidirectional access:

Browser history: A doubly linked list keeps track of visited pages and lets users easily move back and forth. Adding a new page (prepend) or removing one (delete) is fast, and the list grows dynamically as users browse.
Music playlists: Circular doubly linked lists are used for looping playlists in apps like Spotify. Users can easily skip forward (next) or backward (prev), and new songs (append) fit smoothly into the loop.
Undo/redo functionality: Text editors use doubly linked lists to store actions. Each edit is a node, and moving backward (undo) or forward (redo) navigates through the list.
Task scheduling: Circular singly linked lists are used for round-robin scheduling in operating systems. Each process is a node, and the list cycles through them to allocate CPU time. New tasks are added using append.

When Not to Use Linked Lists

Despite their strengths, linked lists have weaknesses in some situations because of their structure:

Slow random access: Reaching an index requires you to traverse from the head (O(n)), unlike arrays, which have O(1) access.
High memory overhead: Each node in a linked list stores pointers (next, prev), which uses more memory than arrays. This can be an issue for large datasets.
Poor search performance: Finding a value requires checking each node (O(n)), which is slower than hash tables (O(1)) or binary search trees (O(log n)).

Better Alternatives for Specific Cases

In some cases, other data structures outperform linked lists:

Random access: Use arrays or dynamic arrays (like JavaScript’s Array) for quick indexing. For instance, if you need to show a table in a web app, an array's O(1) access lets you quickly reach any row.
Frequent searches: Hash tables (like JavaScript’s Map) are better for fast lookups. For example, a contact list app that searches by name would use a hash table to speed up the process.
Memory-constrained environments: Arrays use less memory for large, fixed-size datasets, such as image processing buffers in graphics apps.

The key takeaway is that linked lists are great when your data needs dynamic growth, frequent insertions or deletions, or cyclic navigation, like in playlists or history features.

Avoid using linked lists for random access, frequent searches, or memory-sensitive tasks, where arrays, hash tables, or trees are better options.

You can experiment with your src/playground implementations to see how linked lists fit your project’s needs.

Conclusion

Congratulations on finishing this handbook! 🥳 You've learned how to implement different types of linked lists using TypeScript, including singly linked lists, doubly linked lists, and circular linked lists.

By understanding these linked lists, you're well-prepared to work with more complex data structures.

Thanks for following along with this tutorial. You can follow me on X, where I share more useful tips on data structures and web development.

Happy coding!

Yazdun - freeCodeCamp.org

How to Work with Queues in TypeScript

Here’s what we’ll cover

Prerequisites

Getting Started

What Are Queues?

What Are Linked Lists?

What is a Simple Queue?

What is a Circular Queue?

What is a Double Ended Queue?

What is a Priority Queue?

When to Use Queues (and When to Avoid Them)

When to Avoid Queues

Conclusion

How to Code Linked Lists with TypeScript: A Handbook for Developers

Here’s What We’ll Cover

Prerequisites

Getting Started

What are Linked Lists?

What is a Singly Linked List?

How to Create a Generic Node Structure for a Singly Linked List

How to Implement a Singly Linked List

What is the head Pointer in a Linked List?

How to Prepend a Node in a Singly Linked List

How to Append a Node in a Singly Linked List

How to Delete the head of a Singly Linked List

How to Delete the Last Node of a Singly Linked List

How to Delete a Node from a Singly Linked List

How to Find a Node in a Singly Linked List

How to Insert a Node at a Specific Position in a Singly Linked List

How to Traverse a Singly Linked List

How to Test Your Singly Linked List

What is a Doubly Linked List?

How to Create a Generic Node Structure for a Doubly Linked List

How to Implement a Doubly Linked List

How to Prepend a Node in a Doubly Linked List

How to Append a Node in a Doubly Linked List

How to Delete the Head of a Doubly Linked List

How to Delete the Last Node of a Doubly Linked List

How to Delete a Node from a Doubly Linked List

How to Find a Node in a Doubly Linked List

How to Traverse a Doubly Linked List

How to Insert a Node at a Specific Position in a Doubly Linked List

How to Test Your Doubly Linked List

What is a Circular Linked List?

What is a Circular Singly Linked List?

How to Create a Generic Node Structure for a Circular Singly Linked List

How to Implement a Circular Singly Linked List

How to Prepend a Node in a Circular Singly Linked List

How to Append a Node in a Circular Singly Linked List

How to Delete the Head of a Circular Singly Linked List

How to Delete the Last Node of a Circular Singly Linked List

How to Delete a Node from a Circular Singly Linked List

How to Find a Node in a Circular Singly Linked List

How to Traverse a Circular Singly Linked List

How to Insert a Node at a Specific Position in a Circular Singly Linked List

How to Test Your Circular Singly Linked List

What is a Circular Doubly Linked List?

How to Create a Generic Node Structure for a Circular Doubly Linked List

How to Implement a Circular Doubly Linked List

How to Prepend a Node in a Circular Doubly Linked List

How to Append a Node in a Circular Doubly Linked List

How to Delete the Last Node of a Circular Doubly Linked List

How to Delete the Head of a Circular Doubly Linked List

How to Find a Node in a Circular Doubly Linked List

How to Traverse a Circular Doubly Linked List

How to Delete a Node from a Circular Doubly Linked List

How to Insert a Node at a Specific Position in a Circular Doubly Linked List

How to Test Your Circular Doubly Linked List

When to Use Linked Lists (and When to Avoid Them)

Why Use Linked Lists?

Real-World Use Cases

When Not to Use Linked Lists

Better Alternatives for Specific Cases

Conclusion

What is the `head` Pointer in a Linked List?

How to Delete the `head` of a Singly Linked List