DESCO, Sub-Assistant Engineer, Exam: 20.06.2025 (BUET)প্রশ্ন ও সমাধান

A singly linked list is a linear data structure made of nodes, where each node stores data plus a single pointer to the next node; the last node's pointer is NULL. Unlike an array, its elements are not stored in contiguous memory, so insertion/deletion don't require shifting elements — only pointer updates.

graph LR
  H[head] --> A["10 | •"] --> B["20 | •"] --> C["30 | •"] --> D["40 | NULL"]

Node structure (C):

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

Example — building 10 → 20 → 30:

struct Node *head = malloc(sizeof(struct Node));
head->data = 10;
head->next = malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;

// Traversal
for (struct Node *p = head; p != NULL; p = p->next)
    printf("%d -> ", p->data);   // Output: 10 -> 20 -> 30 ->

Key operations & cost:

Operation	Time
Insert/Delete at head	O(1)
Insert/Delete at tail (no tail pointer)	O(n)
Search / access by index	O(n)

Why use it: dynamic size (grows/shrinks at runtime, unlike a fixed array) and cheap head insertion — used to implement stacks, queues, and adjacency lists. Trade-off: no random access, and each node needs extra memory for the pointer.

Exam takeaway: Singly linked list — O(1) insertion at the front, O(n) search, one-directional traversal only (contrast with doubly linked list, which allows backward traversal).