Data structures and abstract data types study guide

A method for choosing a structure

Start by identifying the relationship between the data items and the order in which they must be used. If data is addressed by one or more integer indices and all elements have the same data type, an array may be suitable. If the required behaviour is first-in, first-out, choose a queue. If the newest item must be handled first, choose a stack. If items represent relationships, consider a graph; if those relationships form a hierarchy, consider a tree. If values are accessed through keys, a dictionary or hash table may be suitable. A vector can be represented by a one-dimensional array.

The explanation should then identify the equivalent implementation. For example, a queue could use an array together with front and rear positions. A stack could use an array and a top position. These representations are not the abstract data types themselves; they are ways of implementing the required behaviour when the language does not provide the structure as a built-in type.

Reasoning about maintenance

For a queue, explain where a new item is added and where an item is removed. In a linear queue, positions are treated as a sequence. In a circular queue, the representation allows the sequence of usable positions to continue from the end back to the beginning. This can allow positions that have become free to be used again. A priority queue requires an additional decision: removal is based on priority rather than only on arrival order. In every case, explain how the front, rear and stored items change.

For a stack, explain that push places an item at the top and pop removes the top item. After each operation, the top position must identify the new top. Check the empty condition before removal and, for a fixed-size representation, check the capacity before addition. These checks are part of maintaining a valid structure.

For a hash table, explain that a key is used to calculate a position at which associated data is stored or searched for. A complete answer should describe the table, the key and the associated value, then explain how insertion and lookup use the calculated position. If more than one key maps to a position, the implementation must have a defined way to represent and maintain the affected data; do not assume that a calculated position is automatically unique.

Static and dynamic decisions

A static representation is easier to describe when the maximum amount of data is known and fixed storage is acceptable. Its disadvantage is that it may not accommodate more data than its capacity. A dynamic representation is useful when the amount of data can change during execution, but the program must manage changes in size and structure. A strong comparison links the decision to the problem rather than claiming that one approach is always better.

Files and records in an applied answer

When a solution stores structured information, identify fields within each record and explain how records are grouped in a file. State whether the program reads or writes a text file or a binary, non-text file. The format used to write data must be compatible with the method used to read it. Avoid claiming that a file is automatically a record, or that text and binary files are interchangeable without describing how their data is interpreted.

Exam application checklist

For a design question, name the required behaviour, select the abstract data type, give an equivalent representation and describe the key operations. For a comparison question, discuss both advantages and disadvantages of static and dynamic structures in relation to the context. For an array question, identify every dimension and what its indices mean. For a maintenance question, trace the relevant positions after each insertion or removal. Finally, test boundary conditions: an empty queue or stack, a full fixed-size representation, reused positions in a circular queue, and multiple data items associated with keys in a hash table.

Self-check

Can you explain why a queue and a stack remove different items? Can you distinguish a field, record and file? Can you define an n-dimensional array using indexed elements and a tuple of integers? Can you describe front, rear and top maintenance? Can you compare static and dynamic structures without saying that one is always superior? Can you select a graph rather than a tree when the relationships are not being described as a hierarchy? If any answer is incomplete, practise by writing a short representation and tracing two or three operations.