Data Structures: Organization, Access, and Efficiency

Grade 11 · Technology · Study Guide

A college-prep overview of fundamental data structures — how they work, when to use them, and how to reason about their performance.

A data structure is a systematic way of organizing and storing data so that operations such as insertion, deletion, and retrieval can be performed efficiently. Choosing the right data structure for a problem is one of the most important decisions in software engineering, because it determines the time and space complexity of every algorithm that touches that data.

The most fundamental data structures are arrays and linked lists. An array stores elements in contiguous memory, giving O(1) random access by index but O(n) insertion and deletion in the middle because elements must shift. A singly linked list stores each element in a node that holds a value and a pointer to the next node; insertion and deletion at a known position are O(1), but finding that position requires O(n) traversal. Doubly linked lists add a pointer backward, enabling O(1) deletion given a node reference.

Stacks and queues are abstract data types typically built on arrays or linked lists. A stack follows Last-In-First-Out (LIFO) order — the classic 'undo' operation or function call stack. A queue follows First-In-First-Out (FIFO) order, used in print spoolers, BFS graph traversal, and task scheduling. A deque (double-ended queue) supports O(1) operations at both ends.

Trees impose hierarchical structure. A binary search tree (BST) stores each node with a key, left subtree of smaller keys, and right subtree of larger keys, giving O(log n) average-case search, insert, and delete — but O(n) worst-case on unbalanced input. Balanced BST variants like AVL trees and Red-Black trees guarantee O(log n) worst case through rotations. Hash tables map keys to array indices via a hash function, delivering average O(1) lookup, insert, and delete at the cost of extra memory and potential collisions handled by chaining or open addressing.

Key terms

Array

A fixed-size collection of elements stored in contiguous memory, accessible in O(1) by index.

Linked List

A sequence of nodes where each node contains data and a pointer to the next node; supports O(1) insertion at a known position.

Stack

A Last-In-First-Out (LIFO) data structure supporting push and pop operations.

Queue

A First-In-First-Out (FIFO) data structure supporting enqueue and dequeue operations.

Binary Search Tree (BST)

A tree where each node's left subtree contains smaller keys and right subtree contains larger keys, enabling O(log n) average search.

Hash Table

A data structure that maps keys to values via a hash function, providing average O(1) lookup.

Big O Notation

A mathematical notation for describing the upper-bound time or space complexity of an algorithm as input size grows.

Collision

When two distinct keys hash to the same index in a hash table; resolved via chaining or open addressing.

Tree Rotation

A local restructuring operation on a BST used in self-balancing trees to maintain O(log n) height.

Heap

A complete binary tree where each node satisfies the heap property; supports O(log n) insert and O(log n) extract-min/max.

Flashcards

Array access time

O(1) — direct index calculation in contiguous memory.

Array insertion (middle)

O(n) — elements after the insertion point must shift right.

Linked list search

O(n) — must traverse from head to find a value.

Stack push / pop

O(1) — operates only on the top element.

Queue enqueue / dequeue

O(1) amortized — operates only on front or back.

BST average search

O(log n) — each comparison halves the remaining search space.

BST worst-case search

O(n) — occurs when the tree is fully unbalanced (like a sorted-insert chain).

Hash table average lookup

O(1) — hash function maps key directly to a bucket.

Hash table worst-case lookup

O(n) — all keys collide into the same bucket (degenerate chaining).

Heap extract-min/max

O(log n) — root removed and heap property restored by sifting down.

LIFO

Last-In-First-Out — the ordering principle of a stack.

FIFO

First-In-First-Out — the ordering principle of a queue.

Questions

1. Which data structure provides O(1) average-case lookup by key?

   1. Array
   2. Linked List
   3. Hash Table
   4. Binary Search Tree
   Show answer

   Answer: Hash Table

   Hash tables use a hash function to map keys directly to array indices, giving average O(1) lookup; BSTs average O(log n) and arrays require O(n) linear search without an index.

2. A call stack in a programming language runtime uses which abstract data type?

   1. Queue
   2. Deque
   3. Stack
   4. Priority Queue
   Show answer

   Answer: Stack

   A call stack follows LIFO — the most recently called function is the first to return, which is exactly how a stack operates.

3. In the worst case, a binary search tree degrades to O(n) for search operations.

   Show answer

   Answer: True

   If elements are inserted in sorted order into a plain BST, every node becomes a right child, creating a structure equivalent to a linked list with O(n) search.

4. The data structure that stores elements in contiguous memory and allows O(1) random access by index is called a(n) ________.

   Show answer

   Answer: array

   Arrays store elements in contiguous memory; the address of any element is base + (index x element_size), computed in constant time.

5. Which operation has O(n) time complexity in a singly linked list without a tail pointer?

   1. Inserting at the head
   2. Deleting the head
   3. Searching for a value
   4. Checking if the list is empty
   Show answer

   Answer: Searching for a value

   To search for a value, you must start at the head and follow pointers one by one until the value is found or the list ends — O(n) in the worst case.

Get a personalized course on Data Structures built around your child.