Die Druckversion wird nicht mehr unterstützt und kann Darstellungsfehler aufweisen. Bitte aktualisiere deine Browser-Lesezeichen und verwende stattdessen die Standard-Druckfunktion des Browsers.

Data Structures

Introduction

Data structures are organized ways to store, relate, access, and update data. They are central to computer science because the same information can behave very differently depending on how it is represented. A program that chooses an appropriate structure can become faster, clearer, and easier to maintain.

This aiMOOC is designed for learners in Grades 11–13. You will compare common structures, reason about their efficiency, connect them to algorithms, and select structures for realistic programming problems. You do not need to memorize every implementation detail. Instead, focus on the relationship between a problem, the operations it needs, and the structure that supports those operations well.

Learning goals

Explain data structures: Describe why programs organize data in different ways.
Distinguish interfaces and implementations: Separate what an abstract data type promises from how a program stores it.
Analyze efficiency: Compare common operations using Big O notation.
Implement structures: Trace and write basic operations on arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs.
Choose structures: Justify a data-structure choice for a concrete application.

Foundations

What Is a Data Structure?

A data structure is a way of organizing and storing data together with the relationships and operations that make the data useful. Examples include arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs. The structure you choose affects how efficiently a program can search, insert, delete, traverse, prioritize, or connect data.

A data structure is not the same thing as an algorithm. A data structure organizes data; an algorithm is a procedure for solving a problem. They work together. For example, binary search is an algorithm that takes advantage of ordered, indexable data, while breadth-first search is an algorithm that naturally uses a queue when traversing a graph.

Abstract Data Types and Implementations

An abstract data type, or ADT, describes behavior from the user's point of view. It specifies which operations are available and what those operations mean. A stack ADT, for example, supports adding an item to the top and removing the most recently added item. The ADT does not require one particular representation: a stack can be implemented with an array, a dynamic array, or a linked list.

This distinction helps you reason at two levels. At the interface level, you ask what operations the program needs. At the implementation level, you ask how memory, links, indices, or hashing can support those operations.

Measuring Efficiency with Big O

Big O notation describes how the amount of work or memory grows as the input size grows. It is a growth-rate model rather than an exact stopwatch measurement. In introductory analysis, you often compare operations using the following broad classes:

Growth	Typical interpretation	Example
O(1)	Constant growth	Accessing an array element by a valid index
O(log n)	Logarithmic growth	Searching a balanced binary search tree
O(n)	Linear growth	Scanning an unsorted list
O(n log n)	Linearithmic growth	Typical efficient comparison sorting
O(n²)	Quadratic growth	Comparing every pair in a simple nested-loop process

Complexity depends on assumptions. A hash-table lookup is often described as average-case O(1), but collisions can make the worst case slower. A binary search tree can support O(log n) search when its height is logarithmic, but an unbalanced tree can become chain-like and require O(n) search.

Linear Data Structures

Arrays and Dynamic Arrays

An array stores elements in indexed positions. Because the address of an element can be calculated from its index, indexed access is typically O(1). In a fixed-size array, the number of available positions is determined when the array is created. A dynamic array keeps an underlying array but occasionally allocates a larger block and copies elements so that the logical sequence can grow.

Arrays are strong when you need fast indexed access and compact storage. They are less convenient when you repeatedly insert or delete near the front or middle, because later elements may have to shift. Dynamic arrays make appending efficient on average by growing capacity geometrically, but an individual resize can be expensive.

A useful distinction is between size and capacity. Size is the number of elements currently stored. Capacity is the number of elements the underlying storage can hold before a resize is needed.

Linked Lists

A linked list stores data in nodes. Each node contains a value and one or more references to other nodes. In a singly linked list, each node usually points to the next node. In a doubly linked list, nodes also store a link to the previous node.

Linked lists do not provide constant-time access to an arbitrary position by index; reaching the kth node usually requires following links from the beginning. However, if you already have a reference to the relevant node or predecessor, insertion and deletion can often be performed without shifting many other elements. Linked structures therefore trade direct indexing for flexible connections.

