CampusLearn
← BIT 201 Data Structures and Algorithms

Arrays, Linked Lists, Stacks and Queues

Notes

Sequential storage A data structure organises values so that a program can store, retrieve and change them reliably. An array holds indexed elements in contiguous storage, allowing direct access by position without inspecting earlier elements. In a fixed array, capacity is set in advance; a dynamic array expands by allocating more storage and copying values. A linked list instead stores nodes containing data and links to other nodes. Access requires following links, while insertion at a known node can avoid shifting many elements. Access rules and selection A stack follows last in, first out: push adds an item and pop removes the most recently added item. It supports undo operations and nested function calls. A queue follows first in, first out and suits service requests arriving over time. Enqueue adds at the rear, while dequeue removes at the front. Implementations should detect empty removals and capacity limits. Choose a structure using the dominant operations, memory overhead and required ordering, rather than assuming that one structure is always fastest. Practical example A Nairobi matatu SACCO records 120 departures in an array and retrieves departure 80 directly using index 79 under zero-based indexing. Inserting a new first departure into a full logical sequence requires shifting 120 existing entries. Its booking desk separately queues 18 customers; serving 7 leaves 18 minus 7 = 11 waiting. A supervisor records three edits on an undo stack: fare, route and driver. One pop reverses the driver edit first. These concrete operations show why indexed records, fair service and undo history need different access rules.

Quiz

1. What is a likely cost of inserting at the beginning of an array?

2. Which structure best preserves arrival order at a booking desk?

3. Fare, route and driver edits are pushed in that order. Which is undone first?

Sign in to submit and securely grade your quiz.