Glanz: aiMOOC über GPT aiMOOC Action erstellt

2026-08-29T12:25:37Z

aiMOOC über GPT aiMOOC Action erstellt

Neue Seite

{{T}}
[[Category:English]]
[[Category:Data Structures]]

{{BR}}
= Introduction =

Data structures are organized ways to store, relate, access, and update data. They are central to [[English:Computer science|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.

{{#ev:youtube|https://www.youtube.com/watch?v=DuDz6B4cqVc|500|center}}

'''Learning goals'''

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

{{BR}}
= Foundations =

{{BR}}
== 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 [[English:Algorithm|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.

{{BR}}
== 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.

{{#ev:youtube|https://www.youtube.com/watch?v=PmAI76OGE_E|500|center}}

{{BR}}
== Measuring Efficiency with Big O ==

[[English:Big O notation|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:

{| class="wikitable"
! 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.

{{BR}}
= Linear Data Structures =

{{BR}}
== 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.

[[File:Array Representations.svg|500px|frameless|center]]

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.

{{BR}}
== 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.

[[File:LinkedListHsrw.svg|500px|frameless|center]]

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.

{{BR}}
== 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.

[[File:Data stack.svg|500px|frameless|center]]

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.

{{BR}}
== 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'''.

[[File:Data Queue.svg|500px|frameless|center]]

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.

{{BR}}
= Hash-Based Structures =

{{BR}}
== 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.

[[File:Hash table 5 0 1 1 1 1 1 LL.svg|500px|frameless|center]]

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.

{{#ev:youtube|https://www.youtube.com/watch?v=KyUTuwz_b7Q|500|center}}

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.

{{BR}}
= Trees and Heaps =

{{BR}}
== 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.

[[File:Binary search tree.svg|500px|frameless|center]]

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).

{{BR}}
== 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.

[[File:Heap-as-array.svg|500px|frameless|center]]

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.

{{BR}}
= Graphs =

{{BR}}
== 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.

[[File:Graph for example adjacency matrix.svg|500px|frameless|center]]

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.

{{BR}}
== 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.

{{BR}}
= 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.

{| class="wikitable"
! 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."

{{BR}}
= 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:

<syntaxhighlight lang="python">
stack = []
stack.append("first")
stack.append("second")
top_item = stack.pop()
print(top_item)
</syntaxhighlight>

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

{{BR}}
= Interactive Tasks =

{{BR}}
== Quiz: Test Your Knowledge ==

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

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

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{MC}}

'''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)

{{E}}
<br>

{{BR}}
== Memory Game ==

<div class="memo-quiz">
{|
|-
| 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
|}
{{E}}
<br>

{{BR}}
== Drag and Drop ==

<div class="lueckentext-quiz">

{| class="wikitable"
! 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
|}
{{E}}

<br>
...
<br />

{{BR}}
== Crossword Puzzle ==

<div class="kreuzwort-quiz">
{|
|-
| 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?
|}
{{E}}
<br>

{{BR}}
== LearningApps ==

<iframe> https://learningapps.org/index.php?s=Data+Structures </iframe>

{{BR}}
== Cloze Text ==

<quiz display=simple>
{'''Complete the text.'''<br>
|type="{}"}
An { array } supports direct access through an index. A { linked list } connects nodes through references. A stack follows the { last in first out } principle. A queue follows the { first in first out } principle. A { hash function } maps keys toward table locations. A balanced binary search tree can support search in { logarithmic time }. A graph represents entities as vertices connected by { edges }. Breadth-first search normally uses a { queue }. Big O notation describes how resource use { grows with input size }. An invariant is a property that valid operations must { preserve }.
</quiz>

<br>

{{BR}}
= Open-Ended Tasks =

{{BR}}
=== Easy ===
# [[English:Array visualization|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.
# [[English:Stack simulation|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.
# [[English:Queue observation|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.
# [[English:Linked list diagram|Linked list diagram]]: Draw five linked nodes with data and next references, then show how the links change when one middle node is removed.

{{BR}}
=== Standard ===
# [[English:Hash collision experiment|Hash collision experiment]]: Design a small hash function for classroom data, insert at least twelve keys, record collisions, and compare two collision-resolution strategies.
# [[English:Binary search tree model|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.
# [[English:Graph route project|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.
# [[English:Data structure interview|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.

{{BR}}
=== Advanced ===
# [[English:Complexity benchmark|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.
# [[English:Priority queue scheduler|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.
# [[English:Graph algorithm video|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.
# [[English:Data structure design portfolio|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.

{{:Open Task - Create a MOOC}}

{{BR}}
= Learning Assessment =

# [[English:Structure selection 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.
# [[English:Complexity reasoning assessment|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.
# [[English:Tree balance assessment|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.
# [[English:Hash table assessment|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.
# [[English:Graph representation assessment|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.
# [[English:Transfer assessment|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.

<br>
<br>

{{BR}}
= Evidence of Learning =

{| class="wikitable"
! 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.
|}

<br>
<br>

{{BR}}
= OERs on the Topic =

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

<iframe> https://en.m.wikipedia.org/wiki/Data_structure </iframe>

<br>

{{BR}}
= Linked Learning Areas =

{| align=center
{{:D-Tab}}
'''[[English:Data Structures|Data Structures]]'''
# [[English:Array data structure|Arrays]]
# [[English:Linked list|Linked lists]]
# [[English:Stack data structure|Stacks]]
# [[English:Queue data structure|Queues]]
# [[English:Hash table|Hash tables]]
# [[English:Tree data structure|Trees]]
# [[English:Heap data structure|Heaps]]
# [[English:Graph data structure|Graphs]]
# [[English:Algorithm analysis|Algorithm analysis]]
# [[English:Computer programming|Programming]]
|}

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

{{BR}}
= aiMOOC Projects =
[[Category:English]]
[[Category:Data Structures]]
[[Category:Computer Science]]
[[Category:Programming]]
[[Category:Algorithms]]
[[Category:Grades 11-13]]
[[Category:AI_MOOC]]
[[Category:GPT aiMOOC]]
{{MT}}

English:Data Structures - Versionsgeschichte

Glanz: aiMOOC über GPT aiMOOC Action erstellt