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.prevandnode.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
nullterminator: 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
nullends). - 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
nullpointers 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.
التالي · الدرس 23 من 92
Linked List Operations (Insertion, Deletion, Traversal)
قراءة 2 دقيقة
أنهيت 22 من 92 درسًا

اسأل Byte عن هذا الدرس
محادثة خاصة حول هذا الدرس. قرأ Byte الدرس كاملًا، ويجيب خلال ثوانٍ، ويُظهر القسم الذي تأتي منه كل إجابة. يمكنك السؤال بأي لغة.
الأسئلة والأجوبة
أسئلة عامة حول هذا الدرس. يجيب AI Tutor فورًا بلغتك، ويراجع فريق FreeAcademy الإجابات، ويمكن لكل المتعلمين قراءتها.