Stacks

A stack follows the last in, first out principle. The most recently added item is the first one removed. The common operations are push to add an item, pop to remove the top item, and peek or top to inspect the top item without removing it.

Stacks appear in expression evaluation, undo systems, depth-first search, and function-call management. A browser's simple back-history model can also be explained with stack-like behavior, although real browsers use more complex structures.

Queues

A queue follows the first in, first out principle. Items enter at the rear and leave from the front. Common operations are enqueue and dequeue.

Queues are useful when order of arrival matters, such as print jobs, message processing, task scheduling, simulations, and breadth-first search. A circular buffer is an array-based queue implementation that reuses positions at the beginning of the array instead of repeatedly shifting elements.

Hash-Based Structures

Hash Tables

A hash table stores key-value associations. A hash function maps a key to an index or bucket. If two keys map to the same location, a collision occurs. Collision-resolution strategies include separate chaining and open addressing.

With a suitable hash function and a controlled load factor, insertion, lookup, and deletion are often O(1) on average. That average performance does not mean every operation is constant time. Poor hashing, too many collisions, or adversarial input can create much slower behavior.

Hash tables are a natural choice for dictionaries, caches, symbol tables, sets, frequency counters, and fast membership tests. Their main strength is direct access by key rather than ordered traversal.

Trees and Heaps

Trees

A tree is a hierarchical structure made of nodes connected by edges. A rooted tree has one distinguished root. Nodes may have children, and nodes with no children are called leaves. Trees model file systems, organization charts, syntax, menus, search indexes, and many other hierarchies.

A binary tree allows each node to have at most two children. A binary search tree additionally maintains an ordering rule: keys in the left subtree compare smaller than the node's key, while keys in the right subtree compare larger, assuming distinct comparable keys.

Search, insertion, and deletion depend on tree height. In a balanced binary search tree, height is O(log n), so these operations can also be O(log n). In the worst case, repeated insertion in an unfortunate order can produce a highly unbalanced tree with height O(n).

Heaps and Priority Queues

A priority queue is an ADT in which removal returns an item with highest or lowest priority rather than simply the oldest item. A binary heap is a common implementation. It is a complete binary tree that satisfies a heap-order property.

A binary heap is usually stored compactly in an array. For a zero-based array, the children of position i are commonly found at positions 2i + 1 and 2i + 2 when those positions exist. Insertion and removal of the extreme-priority element are O(log n), while inspecting that extreme element is O(1).

Heaps are useful for schedulers, event simulations, shortest-path algorithms, and efficient top-k processing.

Graphs

Vertices, Edges, and Representations

A graph represents entities as vertices and relationships as edges. Graphs may be directed or undirected, weighted or unweighted, connected or disconnected. They can model road networks, social connections, communication networks, prerequisite relationships, and web links.

Two important representations are the adjacency list and the adjacency matrix. An adjacency list stores, for each vertex, the vertices connected to it. An adjacency matrix uses a two-dimensional table whose entries indicate whether pairs of vertices are connected.

Adjacency lists are usually space-efficient for sparse graphs, where relatively few of the possible edges exist. Adjacency matrices use O(V²) space for V vertices but make an edge-existence test straightforward and constant time. The best representation depends on graph density and the operations the algorithm performs most often.

Traversing Graphs

Breadth-first search explores vertices in increasing distance from a starting point in an unweighted graph and naturally uses a queue. Depth-first search explores one path deeply before backtracking and can be implemented with recursion or an explicit stack.

Both traversals run in O(V + E) time when the graph is stored as adjacency lists, where V is the number of vertices and E is the number of edges. Their traversal order differs, so they support different tasks. Breadth-first search can find shortest paths measured by number of edges in an unweighted graph, while depth-first search is useful for tasks such as cycle detection, connected-component exploration, and topological reasoning in directed acyclic graphs.

