Linked Lists

Introduction

A linked list is a linear data structure in which each element (a node) contains the data plus a pointer (next) to the following node. Unlike an array, a linked list does not occupy contiguous memory — nodes can be scattered anywhere in RAM and are connected by pointers. This makes insertion and deletion at known positions cheap (O(1) given the pointer) at the cost of losing random access (you must walk the list from the head).

Types of Linked Lists

• Singly Linked List — each node points to the next.
• Doubly Linked List — each node has next and prev pointers.
• Circular Linked List — the last node's next points back to the head.
• Circular Doubly Linked List — both circular and doubly linked.

Node Definition

struct Node {
    int data;
    struct Node* next;
};

Basic Operations on Singly Linked List

Insertion at head:

void insertHead(Node** head, int x) {
    Node* n = malloc(sizeof(Node));
    n->data = x;
    n->next = *head;
    *head = n;
}

Insertion at tail:

void insertTail(Node** head, int x) {
    Node* n = malloc(sizeof(Node));
    n->data = x; n->next = NULL;
    if (!*head) { *head = n; return; }
    Node* cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = n;
}

Deletion by value:

void deleteValue(Node** head, int x) {
    Node* cur = *head;
    Node* prev = NULL;
    while (cur && cur->data != x) { prev = cur; cur = cur->next; }
    if (!cur) return;
    if (prev) prev->next = cur->next;
    else *head = cur->next;
    free(cur);
}

Traversal: walk cur from head until cur->next is NULL, performing the desired action at each node.

Doubly Linked List

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

Each node has two pointers. Deletion of a given node becomes O(1) if you have a pointer to it — you fix up its neighbors directly without scanning for prev.

Circular Linked List

The last node's next pointer goes back to the head instead of NULL. Useful for round-robin scheduling, playlists, or buffer rotation. Traversal must check current != head rather than current != NULL.

Array vs Linked List

Applications

Linked lists implement stacks, queues, hash table buckets (chaining), free lists in memory allocators, and adjacency lists in graph representations. Circular lists are used for round-robin CPU scheduling.

Summary

A linked list trades random access for cheap insertion and deletion. Use it when the dataset grows and shrinks frequently at the ends or at known positions. Use arrays when random access dominates or cache friendliness matters.

Important Questions

1. Define linked list and list its types.
2. Write the structure of a node for a singly linked list.
3. Write C/Java code to insert a node at the head and at the tail.
4. Write C/Java code to delete a node by value.
5. Explain the doubly linked list and its advantages.
6. Compare array and linked list.
7. What is a circular linked list? Give one application.
8. Explain how a linked list can implement a stack.