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

A first in first out data structure. Items are added to the end of the queue and are removed from the front of the queue

Linear queue

Items are added into the next available space in the queue, starting from the front. Makes user of two pointers, one at the front and one at the back

Circular queue

Once the queue’s rear pointer is equal to the maximum size of the queue it can loop back to the front, using space more effectively

Trees

A connected form of a graph. Trees have a root node which is the top node. Nodes are connected using branches, with the lower-level nodes being the children of the higher-level nodes

Binary tree

A type of tree in which each node has a maximum of two children

Pre-Order Traversal

Follows the order: root node, left subtree, right subtree. Using the outline method, nodes are traversed in the order in which you pass them on the left, beginning at the left hand side

In-Order Traversal

Follows the order: left subtree, root node, right subtree. Using the outline method, nodes are traversed in order in which you pass under them

Post-Order Traversal

Follows the order: left subtree, right subtree, root node. Using the outline method, nodes are traversed in the order in which you pass them on the right

Hash Tables

An array which is coupled with a hash function. The hash function takes in data (a key) and releases an output (the hash) and maps the key to an index in the hash table