Linked List in DSA: Singly, Doubly & Circular with Code

A linked list in DSA is a dynamic linear data structure where each element, called a node, stores data and one or more links to other nodes. It matters because insertions, deletions, queues, undo systems, memory allocators, and graph adjacency lists often need flexible storage without shifting large arrays.

Linked lists sit between arrays and pointer-heavy structures such as trees and graphs. Intermediate learners use them to master references, mutation, edge cases, and algorithmic invariants; advanced learners use them to reason about cache locality, memory overhead, concurrency, and low-level systems design.

After reading, you should be able to implement singly linked list, doubly linked list, circular linked list, and circular doubly linked list operations, analyse their complexity, avoid common bugs, and answer placement or GATE-style questions confidently.

Core Concepts

A linked list in data structure design is built from nodes, links, and a small set of operations: traversal, insertion, deletion, search, reversal, and cycle handling. The important variants differ mainly in how many links each node stores and whether the last node connects back to the first node.

1.Node Structure

A node is the smallest unit of a linked list. In a singly linked list, a node stores data and a reference to the next node. In a doubly linked list, it also stores a reference to the previous node. This makes nodes more flexible than array cells, but also more error-prone because a wrong reference can break the entire chain.

Think of an Aadhaar update workflow where each status points to the next status: submitted, verified, processed, completed. That is a familiar one-way sequence. In healthcare software, a patient monitoring timeline may connect readings in order so that a doctor can traverse event history without moving large blocks of memory.

A linked list does not provide constant-time random access. Accessing the nth node takes O(n) time because traversal must start from head or tail depending on the variant.

Code Example

2.Singly Linked List

A singly linked list is the simplest linked list type. Each node points only to the next node, so traversal is naturally forward-only. It is memory-efficient compared with a doubly linked list because it stores one link per node, but deleting a node often requires access to the previous node.

For a familiar Indian example, an IRCTC booking confirmation flow can be represented as a one-way sequence: selected train, passenger details, payment, ticket generation. In e-commerce, a lightweight order-processing pipeline can use a singly linked list when each stage only needs to hand work to the next stage.

Insertion at the head is O(1). Insertion at the tail is O(1) only if a tail pointer is maintained; otherwise it is O(n). Search is O(n), deletion by value is O(n), and traversal is O(n). This makes a singly linked list useful for sequential processing, not random indexing.

Standard GATE and interview question: What is the time complexity of inserting a node at the beginning of a singly linked list? The answer is O(1), because only the new node next and head pointer change.

Code Example

3.Doubly Linked List

A doubly linked list stores two references in every node: previous and next. This supports forward and backward traversal, and deletion becomes easier when the node reference is already available. The trade-off is extra memory and more pointer updates on every insertion or deletion.

A familiar example is browser navigation: after opening pages in sequence, the back and forward buttons need movement in both directions. In SaaS products, an undo-redo stack for a design editor or document workflow can use a doubly linked structure to move across user actions efficiently.

Because both directions are available, LRU cache implementations often combine a doubly linked list with a hash map. The hash map finds a node in O(1), and the list moves recently used items to the front in O(1). For a deeper treatment of pointer updates, see A Detailed walkthrough of the Doubly Linked List.

The most common doubly linked list bug is updating only one side. When deleting a middle node, both node.prev.next and node.next.prev must be repaired, otherwise forward and backward traversals disagree.

Code Example

4.Circular Singly List

A circular singly linked list is a singly linked list where the last node points back to the head instead of None. This creates a loop, so traversal must stop using a condition such as returning to head, not by waiting for None. It is ideal when processing must repeatedly cycle through participants, tasks, or turns.

A familiar example is token rotation in a small UPI dispute-review team where the next available reviewer is selected in a repeating order. In operating systems, round-robin CPU scheduling uses the same idea: each process gets a time slice, then the pointer moves to the next process and eventually returns to the first.

