Arrays, Linked Lists, Stacks and Queues: every key term you need (+ practice quiz)
25 flashcard terms for Data Structures & Algorithms Topic 2, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A block of equally sized cells laid out back to back in memory, so the address of any element follows from the base address plus index times element width.
Random access indexing
Reading or writing element i of an array in O(1) time using address arithmetic. Linked structures cannot do this and need O(n) traversal to reach position i.
Dynamic array
A growable array that allocates a larger buffer and copies when full, usually doubling capacity. Appends cost O(1) amortized while indexing stays O(1) worst case.
Array insertion cost
Inserting at an interior position shifts every later element right, so it costs O(n) worst case. Appending at the end is the only cheap insertion point.
Singly linked list
A chain of nodes each holding a value and one next pointer. Insertion or deletion given a node reference is O(1), but reaching position i takes O(n) hops.
Doubly linked list
A chain whose nodes carry both next and previous pointers, allowing O(1) deletion of a node given only that node and backward traversal at the cost of one extra pointer per node.
Circular linked list
A list whose last node points back to the first, so traversal never hits a null end. Convenient for round-robin scheduling and for buffers with no natural boundary.
List node
The allocated record inside a linked structure holding a payload plus one or more links. Each node is a separate allocation, which is why linked lists have poor memory locality.
Head pointer
The reference to the first node of a list and the entry point for all traversals. Losing it leaks the entire chain, so operations must update it carefully.
Tail pointer
A stored reference to the last node so appending becomes O(1) instead of requiring a full traversal. It must be refreshed whenever the final node is removed.
Sentinel node
A dummy node placed at a list boundary so that insertion and deletion need no special case for an empty list or for the first element, shortening and de-risking the code.
Cache locality
The performance advantage of touching nearby addresses, which favours arrays over linked nodes. A linear array scan often beats a linked traversal even at identical asymptotic cost.
Stack abstract data type
A collection supporting push, pop and peek where the most recently added item leaves first. Every operation is O(1) on either an array or a linked implementation.
Last in first out order
The stack discipline in which removal always returns the newest element. It matches nested structure such as bracket matching, undo histories and expression evaluation.
Call stack
The runtime stack of activation records holding parameters, locals and return addresses. Recursion depth maps directly onto it, so deep recursion risks stack overflow.
Queue abstract data type
A collection supporting enqueue at the back and dequeue at the front, so the oldest element leaves first. It underlies breadth-first search and scheduling.
First in first out order
The queue discipline in which removal returns the element that has waited longest, giving fairness in scheduling and level-by-level order in graph traversal.
Circular buffer
A fixed-size array used as a queue with head and tail indices that wrap using modular arithmetic, giving O(1) enqueue and dequeue without shifting elements.
Double-ended queue
A structure allowing insertion and removal at both ends in O(1). It generalises the stack and queue and powers sliding-window maximum algorithms.
Array-backed stack
A stack stored in a dynamic array with a top index. Push and pop are O(1) amortized, memory is compact, and only occasional resizing copies cost more.
Linked queue
A queue held as a linked list with both head and tail pointers, giving true worst-case O(1) enqueue and dequeue with no resizing pause, at the price of per-node overhead.
Iterator invalidation
The hazard that resizing or restructuring a container leaves outstanding references pointing at freed or stale memory. Linked nodes survive growth while array reallocation breaks pointers.
In-place list reversal
Walking a singly linked list once while redirecting each next pointer to the previous node, using three references and finishing in O(n) time with constant extra space.
Two-pointer traversal
Advancing one reference faster than another over a list or array to find a midpoint, detect a cycle, or compare positions without a second pass or extra storage.
Unrolled linked list
A hybrid storing a small array of elements in each node, cutting pointer overhead and improving locality while keeping cheap splicing between blocks.