BPSC (Multiple Ministry) Assistant Programmer (CSE) Exam: 19.07.2023প্রশ্ন ও সমাধান

Direct answer: an array stores elements in contiguous memory with O(1) index-based access but costly insertion/deletion; a linked list stores elements in scattered nodes connected by pointers, giving O(1) insertion/deletion at a known position but only O(n) sequential access.

graph LR
  subgraph Array - contiguous memory
  A0["arr[0]=10"] --- A1["arr[1]=20"] --- A2["arr[2]=30"] --- A3["arr[3]=40"]
  end

graph LR
  subgraph "Linked List - scattered nodes"
  N1["10 | next"] --> N2["20 | next"] --> N3["30 | next"] --> N4["40 | NULL"]
  end

Aspect	Array	Linked List
Memory layout	Contiguous block	Scattered nodes linked by pointers
Access by index	O(1) — direct address computation	O(n) — must traverse from the head
Insertion/deletion at start	O(n) — must shift all elements	O(1) — just relink pointers
Insertion/deletion in middle	O(n) — shift elements after the point	O(n) to find the position, O(1) to link once found
Memory overhead	None extra — just the data	Extra pointer per node
Size	Fixed at creation (static array) or costly to resize	Grows/shrinks dynamically, one node at a time
Cache performance	Excellent (contiguous, cache-friendly)	Poor (nodes scattered, more cache misses)

Worked example: inserting a new element at the front of a collection of 1,000 items — an array must shift all 1,000 existing elements one slot to the right (O(n)); a linked list simply creates a new node and points it at the current head (O(1)), regardless of the list's size.

Exam takeaway: choose arrays when index-based random access and cache-friendly iteration matter most (e.g. lookup tables); choose linked lists when frequent insertions/deletions at arbitrary positions matter more than random access (e.g. implementing a queue/stack whose size is unpredictable).