The key advantage is O(1) movement from tail to head. If a tail pointer is maintained, appending is also O(1) because the new tail can point directly to head. The key risk is infinite traversal when the stopping condition is wrong.

Standard question: How do you detect completion of one traversal in a circular linked list? Start at head, move at least once, and stop when the current pointer becomes head again.

Code Example

5.Circular Doubly List

A circular doubly linked list combines two features: every node has previous and next links, and the tail connects to the head while the head connects back to the tail. This makes movement possible in both directions without hitting None.

A familiar example is a music playlist where pressing next after the last song returns to the first song, and pressing previous from the first song returns to the last song. In warehouse automation, a rotating carousel of bins can be modelled similarly because the picker can move clockwise or anticlockwise.

This structure is powerful for deques, schedulers, and UI carousels, but insertion and deletion must update four references in common cases. Circular doubly lists are also popular for implementing intrusive lists in systems programming, where list links are stored inside the objects themselves.

In a circular doubly linked list, an empty list has no head, and a one-node list points to itself in both directions. Many bugs happen because the one-node case is treated like a normal middle-node case.

Code Example

6.Sentinel Linked List

A sentinel linked list uses a dummy node that does not store real business data. The sentinel sits before the first real node, or in circular designs it can represent both beginning and end. This reduces special cases because insertions and deletions can treat the area after sentinel uniformly.

A familiar example is a banking mini-statement where a dummy header can anchor transaction nodes even when there are no transactions for the month. In an e-commerce cart, a sentinel node can simplify adding and removing items without repeatedly checking whether the cart is empty.

Sentinel nodes are not required, but they are useful in production code and interviews because they make boundary logic clearer. Many linked list problems become shorter when a dummy head is used before operations such as deleting all matching nodes or merging two sorted lists.

A dummy head is an implementation technique, not a separate data structure category in most textbooks. It is especially useful when the real head might change during deletion or merging.

Code Example

7.Advanced Variants

Three less common variants appear in advanced interviews and systems discussions: XOR linked lists, unrolled linked lists, and skip lists. An XOR linked list stores a compressed address relationship instead of two separate links, which is mainly relevant in low-level languages with manual memory access. It is rarely used in application code because garbage-collected languages do not expose stable raw addresses safely.

An unrolled linked list stores multiple elements inside each node, improving cache behaviour and reducing per-element pointer overhead. A skip list keeps multiple forward layers so search, insertion, and deletion take expected O(log n) time, making it a probabilistic alternative to balanced trees.

A familiar analogy is a metro route map: the local train stops at every station, while the express layer skips many stations. In industry, ordered indexes in databases or SaaS feature-flag stores may use skip-list-like ideas to find keys faster than a plain linear linked list.

If asked whether a skip list is just a linked list, answer carefully: it is a layered linked structure with probabilistic balancing. Expected search time is O(log n), while a normal singly linked list search is O(n).

Code Example

Choose the linked list variant from the required movement pattern: one-way uses singly, two-way uses doubly, repeated cycles use circular, and boundary-heavy operations often become cleaner with a sentinel node.

Operations and Complexity

Linked list performance depends on what pointer you already have. Inserting at head is constant time, but finding the insertion position is linear. Deleting a known node in a doubly linked list is O(1), while deleting by value still requires O(n) search.

Reverse a List

Reversal is one of the most tested linked list operations because it checks whether you can maintain references without losing the remaining chain. The safe mental model uses three references: previous, current, and next_node. Store the next node before changing current.next, then move all three references forward.

A familiar example is reversing a queue of customer-support tickets for audit playback. In banking reconciliation, transaction events might be stored oldest to newest, but an investigation view may need newest to oldest without rebuilding an array first.

Never overwrite current.next before saving it. If the next reference is lost, the rest of the linked list becomes unreachable.

Code Example

Detect a Cycle

Cycle detection identifies whether following next references eventually loops instead of reaching None. Floyd’s tortoise and hare algorithm uses two pointers: slow moves one step, fast moves two steps. If a cycle exists, the two pointers eventually meet.

