Linked Lists: Singly, Doubly and Circular, with Insertion and Deletion

Static vs dynamic lists

A list is an ordered collection of elements.

• Static list (array): fixed size, contiguous memory, O(1) access to any element; inserting or deleting in the middle requires shifting elements, O(n).
• Dynamic list (linked list): nodes are allocated as needed and linked by pointers; the size changes freely; inserting or deleting at a known place is O(1), but finding an element takes O(n).

Singly linked list

Each node holds the data and a pointer to the next node. A pointer called head (or start) points to the first node; the last node's next is NULL.

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

head -> [10|*] -> [20|*] -> [30|NULL]

Traversal

void display(void) {
    for (struct node *p = head; p != NULL; p = p->next)
        printf("%d ", p->data);
}

Insert at the beginning, O(1)

void insertFirst(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x;
    n->next = head;
    head = n;
}

Insert at the end, O(n)

void insertLast(int x) {
    struct node *n = malloc(sizeof *n);
    n->data = x;
    n->next = NULL;
    if (head == NULL) { head = n; return; }
    struct node *p = head;
    while (p->next != NULL) p = p->next;
    p->next = n;
}

Insert after a given node

Create the new node n; set n->next = p->next, then p->next = n. The order matters: doing it the other way round loses the rest of the list.

Delete the first node

void deleteFirst(void) {
    if (head == NULL) return;
    struct node *t = head;
    head = head->next;
    free(t);
}

Delete a node with a given value

Find the node before it (p), then set p->next = p->next->next and free the removed node.

Doubly linked list

Each node has two pointers: prev and next.

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

NULL <- [10] <-> [20] <-> [30] -> NULL

Advantages: it can be traversed in both directions, and a node can be deleted when you only have a pointer to it (O(1)), because its previous node is known. The cost is extra memory for prev and more pointer updates.

Deleting node p: p->prev->next = p->next; and p->next->prev = p->prev; (checking for NULL at the ends).

Circular linked list

The last node points back to the first node instead of NULL. Traversal stops when it returns to the start:

struct node *p = head;
if (p) do { printf("%d ", p->data); p = p->next; } while (p != head);

It is useful for round-robin scheduling and circular buffers. Keeping a pointer to the last node gives O(1) insertion at both the beginning and the end.

Linked stack and linked queue

• Stack: push and pop at the head.
• Queue: keep front and rear pointers; enqueue at the rear, dequeue at the front. Both are O(1).

Array vs linked list

Exam tip

Always draw the pointer diagram before and after an insertion or deletion, and write the steps in the right order. Most wrong answers set p->next = n before saving the old p->next.