Choosing the Right Structure

There is no universally best data structure. You choose by identifying the operations that matter, the expected amount and shape of data, ordering requirements, memory constraints, and the guarantees your application needs.

Problem need	Often suitable structure	Reason
Fast access by numeric position	Array or dynamic array	Direct indexing is typically constant time
Frequent insertion through known links	Linked list	Nodes can be relinked without shifting a whole sequence
Most-recent item handled first	Stack	Last in, first out behavior matches the requirement
Arrival order must be preserved	Queue	First in, first out behavior matches the requirement
Fast lookup by key	Hash table	Average lookup can be constant time
Ordered searching and range-oriented structure	Balanced search tree	Ordering supports logarithmic navigation and sorted traversal
Repeated access to highest or lowest priority	Heap-based priority queue	Extreme element is available quickly
Arbitrary relationships and routes	Graph	Vertices and edges directly model networks

A good justification names both the required operations and the trade-off. For example, saying "use a hash table because it is fast" is incomplete. A stronger argument is: "Use a hash table because the application performs many membership tests by unique key, does not need sorted iteration, and can tolerate average-case rather than strict worst-case constant lookup."

Implementation Thinking

When implementing a data structure, maintain its invariants: properties that must remain true after every operation. A binary search tree must preserve its ordering rule. A heap must preserve both completeness and heap order. A queue must remove items in the same order in which they entered unless the specification says otherwise.

You should also test boundary cases: an empty structure, a structure with one element, duplicate keys if duplicates are allowed, full capacity in an array-based implementation, missing search targets, and repeated insertion or deletion. Testing these cases helps reveal pointer errors, incorrect index arithmetic, and broken invariants.

Here is a short Python example that uses a list as a stack:

stack = []
stack.append("first")
stack.append("second")
top_item = stack.pop()
print(top_item)

The final item added is removed first, so this code prints second. The important idea is the stack behavior, not the particular programming language.

Interactive Tasks

Quiz: Test Your Knowledge

Which operation is typically constant time for an array? (Accessing an element by index) (!Inserting at the front of a full array) (!Searching an unsorted array by value) (!Deleting every element)

What principle describes a stack? (Last in first out) (!First in first out) (!Smallest key first) (!Random item first)

Which operation removes the oldest item from a standard queue? (Dequeue) (!Push) (!Peek) (!Hash)

Why can a hash table experience collisions? (Different keys can map to the same location) (!Every key must be stored twice) (!Arrays cannot store keys) (!Trees always contain duplicate nodes)

What extra rule defines a binary search tree? (Keys are ordered between left and right subtrees) (!Every node has exactly two children) (!Every leaf has the same key) (!Nodes are stored in arrival order)

Which structure is commonly used to implement a priority queue efficiently? (Binary heap) (!Singly linked cycle) (!Plain text file) (!Unsorted fixed record)

Which graph traversal naturally uses a queue? (Breadth first search) (!Depth first search) (!Binary search) (!Hash probing)

Why are adjacency lists often preferred for sparse graphs? (They avoid storing most nonexistent edges) (!They require one matrix cell for every vertex pair) (!They sort every vertex automatically) (!They guarantee constant time shortest paths)

What does Big O notation mainly describe? (How resource use grows with input size) (!The exact runtime in seconds) (!The programming language syntax) (!The number of comments in source code)

What is an invariant in a data structure? (A property that operations must preserve) (!A value that must change after every operation) (!A file that contains test data) (!A random choice of memory address)

Memory Game

Array	Indexed sequence with typically constant-time direct access
LinkedList	Nodes connected by stored references
Stack	Last-in-first-out collection
Queue	First-in-first-out collection
HashTable	Key-value structure based on a hash function
BinaryHeap	Complete tree structure used for priority queues
Graph	Vertices connected by edges
Invariant	Property that remains true after valid operations

Drag and Drop