A familiar example is a mistaken approval workflow where a PAN verification step points back to document upload forever. In distributed job orchestration, a bad dependency graph may create a repeated chain of tasks that never completes.

Floyd cycle detection uses O(n) time and O(1) extra space. This is preferred over a visited-set solution when the interviewer asks for constant auxiliary space.

Code Example

Common Pitfalls

Most linked list bugs are not caused by syntax; they come from broken invariants. Before and after every operation, ask whether head is valid, tail is valid, all next references are reachable, and all prev references agree with next references in a doubly linked list.

  • Forgetting the empty list case: Insert and delete functions must handle head as None.
  • Breaking the chain during reversal: Save the next node before changing current.next.
  • Ignoring tail updates: When deleting the last node, tail must move to the previous node or become None.
  • Using None as circular traversal stop: Circular linked lists do not naturally end at None.
  • Updating only one pointer in doubly lists: Both neighbouring nodes must be repaired.
  • Assuming linked lists are always faster than arrays: Arrays often perform better for indexing and cache locality.
Arrays usually have better cache locality because elements are stored contiguously. Linked lists are chosen for flexible insertion and deletion patterns, not for fast indexed lookup.

Learning Path

Use this path to move from implementation basics to interview-ready problem solving. Write code by hand first, then run it, then dry-run pointer changes on paper.

Frequently Asked Questions

What is a linked list in DSA?

A linked list in DSA is a linear data structure made of nodes connected through references or pointers. Unlike arrays, nodes do not need to be stored in contiguous memory, which makes insertion and deletion flexible but indexed access slower.

What is the difference between array and linked list?

An array stores elements contiguously and supports O(1) access by index. A linked list stores elements as connected nodes and needs O(n) traversal for indexed access. Linked lists are better when frequent insertions and deletions happen at known positions.

What is the difference between singly and doubly linked list?

A singly linked list stores only a next reference, so it supports forward traversal. A doubly linked list stores both previous and next references, so it supports movement in both directions. The doubly linked list uses more memory but simplifies deletion when the node reference is known.

When should I use a circular linked list?

Use a circular linked list when processing naturally repeats, such as round-robin scheduling, rotating reviewers, playlists, or cyclic queues. It avoids manually jumping from tail to head, but traversal must use a safe stopping condition to avoid infinite loops.

How do you implement insertion in a linked list?

Insertion requires creating a node and rewiring references. At the head, the new node points to the old head and then head changes to the new node. At the tail, using a tail pointer makes insertion O(1); without it, traversal to the last node takes O(n).

Why is linked list deletion sometimes O(1) and sometimes O(n)?

Deletion is O(1) only when the required node and its neighbour information are already available. If you must search for the node by value, the search takes O(n). In a singly linked list, deleting a known node may still need the previous node unless special techniques are used.

What is the most common linked list mistake?

The most common mistake is losing a reference before rewiring pointers. During reversal, deletion, or insertion, save the next node before changing links. Also handle empty lists, one-node lists, and head or tail changes separately.

Is linked list faster than array?

Not always. Linked lists can be faster for insertion or deletion when the position is already known, but arrays are usually faster for indexing and sequential scans because of cache locality. The correct choice depends on the operation pattern.

Key Takeaways

The most important points are concrete: a singly linked list is memory-light and forward-only; a doubly linked list supports two-way movement with extra memory; a circular linked list connects tail back to head; and sentinel nodes reduce boundary-condition bugs. Indexed access remains O(n) across normal linked list variants.

For GATE and interviews, revise insertion at head, deletion edge cases, reversal using three pointers, Floyd cycle detection, and slow-fast pointer problems. Be ready to state exactly when an operation is O(1) and when it becomes O(n) because traversal is required.

The natural next step is A Quick Guide to Circular Linked List in C++, especially if you want to compare Python reference-based implementation with pointer-style circular linked list code.

DSA DSA Fundamentals Linkedlist Singly Linkedlist Doubly LInkedlist