This will be examined at the level of diagrams and pseudocode.
Students should be able to describe the most common data structures (arrays, stacks, queues, linked lists, binary trees) and the most common data processing operations on each of the basic data structures (addition, deletion and retrieval of data, traversal, searching for a given data, sorting of data into some order).
This should be taught and connected to flow charts, pseudocode and programming in the SL/HL core.
The basic ideas and their application should be illustrated with non-computer examples. Each basic idea should then be practised in specific algorithmic contexts using concepts drawn from f low charts, pseudocode and programming.
Suggested practical activity: snowflakes and fractals, towers of Hanoi. (see recursion page also)
Students will be required to state the output of the recursive algorithm.
For example, trees.
For topics 5.1.6 to The Univerasity of San Francisco and University of Singapore have some useful interactive animations
USFCA (first four sections) are particulary useful USFCA animations.
UoS is good for linked lists for example and has pseudocode running in the simulations visualgo.net
Characteristics: Last in, first out (LIFO).
Examples of the applications of stacks may include running recursive processes, return memory addresses.
LINK Recursive thinking; connecting computational thinking and program design.
Access methods: push • pop • isEmpty.
LINK Connecting computational thinking and program design.
Characteristics: First in, first out (FIFO).
Examples of the applications of queues may include print queues and the computer modelling of physical queues (eg supermarket checkouts).
Good discussion of queues and their uses (geeksforgeeks)
Both linear and circular implementation of a queue are required.
LINK Connecting computational thinking and program design.
Access methods: • enqueue • dequeue • isEmpt y.
LINK Connecting computational thinking and program design.
Students should be able to explain push and pop operations, and test on empty/full stack.
Array implementation of a stack animation (usfca)
Students should be able to explain enqueue and dequeue operations, and test on empty/full queue.
Array implementation of a queue animation - circular (usfca)
Linked lists will be examined at the level of diagrams and descriptions. This animation shows how diagrams of a linked list queue might look, experiment with it: Linked list implementation of a queue animation - circular (usfca)
Students are not expected to construct linked list algorithms using pseudocode
Students should understand the concepts of nodes and pointer.
LINK Logical thinking.
Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held in the linked list, searching for a given data item.
Linked list implementation of a stack animation (usfca)
Binary trees will be examined at the level of diagrams and descriptions. Students are not expected to construct tree algorithms using pseudocode. Tracing and constructing algorithms are not expected.
Link for python schools data structures and algorithms. Stack, Queue, Linked List and Binary Tree are near the bottom!
Recursive thinking Binary tree animation (usfca)
Carnegie Melon University CS Binary tree notes
learnlearn.uk CS Non-Binary tree notes
A Binary Tree is a value-oriented dynamic data structure whose elements are organised on the basis of their values. All trees are hierarchical in nature. Intuitively, hierarchical means that a “parent-child” relationship exists between the nodes in the tree. If there is a link between a node “n” and a node “m”, and “n” is above node “m” in the tree, then “n” is the parent of “m”, and node “m” is a child of “n”. Children of the same parent are called siblings. Each node in a tree has at most one parent. There is exactly one node, called the root of the tree, that has no parent. A node that has no children is called a leaf of the tree. A subtree in a tree is any node in the tree together with all its descendants. Each node in a binary tree has no more than two children.
These definitions only apply to a binary tree.
Students should be able to sketch diagrams showing the resulting binary tree after adding a new data item, adding one or more new nodes, and/or removing one or more nodes.
Tutorchase static vs dynamic datastructure article
An array or arrays is the faster option for related data sets of similar type for example a set of numbers but is static
A stack is LIFO and so can be used to reverse the order of data. A queue is FIFO and maintains the order of data. If implemented using an array these data structures will be quick. If implemented using a linked list these structures will expand to hold the required data
A Linked list is useful for one dimensional data where flexibility of access and manipulation is important
A Tree can be the most suitable structure where there is a hierachy on the data or a fast search using the key field is important.
Note that Linked list and Tree are usually implemented dynamically using nodes and pointers