Linked list, graph, stack, queue, tree, binary search tree and hash table

The following structures to store data: linked-list, graph (directed and undirected), stack, queue, tree, binary search tree, hash table

1.4.2 Data Structures

Practise exam questions

Data Structures — Note 2 of 3

Candidates need to have an understanding of the behaviour of linked-lists, graphs, stacks, queues, trees, binary search trees and hash tables. Candidates need to be able be aware of how the aforementioned data structures can be implemented. We would recommend a general understanding of these principles that can be applied to a given scenario rather than trying to memorise code patterns.

What you need to know

Abstract data structures model data in ways that suit particular problems. You need to understand how each behaves, what it is used for and how it can be implemented, rather than memorising code.

What to know

Key terms

Exam tipCommon mistake

Linked list: A dynamic structure of nodes, each holding data and a pointer to the next node. A start pointer gives the first node. Items can be added or removed by changing pointers, without moving other data.
Stack: A LIFO (last in, first out) structure. push adds to the top, pop removes from the top, peek looks at the top item. Uses: undo, the call stack, backtracking, reversing.
Stack errors: overflow (pushing onto a full stack) and underflow (popping from an empty stack).
Queue: A FIFO (first in, first out) structure. Items are enqueued at the rear and dequeued from the front. Uses: print queues, keyboard buffers, breadth-first search.
Common mistake: Saying items are removed from the rear of a queue. They are added at the rear and removed from the front.
Circular queue: When the rear pointer reaches the end of the array it wraps around to the start, reusing freed spaces.
Graph: A set of nodes (vertices) connected by edges (arcs). Edges can be directed or undirected and weighted (e.g. distances). Stored as an adjacency matrix or adjacency list.
Tree: A connected graph with no cycles, with a root node and child nodes in a hierarchy. Nodes with no children are leaves.
Binary search tree: Each node has at most two children; values less than the node go in the left subtree and greater values in the right subtree, allowing fast searching.
Hash table: Data is stored at a location calculated by applying a hash function to its key, so it can be found directly. Collisions (two keys giving the same location) are handled e.g. by placing the item in the next free space or by chaining a list at that location.

Exam technique

Tip:Learn the behaviour (LIFO/FIFO, the ordering rule of a BST) and be able to draw each structure after a series of operations.