1.4.2 Data Structures

Arrays

Arrays

An ordered, static set of elements of a single type. A 1D array is a linear array. Unless stated in the question, arrays are always taken to be zero-indexed

2D and 3D arrays

2D: Can be visualised as a table or spreadsheet. When searching through, you first go down the rows and then across the columns.

3D: Can be visualised as a multi-page spreadsheet. Selecting an element requires three variables. An array number, the row number an the column number

Records

More commonly referred to as a row in a file and is made up of fields. Used in databases. Each field in a records can be identified by recordName.fieldName. When creating a record, a variable must first be declared before its attributes can be accessed

Lists

A data structure consisting of a number of ordered items where the items can occur more than once. Can contain elements of more than one data type

Tuples

An immutable, ordered set of values of any type. Once it is created it cannot be changed. Tuples are initialised using regular brackets instead of square brackets

Linked Lists

A dynamic data structure used to hold an ordered sequence where the items forming it are stored non-contiguously. Each item is called a node, and contains a data field alongside another address called a link or pointer field which contains the address of the next item in the list

Manipulating a linked list

Values can easily be added or removed by editing pointers. When removing a node, it isn’t actually deleted, only ignored. Although this is easier, it wastes memory and as items are stored in a sequence, they can only be traversed in this order and cannot be accessed directly

Graphs

A set of vertices/nodes connected by edges/arcs. There are three types:

• Directed: Edges can only be traversed in one direction

• Undirected: Edges can be traversed in both directions

• Weighted: A cost is attached to each edge

Stacks

A last in first out data structure. Items can only be added to or removed from the top of the stack. Used to reverse an action, such as go back a page in web browsers. Stacks can be implemented as either a static or dynamic structure

Queues