Types of Linked Lists (Singly, Doubly, Circular)

Types of Linked Lists

Linked lists come in several flavors, each offering different trade-offs in terms of memory overhead and the operations they make easy or hard. Below we’ll cover three core variations:

Singly Linked List
Doubly Linked List
Circular Linked List

In every case, N denotes the number of nodes in the list, and value is the payload each node carries.

1. Singly Linked List (SLL)

A singly linked list is what we looked at previously: each node has a pointer only to its next neighbor. It supports:

O(1) insertion/removal at head (prepend/removeHead)
O(1) insertion at tail if you maintain a tail pointer (append)
O(N) removal at tail or arbitrary index (must traverse)
O(N) search/traversal

Skeleton Code

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

class SinglyLinkedList {
  constructor() {
    this.head   = null;
    this.tail   = null;
    this.length = 0;
  }

  prepend(value) { /* … O(1) … */ }
  append(value)  { /* … O(1) … */ }
  removeHead()   { /* … O(1) … */ }
  removeTail()   { /* … O(N) … */ }
  find(val)      { /* … O(N) … */ }
  // etc.
}

2. Doubly Linked List (DLL)

A doubly linked list augments each node with a prev pointer so you can move backward as well as forward. This extra pointer costs memory (an extra reference per node) but gives you:

O(1) insertion/removal at both head and tail (no need to traverse)
O(1) removal of a known node (you have direct node.prev and node.next)
O(N) search/traversal (still linear if you don’t know the node)

Skeleton Code

class DNode {
  constructor(value) {
    this.value = value;
    this.next  = null;
    this.prev  = null;
  }
}

class DoublyLinkedList {
  constructor() {
    this.head   = null;
    this.tail   = null;
    this.length = 0;
  }

  prepend(value) {
    const node = new DNode(value);
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      node.next       = this.head;
      this.head.prev  = node;
      this.head       = node;
    }
    this.length++;
  }

  append(value) {
    const node = new DNode(value);
    if (!this.tail) {
      this.head = this.tail = node;
    } else {
      this.tail.next = node;
      node.prev      = this.tail;
      this.tail      = node;
    }
    this.length++;
  }

  remove(node) {
    if (!node) return null;
    if (node.prev) node.prev.next = node.next;
    else            this.head      = node.next;
    if (node.next) node.next.prev = node.prev;
    else            this.tail      = node.prev;
    this.length--;
    return node.value;
  }

  // removeHead(), removeTail(), find(), etc.
}

Space vs. Time:

Space Overhead: +1 pointer per node (prev)
Faster Deletes: remove an arbitrary node in O(1) once you have a reference to it.

3. Circular Linked List (CLL)

A circular linked list “loops back” by having its tail’s next point to the head, forming a circle. You can implement this on top of either a singly or doubly structure.

3.1. Singly Circular

tail.next → head
No null terminator: every node has a successor.
Handy for round-robin scheduling, or when you want to start anywhere and traverse “forever.”

Key operations remain the same complexities as a singly list, but you must be careful to stop when you’ve come full circle.

Skeleton Code (Singly Circular)

class SinglyCircularList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  append(value) {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
      this.tail = node;
      node.next = node;       // points to itself
    } else {
      node.next      = this.head;
      this.tail.next = node;
      this.tail      = node;
    }
    this.length++;
  }

  traverse(callback) {
    if (!this.head) return;
    let curr = this.head;
    do {
      callback(curr.value);
      curr = curr.next;
    } while (curr !== this.head);
  }

  // Removing/inserting at head or tail is still O(1),
  // but watch your loop-termination conditions!
}

3.2. Doubly Circular

Combines the benefits of DLL (bi-directional) and CLL (no null ends).
prev and next pointers, and tail.next = head, head.prev = tail.

Skeleton Code (Doubly Circular)

class DNode {
  constructor(value) {
    this.value = value;
    this.next  = null;
    this.prev  = null;
  }
}

class DoublyCircularList {
  constructor() {
    this.head   = null;
    this.length = 0;
  }

  append(value) {
    const node = new DNode(value);
    if (!this.head) {
      node.next = node.prev = node;
      this.head = node;
    } else {
      const tail = this.head.prev;
      tail.next    = node;
      node.prev    = tail;
      node.next    = this.head;
      this.head.prev = node;
    }
    this.length++;
  }

  // prepend, remove, traverse etc. follow similar patterns,
  // just mind the circular pointers.
}

Why choose circular?

Useful when you need wrap-around traversal without extra checks.
No null pointers can simplify some algorithms but requires careful loop guards.

Summary of Time Complexities

Operation	Singly SLL	Doubly DLL	Singly CLL	Doubly CLL
Insert at head	O(1)	O(1)	O(1)	O(1)
Insert at tail	O(1)*	O(1)	O(1)*	O(1)
Remove head	O(1)	O(1)	O(1)	O(1)
Remove tail	O(N)	O(1)	O(N)	O(1)
Remove given node	O(N)	O(1)	O(N)	O(1)
Search (find value)	O(N)	O(N)	O(N)	O(N)

* Singly tail ops assume you keep a tail pointer; removal still requires O(N) unless you have a prev pointer.

Tip: Choose the simplest structure that meets your needs—extra pointers cost memory, extra checks cost code complexity. Singly lists are often enough; use doubly or circular variants when you really need bi-directional traversal or seamless wrap-around.