Doubly and circular linked lists; operation costs compared with arrays

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• In iterative list reversal, what is returned as the new head? from Lesson 3.4.2
• Queue from two stacks: what is the amortized cost per operation? from Lesson 3.3.3
• What does inserting at index 0 of an n-element array cost, and why? from Lesson 3.1

1 · The Hook

🎣

A metro train can be driven from either end: the driver walks to the other cab and goes back the way she came. A ring road has no end at all: keep driving and you return to the start. Linked lists come in both shapes, and each shape makes some operations cheaper.

2 · Predict First

🤔

In a singly linked list you are given a pointer to a node in the middle (not the head). Can you delete that node in O(1)? What changes if every node also points to its previous node? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Singly linked: no, because the previous node’s next must change and you cannot find the previous node without walking from the head (O(n)). With a prev pointer, the neighbours are at hand: delete in O(1).

Doubly linked list

Each node has prev and next. You can walk both ways, and delete or insert next to a given node in O(1). The cost: one more pointer per node and twice as many pointer updates.

struct dnode {
    int data;
    struct dnode *prev, *next;
};

struct dnode *dnew(int x)
{
    struct dnode *n = malloc(sizeof(struct dnode));
    n->data = x;
    n->prev = n->next = NULL;
    return n;
}

void insertAfterD(struct dnode *p, int x)       /* 4 pointer updates */
{
    struct dnode *n = dnew(x);
    n->prev = p;
    n->next = p->next;
    if (p->next != NULL) p->next->prev = n;
    p->next = n;
}

void removeD(struct dnode **head, struct dnode *p)  /* no search for the previous node */
{
    if (p->prev != NULL) p->prev->next = p->next; else *head = p->next;
    if (p->next != NULL) p->next->prev = p->prev;
    free(p);
}

int main(void)
{
    struct dnode *head = dnew(1), *tail, *p;
    insertAfterD(head, 3);
    insertAfterD(head, 2);
    tail = head->next->next;
    insertAfterD(tail, 4);
    tail = tail->next;
    removeD(&head, head->next);             /* remove 2 */
    for (p = head; p != NULL; p = p->next) printf("%d ", p->data);
    printf("| backwards: ");
    for (p = tail; p != NULL; p = p->prev) printf("%d ", p->data);
    printf("\n");
    return 0;
}

Output

1 3 4 | backwards: 4 3 1

Inserting after p updates four pointers (n->prev, n->next, p->next->prev, p->next); deleting p updates two (its neighbours’ links), with care at the ends.

Circular singly linked list

The last node’s next points back to the first. There is no NULL, so a traversal must stop when it returns to its start (use do-while). Keeping a pointer to the last node gives O(1) access to both ends (first = last->next): useful for round-robin scheduling and queues.

