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

Updated 2 Nov 20265 min read
Doubly and Circular Linked Lists Explained: Operations, Worked Examples and GATE Traps

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

(prev,data,next)

head.prev=NULL, tail.next=NULL

Circular singly linked

(data,next)

tail.next=head

Circular doubly linked

(prev,data,next)

head.prev=tail, tail.next=head

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

prev

data

next

1000

NULL

10

1040

1040

1000

20

1080

1080

1040

40

NULL

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:

  1. N.prev=1040

  2. N.next=1080

  3. 1040.next=1060

  4. 1080.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.

Three panels tracing a doubly linked list at addresses 1000, 1040 and 1080 as node 1060 is inserted and node 1040 is deleted.

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:

c
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.

Circular singly list from address 3200 to 3400 after head deletion, beside the final circular doubly ring holding 5, 20 and 25.

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], count 1,2,3 and remove 3.

  • Resume with [4,5,6,7,1,2], count 4,5,6 and remove 6.

  • Resume with [7,1,2,4,5], count 7,1,2 and remove 2.

  • Resume with [4,5,7,1], count 4,5,7 and remove 7.

  • Resume with [1,4,5], count 1,4,5 and remove 5.

  • Resume with [1,4], count 1,4,1 and remove 1.

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, tail

Circular doubly, head

Node links

prev, next

next

prev, next

End

Two NULL links

tail.next=head

head.prev=tail, tail.next=head

Forward traversal

O(n)

O(n)

O(n)

Backward traversal

O(n)

Unsupported

O(n)

Front insert

O(1)

O(1)

O(1)

Append

O(1)

O(1)

O(1)

Delete head

O(1)

O(1)

O(1)

Delete known node

O(1)

O(n) without predecessor

O(1)

Delete tail

O(1)

O(n)

O(1)

Value search

O(n)

O(n)

O(n)

Extra link

One prev

None

One prev

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:

  1. Linear doubly has tail.next=NULL; circular doubly has tail.next=head.

  2. Overwriting current.next before saving its old successor can lose the remaining nodes.

  3. Read a victim's neighbours before freeing it.

  4. Deletion by value is O(1) only when the node is known. Otherwise, search costs O(n).

  5. 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.