Match the correct terms.	Topic
Direct indexed access	Array
Last in first out	Stack
First in first out	Queue
Key mapped to bucket	Hash table
Vertices connected by edges	Graph

...

Crossword Puzzle

Array	Which structure stores elements in indexed positions?
Stack	Which structure removes the most recently added item first?
Queue	Which structure removes items in arrival order?
Hashing	What process maps a key toward a table location?
Vertex	What is a node in a graph commonly called?
Pointer	What programming concept can store a reference to another memory location?

LearningApps

Cloze Text

Open-Ended Tasks

Easy

Array visualization: Create a labeled diagram of an array with at least eight positions, show three example index accesses, and explain why direct indexing is efficient.
Stack simulation: Use cards or sticky notes to model push and pop operations, record the sequence of actions, and photograph or draw the final stack.
Queue observation: Observe a real queue such as a cafeteria line or printer queue, describe where the first-in-first-out model fits, and note one way reality differs from the simplified model.
Linked list diagram: Draw five linked nodes with data and next references, then show how the links change when one middle node is removed.

Standard

Hash collision experiment: Design a small hash function for classroom data, insert at least twelve keys, record collisions, and compare two collision-resolution strategies.
Binary search tree model: Build a binary search tree from a chosen sequence of values, trace searches for three targets, and explain how insertion order changes tree height.
Graph route project: Model a local transport or school-room network as a graph, create an adjacency list, and use breadth-first search reasoning to find a route with the fewest edges.
Data structure interview: Interview a programmer, IT specialist, or advanced computing student about one real data-structure choice, then summarize the problem, chosen structure, and trade-offs.

Advanced

Complexity benchmark: Implement or simulate two structures that solve the same lookup problem, collect timing or operation-count data at increasing input sizes, and interpret the pattern using Big O reasoning.
Priority queue scheduler: Design a task scheduler based on a heap-backed priority queue, define how priorities are compared, test at least two tie cases, and justify the design.
Graph algorithm video: Produce a short instructional video that demonstrates breadth-first search and depth-first search on the same graph, highlighting how the queue and stack behaviors change traversal order.
Data structure design portfolio: Choose a realistic application such as a game, library system, social network, or route planner, propose at least three interacting data structures, justify each choice, and discuss one alternative design.

Learning Assessment

Structure selection assessment: For a messaging system, compare a queue, stack, and priority queue, then justify which behavior is most appropriate under two different delivery policies.
Complexity reasoning assessment: Given several operation counts for increasing input sizes, infer a plausible growth class and explain what additional evidence would make your conclusion stronger.
Tree balance assessment: Compare two insertion orders that produce different binary search tree shapes, predict their search costs, and propose a strategy that avoids severe imbalance.
Hash table assessment: Analyze a collision-heavy hash table, identify whether the problem is caused by the hash function, load factor, or collision strategy, and recommend a justified improvement.
Graph representation assessment: Choose between an adjacency list and adjacency matrix for a sparse road network and a dense small network, explaining the time-space trade-off in each case.
Transfer assessment: Design a data model for a new application of your choice and defend how at least two data structures cooperate to support the application's most important operations.

Evidence of Learning

Evidence type	What successful learning can show
Knowledge	You can explain the defining behavior, common operations, and typical uses of arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs.
Reasoning	You can compare time and space trade-offs, distinguish average and worst cases, and connect performance claims to assumptions.
Skills	You can trace operations, maintain structural invariants, build small representations, and test boundary cases.
Products	You can produce diagrams, code, benchmarks, graph models, explanations, and a justified design portfolio.
Transfer	You can identify the operations required by an unfamiliar problem and choose or combine structures that support those operations appropriately.

OERs on the Topic

The following English Wikipedia article provides an open reference overview of the topic:

Linked Learning Areas

Data Structures

Data structures connect directly with Algorithms, Software engineering, databases, Computer networks, Artificial intelligence, Mathematics, and Discrete mathematics. They are especially important in programming courses because implementation choices determine how algorithms use memory and time.