Introduction
Almost every program you will ever meet stores a collection of items — a list of marks, the characters of a name, the queue of jobs waiting for a printer. Arrays, strings and linked lists are the three most fundamental ways to keep such a collection in memory. Understanding them is not optional for a Data Structures exam: they are the raw material out of which stacks, queues, hash tables, trees and graphs are later built. In BCS, Bank IT and IT-officer written and MCQ papers, this topic appears again and again — index calculations, time-complexity of insert/delete, the difference between arrays and linked lists, string length, and pointer manipulation are perennial favourites.
This lesson builds the ideas from first principles: how memory is laid out, why array indexing is O(1), how a string is really just an array of characters, and how a linked list trades away random access to gain cheap insertion. Master these and you can reason about any linear data structure.
Learning objectives
- Define an array and explain contiguous memory allocation and the address-calculation formula.
- Compute the memory address of any element in a 1-D or 2-D array (row-major and column-major).
- State and justify the time complexity of access, search, insertion and deletion for arrays.
- Explain what a string is, how it is stored, null-termination, and common string operations.
- Define singly, doubly and circular linked lists and describe node structure with pointers.
- Perform insertion and deletion at the head, tail and middle of a linked list.
- Compare arrays and linked lists and choose the right one for a given problem.
- Answer typical exam MCQs on indexing, complexity and pointer manipulation with confidence.