Master Linked Lists in C: From Arrays to Circular Lists

Sequential Storage vs. Linked Storage

Arrays store elements contiguously, which makes random access fast but causes costly element shifting during insertions and deletions. An example shows how inserting {1,2,3,4} after the first element requires moving existing elements and then overwriting the target position.

Insert requires moving many elements, wasting CPU cycles.

Array size must be pre‑allocated to avoid overflow.

Linked List – Linked Storage

Linked lists overcome array drawbacks by using non‑contiguous memory and pointers, allowing dynamic growth without massive data movement. Each node contains a data field and a next pointer that links to the following node.

Insertion and deletion only require updating pointers, as illustrated by the following diagrams.

While linked lists save time on modifications, they consume more memory for the pointer fields.

Linked List Overview

Common variants include singly linked list, doubly linked list, and circular singly linked list. Their structures are similar, differing mainly in pointer arrangement.

Singly linked list : each node points only to its successor.

Doubly linked list : each node has both prev and next pointers.

Circular linked list : the last node points back to the head, forming a loop.

Singly Linked List

Concept and Node Design

A node is defined as:

typedef struct Node {
    int data;            // data can be any type, including structs
    struct Node *next;   // pointer to the next node
} Node, *LinkedList;

Initialization

Allocate a head node and set its next to NULL. Always check the return value of malloc to avoid dereferencing a null pointer.

LinkedList listinit(){
    Node *L = (Node*)malloc(sizeof(Node));
    if (L == NULL) {
        printf("Allocation failed");
        exit(0);
    }
    L->next = NULL;
    return L;
}

Head‑Insertion Method

New nodes are inserted at the front, resulting in a reversed order of input.

LinkedList LinkedListCreatH(){
    Node *L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
    int x;
    while (scanf("%d", &x) != EOF) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = x;
        p->next = L->next;
        L->next = p;
    }
    return L;
}

Tail‑Insertion Method

Maintains a tail pointer r so that the resulting list preserves the input order.

LinkedList LinkedListCreatT(){
    Node *L = (Node*)malloc(sizeof(Node));
    L->next = NULL;
    Node *r = L;
    int x;
    while (scanf("%d", &x) != EOF) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = x;
        r->next = p;
        r = p;
    }
    r->next = NULL;
    return L;
}

Traversal, Printing and Modification

Traverse from the head, printing each node’s data. Modification searches for a target value and updates it.