int main(void)
{
    int a[] = {7, 14, 21, 28};
    struct node *head = build(a, 4), *last = head, *p;
    while (last->next != NULL) last = last->next;
    last->next = head;                     /* make it circular */
    p = head;
    do {                                   /* visit each node once */
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
    printf("| after last: %d\n", last->next->data);
    return 0;
}

Output

7 14 21 28 | after last: 7

Circular doubly linked list

Combine both: first->prev is the last node and last->next is the first. Often built with a sentinel (dummy header) node so that the list is never truly empty and insertions need no special cases.

Costs compared

4 · Visual

The doubly linked list after the program: arrows both ways; head->prev and tail->next are NULL.

Circular singly linked list: the last node points back to the first.

Insert x after p in a doubly linked list (p <-> q):

   p <----> q            n = new node
   n->prev = p           p <- n
   n->next = q           p <- n -> q
   q->prev = n           p <- n <-> q
   p->next = n           p <-> n <-> q        (4 pointer writes)

Doubly linked insertion touches four pointers.

5 · Worked Examples

Example 1 Easy

What does this print?

int main(void)
{
    int a[] = {7, 14, 21, 28};
    struct node *head = build(a, 4), *last = head, *p;
    while (last->next != NULL) last = last->next;
    last->next = head;                     /* make it circular */
    p = head;
    do {                                   /* visit each node once */
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
    printf("| after last: %d\n", last->next->data);
    return 0;
}

Solution

The do-while prints each node once and stops when p returns to head. last->next is the first node, 7.

Output

7 14 21 28 | after last: 7

Example 2 Medium

How many pointer fields change when a node is inserted between two existing nodes of a doubly linked list? When it is deleted from between two nodes?

Solution

Insert: 4 (two in the new node, one in each neighbour). Delete: 2 (the previous node’s next and the next node’s prev).

Example 3 GATE

Which list type makes all of these O(1): insert at front, insert at end, delete at front, delete at end?

Solution

A doubly linked list with head and tail pointers (or a circular doubly linked list). A singly linked list with a tail pointer still needs O(n) to delete the last node, because the new last node must be found.

6 · GATE Traps

⚠️

• Doubly linked insertion needs 4 pointer updates; forgetting q->prev is the classic bug.
• Deleting the last node of a singly linked list is O(n) even with a tail pointer.
• Traversing a circular list with while (p != NULL) never ends; stop at the start node.
• In a circular list, the last node’s next is the head; keeping a last pointer gives both ends.
• Check the ends: prev of the first node and next of the last node are NULL in a non-circular doubly linked list.

8 · Memory Hook

🧠

“Two cabs, one ring.” A doubly linked list is a train with a cab at each end; a circular list is the ring road with no last exit.

9 · Connect the Dots

Lessons 3.2 and 3.3 built stacks and queues on arrays with fixed capacity. Linked lists grow without a limit and insert at the ends in O(1). Next lesson answers: how are a stack and a queue built from linked nodes, and which end of the list should each operation use?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markDoubly

Given a pointer to a node in a doubly linked list, deleting it costs:

• (A) O(log n)
• (B) O(1)
• (C) O(n²)
• (D) O(n)

Q2NAT1 markPointers

How many pointer fields are written when a new node is inserted between two nodes of a doubly linked list?

Numerical answer: ________

Q3MCQ2 marksOutput

What does this print?

struct dnode {
    int data;
    struct dnode *prev, *next;
};

struct dnode *dnew(int x)
{
    struct dnode *n = malloc(sizeof(struct dnode));
    n->data = x;
    n->prev = n->next = NULL;
    return n;
}

void insertAfterD(struct dnode *p, int x)       /* 4 pointer updates */
{
    struct dnode *n = dnew(x);
    n->prev = p;
    n->next = p->next;
    if (p->next != NULL) p->next->prev = n;
    p->next = n;
}

void removeD(struct dnode **head, struct dnode *p)  /* no search for the previous node */
{
    if (p->prev != NULL) p->prev->next = p->next; else *head = p->next;
    if (p->next != NULL) p->next->prev = p->prev;
    free(p);
}

int main(void)
{
    struct dnode *head = dnew(1), *tail, *p;
    insertAfterD(head, 3);
    insertAfterD(head, 2);
    tail = head->next->next;
    insertAfterD(tail, 4);
    tail = tail->next;
    removeD(&head, head->next);             /* remove 2 */
    for (p = head; p != NULL; p = p->next) printf("%d ", p->data);
    printf("| backwards: ");
    for (p = tail; p != NULL; p = p->prev) printf("%d ", p->data);
    printf("\n");
    return 0;
}

• (A) 1 2 3 4 | backwards: 4 3 2 1
• (B) 1 3 4 | backwards: 4 3 1
• (C) 1 3 4 | backwards: 4 3
• (D) 1 4 3 | backwards: 3 4 1

Q4MCQ1 markCircular

In a circular singly linked list with a pointer last to the last node, the first node is:

• (A) last
• (B) last->next
• (C) last->prev
• (D) NULL

Q5MSQ2 marksCosts

For a singly linked list with head and tail pointers, which are O(1)?

• (A) insert at end
• (B) delete at front
• (C) delete at end
• (D) insert at front

11 · Rule Card

• Doubly linked: prev + next; delete/insert beside a known node O(1); 4 writes to insert, 2 to delete.
• Circular: last->next = head; traverse with do-while until back at the start.
• A last pointer on a circular list gives O(1) access to both ends.
• Singly linked + tail: insert at end O(1), delete at end O(n).
• Price of doubly linked: one more pointer per node.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

doubly linked listprev pointercircular linked listcircular doubly linked listsentinel (dummy header) node

13 · Answer Vault