Types of Linked List

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Types of Linked List: Singly, Doubly, Circular

Three variations, each trading a bit of memory for a bit of extra capability.

🔗 The Three Types

Singly linkedEach node points only to the NEXT node. Simplest, least memory per node, but can only traverse forward.

Doubly linkedEach node points to BOTH the next AND previous node — allows backward traversal, at the cost of an extra pointer per node.

CircularThe last node points back to the FIRST node instead of to null — useful for anything that naturally cycles (like a round-robin scheduler).

💡 One-liner: "Give one real use case for a circular linked list." → A round-robin CPU scheduler, or a repeating playlist — anything that naturally cycles back to the beginning.

What the extra pointer buys, and what it costs

A doubly linked list stores one extra pointer per node — a real memory cost that on small payloads can approach the size of the data itself. In exchange it enables backward traversal and, more importantly, O(1) deletion given only the node to delete, since the previous node is directly reachable.

That deletion property is why doubly linked lists appear inside operating systems and caches. An LRU cache must move an arbitrary entry to the front on every access; with a singly linked list that requires an O(n) search for the predecessor, which would defeat the purpose of the cache entirely.

💡 The circular variant removes the special case rather than adding capability: with no null terminator, "advance to the next item" is the same operation everywhere, and a round-robin scheduler needs no wrap-around check. Fewer special cases means fewer bugs — the usual reason to choose it.

The traversal hazard

A circular list has no natural end, so the loop condition that works on a singly linked list — stop at null — never triggers and the traversal spins forever. Iteration must instead stop on returning to the starting node.

The same absence of a terminator makes cycle detection a real problem on ordinary lists, where a cycle is a bug rather than a design: Floyd's two-pointer method, advancing one pointer by one node and another by two, detects it in O(n) time and O(1) space.

Syllabus points

Singly linked list
Doubly linked list
Circular linked list

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.