void printList(LinkedList L){
    Node *p = L->next;
    int i = 0;
    while (p) {
        printf("Element %d: %d
", ++i, p->data);
        p = p->next;
    }
}

LinkedList LinkedListReplace(LinkedList L, int x, int k){
    Node *p = L->next;
    while (p) {
        if (p->data == x) p->data = k;
        p = p->next;
    }
    return L;
}

Insertion at Position i

Locate the predecessor node, allocate a new node, adjust pointers, and return the updated list.

LinkedList LinkedListInsert(LinkedList L, int i, int x){
    Node *pre = L;
    for (int j = 1; j < i; ++j) pre = pre->next;
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
    return L;
}

Deletion by Value

Find the node containing the target value, link its predecessor to its successor, then free the node.

LinkedList LinkedListDelete(LinkedList L, int x){
    Node *pre = L;
    Node *p = L->next;
    while (p && p->data != x) {
        pre = p;
        p = p->next;
    }
    if (p) {
        pre->next = p->next;
        free(p);
    }
    return L;
}

Doubly Linked List

Concept

Each node stores both a pre (previous) and next pointer, allowing traversal in both directions and eliminating the need to restart from the head for reverse searches.

typedef struct line {
    int data;
    struct line *pre;
    struct line *next;
} line, *a;

Creation

Prompt the user for the number of nodes, create the head node, then iteratively allocate new nodes, linking them forward and backward.

line* initLine(line *head){
    int number, pos = 1, input_data;
    printf("Enter number of nodes: ");
    scanf("%d", &number);
    if (number < 1) return NULL;
    head = (line*)malloc(sizeof(line));
    head->pre = NULL;
    head->next = NULL;
    printf("Input data for node %d: ", pos++);
    scanf("%d", &input_data);
    head->data = input_data;
    line *list = head;
    while (pos <= number) {
        line *body = (line*)malloc(sizeof(line));
        body->pre = NULL;
        body->next = NULL;
        printf("Input data for node %d: ", pos++);
        scanf("%d", &input_data);
        body->data = input_data;
        list->next = body;
        body->pre = list;
        list = list->next;
    }
    return head;
}

Insertion

Allocate a new node, set its pre and next pointers appropriately, and adjust surrounding nodes.

line* insertLine(line *head, int data, int add){
    line *temp = (line*)malloc(sizeof(line));
    temp->data = data;
    temp->pre = NULL;
    temp->next = NULL;
    if (add == 1) {
        temp->next = head;
        head->pre = temp;
        head = temp;
    } else {
        line *body = head;
        for (int i = 1; i < add-1; ++i) body = body->next;
        if (body->next == NULL) {
            body->next = temp;
            temp->pre = body;
        } else {
            body->next->pre = temp;
            temp->next = body->next;
            body->next = temp;
            temp->pre = body;
        }
    }
    return head;
}

Deletion

Locate the node with the target value, reconnect its predecessor and successor, then free it.

line* deleteLine(line *head, int data){
    line *list = head;
    while (list) {
        if (list->data == data) {
            list->pre->next = list->next;
            if (list->next) list->next->pre = list->pre;
            free(list);
            printf("--Deletion successful--
");
            return head;
        }
        list = list->next;
    }
    printf("Error: element not found
");
    return head;
}

Traversal

Iterate using the next pointer and print each node’s data.

void printLine(line *head){
    line *list = head;
    int pos = 1;
    while (list) {
        printf("Node %d data: %d
", pos++, list->data);
        list = list->next;
    }
}

Circular Singly Linked List

Concept

The last node’s next points back to the head, forming a closed loop.

typedef struct list {
    int data;
    struct list *next;
} list;

Initialization

list* initlist(){
    list *head = (list*)malloc(sizeof(list));
    if (head == NULL) {
        printf("Creation failed, exiting
");
        exit(0);
    }
    head->next = NULL;
    return head;
}

After creating the head, set head->next = head to close the loop.

Creation (Insertion)

int insert_list(list *head){
    int data;
    printf("Enter element to insert: ");
    scanf("%d", &data);
    list *node = initlist();
    node->data = data;
    if (head != NULL) {
        list *p = head;
        while (p->next != head) p = p->next;
        p->next = node;
        node->next = head;
        return 1;
    } else {
        printf("Head is empty
");
        return 0;
    }
}

Insertion at Position

list* insert_list(list *head, int pos, int data){
    list *node = initlist();
    node->data = data;
    if (head != NULL) {
        list *t = head;
        for (int i = 1; i < pos; ++i) t = t->next;
        node->next = t->next;
        t->next = node;
        return head;
    }
    return head;
}

Deletion

int delete_list(list *head){
    if (head == NULL) {
        printf("List is empty!
");
        return 0;
    }
    list *temp = head;
    list *ptr = head->next;
    int del;
    printf("Enter element to delete: ");
    scanf("%d", &del);
    while (ptr != head) {
        if (ptr->data == del) {
            if (ptr->next == head) {
                temp->next = head;
                free(ptr);
                return 1;
            }
            temp->next = ptr->next;
            free(ptr);
            return 1;
        }
        temp = temp->next;
        ptr = ptr->next;
    }
    printf("Element not found
");
    return 0;
}

Traversal

int display(list *head){
    if (head != NULL) {
        list *p = head;
        while (p->next != head) {
            printf("%d   ", p->next->data);
            p = p->next;
        }
        printf("
");
        return 1;
    } else {
        printf("Head is NULL!
");
        return 0;
    }
}

Advanced Concept – Doubly Circular Linked List

The doubly circular list combines the bidirectional pointers of a doubly linked list with the circular connection of the tail to the head, enabling efficient forward and backward traversal in a loop.

Summary of Linked Lists

Array‑based sequential tables require shifting many elements during insertions or deletions, leading to O(n) time and the need for pre‑allocated space. Linked lists eliminate these drawbacks by using pointer‑based dynamic storage, offering O(1) insertion and deletion at known positions while incurring extra memory for pointers. Understanding the trade‑offs helps developers choose the appropriate structure for their projects.