Doubly and Circular Linked Lists Explained: Operations, Worked Examples and GATE Traps
Trace insertion and deletion across three linked-list variants, then check your understanding with Josephus, complexity comparisons and rapid pointer questions.
KnowledgeGate Team
Exam prep & CS education

The diagram looks simple, but one wrong prev, a missed head update, or a NULL-based circular loop changes the answer. Reliable solutions preserve each variant's pointer invariant, trace named addresses, and verify loop termination after each mutation. Use GATE CS Exam Preparation as the broader preparation hub.
1. Linked-list variants begin with their end invariant
A linear singly linked node stores (data,next). head names the first node; the last has next=NULL. Variants change links or the meaning of the end.
Variant | Node fields | End invariant |
|---|---|---|
Linear doubly linked |
|
|
Circular singly linked |
|
|
Circular doubly linked |
|
|
An empty list uses head=NULL or tail=NULL. A one-node circular singly list has tail.next=tail. A one-node circular doubly list has head.next=head and head.prev=head.
A second link enables backward movement and constant-time deletion of a known node. Circularity replaces a NULL end with a return to the start. Neither gives constant-time indexed access. A header or sentinel simplifies boundaries but is not user data. See C Programming and Data Structures for the wider subject map.
2. Worked doubly linked list insertion and deletion with exact pointers
Start with three nodes:
Address |
|
|
|
|---|---|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
Here head=1000 and tail=1080. Traversal gives 10,20,40 forward and 40,20,10 backward.
Insert node N at 1060, with data 30, between 1040 and 1080:
N.prev=1040N.next=10801040.next=10601080.prev=1060
The result has 1060=(prev=1040,data=30,next=1080), 1040.next=1060, and 1080.prev=1060. Traversals are 10,20,30,40 and 40,30,20,10.
Delete 1040. Save victim=1040, left=1000, and right=1060. Set left.next=right, set right.prev=left, then free victim. The final records have 1000.next=1060 and 1060.prev=1000; traversals are 10,30,40 and 40,30,10.
Mutation is O(1) only after the position or node is known. Searching for 20 remains O(n). Review Pointers in C for GATE for the memory prerequisite.

3. Worked circular singly linked list using one tail pointer
Let tail=3300. Address 3100 stores 10 and points to 3200; 3200 stores 20 and points to 3300; 3300 stores 30 and points to 3100. Thus head=tail.next=3100. One traversal is 10,20,30, then back to 10.
Append 3400, storing 40, in three steps. Set 3400.next=tail.next, which is 3100; set old tail.next=3400; then set tail=3400. The ring is 10 -> 20 -> 30 -> 40 -> 10. A tail pointer makes append O(1).
To delete the head, save oldHead=tail.next=3100, set tail.next=oldHead.next=3200, then free 3100. The remaining traversal is 20,30,40, then back to 20. tail remains 3400, and the new head is 3200.
Traversal must stop on returning to its saved start address 3200:
Node *start = tail->next; /* address 3200 */
Node *p = start;
do {
visit(p);
p = p->next;
} while (p != start);The test p != NULL never terminates on a valid ring. For singleton deletion, when tail.next==tail, free that node and set tail=NULL.
4. Worked circular doubly linked list in both directions
Start with this ring:
2100=(prev=2300,data=5,next=2200)2200=(prev=2100,data=15,next=2300)2300=(prev=2200,data=25,next=2100)
Set head=2100, so tail=head.prev=2300. Values are 5,15,25 clockwise and 25,15,5 anticlockwise from the tail.
Insert 2250, storing 20, before tail 2300. Set 2250.prev=2200; 2250.next=2300; 2200.next=2250; and 2300.prev=2250. Traversals are 5,15,20,25 clockwise and 25,20,15,5 anticlockwise.
Next, delete 2200. Its predecessor is 2100, and its successor is 2250. Set 2100.next=2250, then 2250.prev=2100. Only then free 2200. The final ring is 5,20,25 clockwise and 25,20,5 anticlockwise.
Check the end invariant after each mutation: 2100.prev=2300 makes head.prev=tail, while 2300.next=2100 makes tail.next=head. No link is NULL in a valid, non-empty circular doubly list.

