Data structures and abstract data types revision notes

What is a data structure?

A data structure is a way of organising and storing data so that it can be used in a solution to a problem. The choice of structure depends on the data and the operations required. For example, a queue is suitable when items must be processed in order, whereas a stack is suitable when the most recently added item must be processed first.

Arrays

A one-dimensional array stores elements of the same data type and uses one index for each element. It can represent a vector. A two-dimensional array uses two indices and can represent a matrix, such as a table of values. More generally, an n-dimensional array is a set of elements with the same data type indexed by a tuple of n integers. A tuple is an ordered list of elements.

When designing a solution, identify what each index represents. In a two-dimensional array, the first index might identify a row and the second a column. A common error is confusing the dimensions or attempting to access an index outside the valid range.

Fields, records and files

A field is an individual item of data. A record is a collection of related fields, and a file is a collection of stored data. A program must be able to read from and write to text files, and also read from and write to binary, non-text files. Text data is represented in a form intended to be read as characters, while binary data is stored in a non-text representation. The program must use a suitable format when interpreting the data it reads.

Abstract data types

An abstract data type describes the data and the operations that can be performed on it without requiring one particular implementation. A programming language may not provide the type as a built-in structure, so it can be represented using an equivalent structure such as an array or linked arrangement of elements.

A queue follows first-in, first-out behaviour. New data is added at the rear and removed from the front. A linear queue has a simple sequence of positions. A circular queue treats the end of the storage as connected to the beginning, so positions can be reused. A priority queue removes an item according to priority rather than simply its arrival position. A queue must maintain information such as the front, rear and the stored items.

A stack follows last-in, first-out behaviour. Data is added and removed at the top. The main operations are often described as push, which adds an item, and pop, which removes the top item. The stack must maintain the position of its current top. Attempting to remove from an empty stack is an error condition; adding to a full fixed-size representation is also an error condition.

A graph represents relationships between items. A tree is a hierarchical structure with connected elements arranged in levels. A hash table stores data using a calculated position derived from a key. The table must be maintained when data is added, found or removed, and the chosen representation must account for keys mapping to positions. A dictionary associates keys with values. A vector can be represented by a one-dimensional array.

Static and dynamic structures

A static structure has a fixed size or allocation determined before or during its use. This can make its storage and indexing straightforward, but its capacity may limit the amount of data it can hold. A dynamic structure can change its size while a program runs. This allows it to adapt to the amount of data, but its management is more complex. When comparing them, relate the choice to the expected amount of data and the operations the solution needs.

Common errors

Do not confuse a queue with a stack: a queue removes the earliest suitable item, while a stack removes the most recently added item. Do not describe an array only as a list; include its common data type and indexed positions. Do not treat a record as the same thing as a file: a record contains related fields, whereas a file stores data. When explaining an implementation, state which positions or variables represent the front, rear, top, key or value and how they change after an operation.