Linear Data Structures: Arrays, Stacks, Queues, Linked Lists, Sorting, Searching & Recursion
What it is
Linear data structures organize a collection of elements in a single sequential line — each element (except possibly the first and last) has exactly one predecessor and one successor. This skill covers arrays and sparse matrices (indexed storage), stacks, queues and priority queues (controlled access order), linked lists (dynamic sequential storage), the standard sorting and searching algorithms that run over these structures, and recursion together with parameter-passing rules — since searching, sorting and list traversal are all naturally written recursively.
Core concepts
Arrays. Elements sit in contiguous memory, so any element is reached in O(1) by computing its address from the base address and index (base + index × element size) — random access. The cost: inserting or deleting in the middle needs every following element shifted, O(n). A classic array has a fixed size set at allocation.
Sparse matrices. A sparse matrix has mostly zero entries. Storing it as a full two-dimensional array wastes space on those zeros; instead only non-zero entries are stored, typically as a list of (row, column, value) triples — a 1,000-cell matrix with 10 non-zero values needs storage for just those 10 triples.
Stack. LIFO: the last element pushed is the first popped; push and pop both act at one end (the "top") in O(1). Real uses: the function call stack itself (each call pushes a frame, each return pops it — this is what makes recursion work), expression evaluation (for example, converting infix to postfix and then evaluating it), and undo (each action pushed, undo pops the most recent).
Queue. FIFO: elements enter at the rear (enqueue) and leave from the front (dequeue). With a proper implementation — a circular buffer or a linked list with a tracked tail — both operations are O(1); a naive array queue that shifts elements after every dequeue degrades to O(n). Real uses: task/CPU scheduling and breadth-first traversal, which visits nodes in the order they were discovered.
Priority queue. Every element carries a priority; dequeue always removes the highest- (or lowest-) priority element first, not necessarily the earliest inserted. A heap is the standard implementation, giving O(log n) insert and extract — an unsorted array gives O(1) insert but O(n) extract, a sorted array the reverse, so the heap balances both.
Linked list. Each node holds its data plus a pointer/reference to the next node; nodes are scattered in memory, not contiguous, so there is no index-to-address formula. A singly linked list points only forward; a doubly linked list adds a previous pointer, trading extra memory for backward traversal. Given a pointer directly to the position, insertion or deletion there is O(1) — only a few pointers move. Finding that position in the first place, with no random access available, takes O(n).
Sorting algorithms. All of the following sort a sequence into order; they differ in method, time cost, and whether equal elements keep their relative order (stability):
| Algorithm | Idea | Time complexity | Stable? |
|---|---|---|---|
| Bubble Sort | Repeatedly swaps adjacent out-of-order elements; the largest unsorted element "bubbles" up each pass | O(n²) | Yes |
| Selection Sort | Repeatedly finds the minimum of the unsorted portion and swaps it into the next sorted position | O(n²) | No |
| Insertion Sort | Builds the sorted portion one element at a time, shifting larger elements right to insert each new one | O(n²) worst, O(n) nearly-sorted | Yes |
| Merge Sort | Divide-and-conquer: splits the sequence in half, sorts each half recursively, merges the sorted halves | O(n log n), all cases | Yes |
| Quick Sort | Divide-and-conquer: partitions elements around a chosen pivot, recursively sorts each side | O(n log n) average, O(n²) worst | No |
Searching. Linear search checks each element in turn until it finds a match — O(n), and it places no requirement on the data's order. Binary search, O(log n), requires the data to already be sorted: it compares the target to the middle element and discards the half that cannot contain it, repeating on the remaining half.
Recursion. A recursive function calls itself on a smaller instance of the same problem. It needs a base case — a condition simple enough to answer directly, with no further call — and a recursive case that does some work and calls itself on an input that has moved strictly closer to the base case. Recursion uses the call stack implicitly: each call's local state is pushed as a stack frame and popped when that call returns, which is also why a missing or unreachable base case eventually overflows the stack.
Parameter passing. Pass-by-value gives the function a copy of the argument; changes made inside the function to that copy never affect the caller's original variable. Pass-by-reference gives the function access to the original variable itself, so changes made inside are visible to the caller after the function returns. This is a conceptual distinction between two calling conventions, not a claim about which one any particular language uses by default — that varies.
Worked example
Recursion trace: factorial(4). Define factorial(n) as 1 when n = 0 (the base case), and n × factorial(n − 1) otherwise (the recursive case). The calls unwind forward: factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which calls factorial(0) — and factorial(0) returns 1 directly, with no further call. Returning back up the stack: factorial(1) = 1 × 1 = 1; factorial(2) = 2 × 1 = 2; factorial(3) = 3 × 2 = 6; factorial(4) = 4 × 6 = 24. Five stack frames (n = 4 down to n = 0) existed at the deepest point, and each returns only after the call it made returns.
Binary search trace. Search the sorted array [3, 7, 12, 18, 24, 29, 33, 41] (indices 0–7) for 24. The middle index, 3, holds 18; 24 is larger, so indices 0–3 are discarded, leaving indices 4–7. The new middle index, 5, holds 29; 24 is smaller, so indices 6–7 are discarded, leaving only index 4 — which holds 24, found in 3 comparisons rather than the 5 a linear scan from the front would need.
Common traps
- Treating array insertion/deletion in the middle as O(1) — it is O(n), because every following element must shift.
- Treating a linked list as having array-like O(1) random access — reaching the k-th node takes O(n) traversal.
- Mixing up removal order — a stack removes the most recently added element (LIFO); a queue removes the least recently added (FIFO).
- Assuming a priority queue dequeues in arrival order — it dequeues by priority, and a later arrival can be served before an earlier one.
- Quoting Quick Sort's worst case as O(n log n) — its worst case is O(n²) (a poor pivot on already-sorted data); only its average case is O(n log n).
- Running binary search on unsorted data — the halving logic depends entirely on the data already being ordered.
- Assuming pass-by-value can modify the caller's variable — only pass-by-reference does.
Speed technique
Group the five sorting algorithms by complexity, not by name: Bubble, Selection and Insertion are the three O(n²) sorts; Merge and Quick average O(n log n) — but Quick alone still carries an O(n²) worst case, the single most commonly missed exception in this list.
Let the data decide the search method: unsorted data leaves only linear search, O(n); sorted data allows binary search, O(log n).
Anchor stack versus queue to a picture: a stack is a pile of plates (LIFO, take from the top); a queue is a line at a counter (FIFO, take from the front). A priority queue breaks the line entirely — whoever has the highest priority is served next, arrival position aside.
For any recursion problem, find the base case first, then check that the recursive case's argument is guaranteed to reach it — that one check catches most recursion bugs before they become a stack overflow.
Check yourself
- A stack executes push(1), push(2), push(3), then two pop() calls. What value is now on top?
Show answer
1 — LIFO pops 3 then 2, leaving 1 on top. - Which of the five standard sorting algorithms has an O(n log n) average case but an O(n²) worst case?
Show answer
Quick Sort. - Binary search runs on a sorted array of 8 elements. What is the maximum number of comparisons it needs?
Show answer
⌈log₂8⌉ = 3 comparisons. - Given a pointer to a linked-list node holding 10, immediately followed by a node holding 20, what single change deletes the 20-node?
Show answer
Redirect the 10-node's next pointer to whatever followed 20, skipping over it. - A function receives an integer parameter by value and doubles it inside the function body. After the function returns, what is the caller's original variable?
Show answer
Unchanged — the function only modified its own copy.
What the exam tests here
None of the 3 papers we hold has asked this. It is on the syllabus, so it can appear — but nothing in the paper record tells us how it would be framed. Treat it as insurance, not as a priority.
Try it: Linear Data Structures, Recursion, Sorting & Searching questions
Real questions from the CUET PG CS bank on exactly this skill. Pick an answer to see the full solution — the intuition, the worked steps, the faster methods and the traps.
A classic (non-dynamic) array is declared with a fixed size of 50 at the time it is allocated. Once the program is running, what is a direct consequence of this design?
Show the answer and worked solution
Answer: option C
A classic array's size is fixed at the moment memory is allocated for it, and that allocation is not revisited automatically while the program runs.
If more than 50 elements are ever needed, the existing block has no extra room, so a new, larger block must be allocated and the data copied over.
Option A describes dynamic-array behaviour, such as automatic resizing, which is precisely what a classic fixed-size array does not do on its own.
Option B is incorrect because array access is O(1) regardless of index, so element 1 and element 50 are reached equally fast.
The fixed-capacity limitation is what option C describes, making it the correct answer.
An array stores n elements. Which statement correctly contrasts deleting the last element with deleting the first element?
Show the answer and worked solution
Answer: option B
Deleting the last element only requires marking that one slot as unused, or reducing a tracked length, with no other element needing to move — O(1).
Deleting the first element leaves a gap at index 0 that must be closed, and the only way to close it without breaking contiguity is to shift every one of the remaining n − 1 elements one position to the left — O(n).
Option D confuses direct access to read or write a single index, which is O(1), with the cost of deletion, which depends on how many elements must move afterward.
This asymmetry, O(1) at the end and O(n) at the front, is what option B describes, making it correct.
An initially empty stack receives the operations, in order: push(5), push(9), push(2), pop(), push(7), pop(). What value does the final pop() return?
Show the answer and worked solution
Answer: option C
Tracing in order: push(5) leaves [5], push(9) leaves [5, 9], push(2) leaves [5, 9, 2] with 2 on top.
The first pop() removes and returns the current top, 2, leaving [5, 9].
push(7) then adds to the top, leaving [5, 9, 7] with 7 on top.
The second pop() removes and returns the current top, which is now 7, so the final pop() returns 7, option C.
An array holds 10 elements at indices 0 through 9. A new element is inserted at index 3, and every element from that position onward must shift one position to the right to make room. How many elements are shifted?
Show the answer and worked solution
Answer: option B
Inserting at index 3 in a 10-element array (indices 0–9) requires every element from index 3 up to the last occupied index, 9, to move one slot right before the new value can be written into index 3.
The elements occupying indices 3, 4, 5, 6, 7, 8 and 9 are the ones that must move — an inclusive count of (9 − 3) + 1 = 7 elements.
Counting only the elements at or after the insertion index, rather than the whole 10-element array or stopping one short, gives this figure.
Seven elements shift, so the correct answer is option B.
Using the standard stack-based algorithm for converting an infix expression to postfix (where * has higher precedence than +), what is the postfix form of A + B * C?
Show the answer and worked solution
Answer: option C
Scanning left to right: operand A goes straight to the output, giving output 'A' with an empty operator stack.
The operator + is pushed onto the empty stack, since there is nothing yet to compare its precedence against.
Operand B goes to the output next, giving 'A B', with + still the only entry on the stack.
The operator * has higher precedence than the + sitting on top of the stack, so + is not popped; * is pushed on top instead, leaving the stack as [+, *].
Operand C goes to the output, giving 'A B C'.
With the input exhausted, the stack is emptied into the output from the top down: * first, then +, giving the final postfix string 'A B C * +', option C.
Answer above — every one shows its working.