5. Circular-list application: solve Josephus with seven people
Take n=7 and k=3. People 1 through 7 form a circle. Counting starts at 1, every third remaining person is removed, and counting resumes at the next survivor.
From
[1,2,3,4,5,6,7], count1,2,3and remove3.Resume with
[4,5,6,7,1,2], count4,5,6and remove6.Resume with
[7,1,2,4,5], count7,1,2and remove2.Resume with
[4,5,7,1], count4,5,7and remove7.Resume with
[1,4,5], count1,4,5and remove5.Resume with
[1,4], count1,4,1and remove1.
The elimination order is 3,6,2,7,5,1, leaving survivor 4.
Check independently with the zero-based recurrence J(1)=0 and J(n)=(J(n-1)+3) mod n. The sequence J(1)..J(7) is 0,1,1,0,3,0,3. The final zero-based position 3 corresponds to one-based person 4.
A circular list models continuation because deletion can hand control to the removed node's successor. However, the recurrence solves this fixed-step problem without constructing a list, so a list is not always the fastest implementation.
6. Complexity and representation choices with explicit assumptions
Assume linear doubly has head,tail; circular singly has tail; circular doubly has head.
Property | Linear doubly | Circular singly, | Circular doubly, |
|---|---|---|---|
Node links |
|
|
|
End | Two |
|
|
Forward traversal |
|
|
|
Backward traversal |
| Unsupported |
|
Front insert |
|
|
|
Append |
|
|
|
Delete head |
|
|
|
Delete known node |
|
|
|
Delete tail |
|
|
|
Value search |
|
|
|
Extra link | One | None | One |
For n=6, traversal visits six nodes in each variant. Circularity changes stopping, not O(n). Search then deletion is O(n)+O(1)=O(n). Linked representations support deque-like updates without changing ADT rules. Compare Stacks and Queues: Operations and Uses.
7. Exam-style question patterns and the traps behind wrong answers
Questions ask you to identify structures from end links, compute pointer assignments, fill in missing pointer updates, trace both directions, calculate complexity under stated pointers, handle empty or singleton lists, or test loop termination. You may also judge whether an invariant survives.
Watch for these traps:
Linear doubly has
tail.next=NULL; circular doubly hastail.next=head.Overwriting
current.nextbefore saving its old successor can lose the remaining nodes.Read a victim's neighbours before freeing it.
Deletion by value is
O(1)only when the node is known. Otherwise, search costsO(n).After singleton deletion, the external pointer must become
NULL, not point to freed storage.
Rapid checks: after doubly insertion, 1080.prev=1060; after circular singly head deletion, tail.next=3200; for n=7,k=3, survivor 4.
8. The short version and the next deliberate step
Use an invariant-first method: write the node fields, mark head and tail, state empty and singleton cases, save neighbours before rewiring, update both directions where present, then verify one complete traversal. Carefully redraw the final 1000,1060,1080 doubly list and the 3200,3300,3400 circular ring from memory. Your two checks are 1000.next=1060 and 3400.next=3200. For a structured route through data structures and the wider syllabus, continue with GATE Guidance by Sanchit Sir.
Keep learning
Doubly and Circular Linked List MCQs: 12 Solved Questions
Solve 12 published MCQs on circular, doubly and XOR linked lists. Each answer explains the invariant, pointer operation or complexity argument behind it.
Queue Data Structure: Operations, Circular Queues and Worked Examples for GATE
Learn queue operations through a five-slot circular queue trace, then connect the same FIFO rule to linked lists, BFS and the two-stack implementation.
Stack and Queue Implementation in Java: Arrays, Linked Lists, and the Interview Problems That Use Them
Implement stacks and circular queues in Java, trace every pointer through wrap-around, and choose the right standard collection for real code.
Linked Lists and Trees in Python from Scratch: Node Classes, Traversals, and Interview Problems
Build linked lists and binary search trees with plain Python objects, then trace reversal, insertion, and traversal patterns that interviews repeatedly test.





