Describe and implement the data structures used in Advanced Higher: one- and two-dimensional arrays, records, sequential files, linked lists, stacks and queues, including their operations.

What this dot point is asking

The SQA wants you to know the data structures used at Advanced Higher, how each one stores data, and the operations each supports. You should be able to choose the right structure for a problem and write code that uses it, including the two-dimensional array and the dynamic structures (linked list, stack, queue).

Arrays and records

A one-dimensional array stores a fixed number of items of the same type, each reached by an integer index. A two-dimensional array extends this to a grid, where each element is reached by a row index and a column index; it suits tabular data such as a timetable or a marks sheet. A record groups several fields of possibly different types (for example a name, an age and a balance) under one structure, and an array of records is a common way to hold many such entities.

Sequential files

A sequential file stores records on backing storage so data persists between runs. Records are written and read in order from the start of the file; to reach the hundredth record you read past the first ninety-nine. Sequential access suits batch processing of an entire file, such as reading every record to produce a report.

Linked lists

A linked list stores data as a chain of nodes. Each node holds a data item and a pointer (reference) to the next node; the last node points to null. Because nodes are linked by pointers rather than stored side by side, you insert or delete an item by rerouting pointers, without shifting every later item as an array would require. The trade-off is that you cannot jump straight to the nth item; you must follow the chain from the head.

Stacks

A stack is a last-in, first-out (LIFO) structure: you add (push) and remove (pop) only at the top. The most recently added item is the first to leave. Stacks model anything that unwinds in reverse order, such as the return addresses of nested or recursive procedure calls, or an undo history.

Queues

A queue is a first-in, first-out (FIFO) structure: items are added (enqueued) at the back and removed (dequeued) from the front, so they leave in the order they arrived. Queues model fair, ordered waiting, such as a print spooler serving jobs in submission order, or a buffer holding incoming data until it can be processed.

Try this

Q1. State which data structure is last-in, first-out. [1 mark]

• Cue. A stack.

Q2. Give one advantage of a linked list over an array for inserting an item in the middle of the data. [1 mark]

• Cue. Insertion only reroutes a couple of pointers; the array would have to shift every later element along by one.