1.4.2 Data Structures

Mutable means that a variable’s value can be changed without creating an entirely new variable. Immutable values cannot be changed.

A static data structure has a fixed length. A dynamic data structure’s length is not fixed.

In a linear data structure elements are stored contiguously. They may be stored non-contiguously in a non-linear structure.

The first element in the data-structure is considered to be at position zero.

A mutable static data structure An array is a data structure that contains a fixed number of values of one data type. The data is mutable and stored linearly. Each value is identified by a single index and it can be iterated by index.

Generally, when searching in a 2D array, you go down the rows, then across the columns. In 3D arrays, you go to the array number, then down, then along.

A record is a data structure consisting of a fixed number of variables, called fields. Every field has an identifier and a data type. Each field in a record can have a different data type.

Lists are dynamic data structures, consisting of ordered items where an item can occur more than once. They are non-contiguous and can hold multiple data types. Like arrays, it identifies values by an index.

An ordered, immutable set of values. Values can be of differing data types.

An ordered, dynamic data structure in which data can be stored non-contiguously and each element is called a node.

Each node contains the data relating to the element and the pointer to the next node. You must start from the first position indicated by the startpointer, then read the next pointer value and follow this pointer value to access the next data item, and so on…

Graphs are non-linear data structures made up of nodes. They are an abstract structure that represents complex, non-linear relationships.

Nodes: The elements in a graph Edges: The connections between nodes Neighbours: When two nodes are connected by an edge Degree: The number of other nodes that a node is connected to A loop: An edge that connects a node to itself A path: A sequence of nodes that are connected by edges A cycle: A closed path, i.e. a path that starts and ends at the same node (and no node is visited more than once)

In a directed graph the edges can only be traversed in one direction. In an undirected graph the edges can be traversed in both directions.

A stack is an abstract data type that holds an ordered, linear sequence of items. It is a Last In, First Out (LIFO) structure. You need to maintain a pointer at the top of a stack. They may be static or dynamic.

Overflow - attempting to push onto a stack that is full Underflow - attempting to pop from a stack that is empty

push(data) = adds an element to the top of the stack pop() = removes an element from the top of the stack peek() = returns a copy of the element on the top of the stack without removing it is_empty() = checks whether a stack is empty is_full() = checks whether a stack is at maximum capacity when stored in a static (fixed-size) structure

A queue is an abstract data type that holds an ordered, linear sequence of items. It is a First in, First Out (FIFO) structure. You need to maintain a pointer at both the front and back of the stack. They may be static or dynamic. New elements are added to the back or rear of the queue. When an element is removed, the remaining elements do not move up to take the empty space.

enqueue(data) = adds an element to the queue dequeue() = returns an element from the front of the queue is_empty() = checks whether the queue is empty is_full() = checks whether the queue is at maximum capacity (if the size of the queue is constrained)

A tree is an abstract data structure used to represent non-linear data. It is a connected, undirected graph consisting of nodes and edges. There are no cycles in trees so only one path between any 2 nodes.

Root = The first node, at the top. It does not have any incoming nodes. Child = A node with incoming edges Parent = A node with outgoing edges Subtree = Subsection of a tree consisting of a parent and all the children of a parent Leaf = A node with no children

A binary tree is a type of tree in which each node has a​ maximum of two children. Nodes are added in the order given, with the first item at the root. If the next item is less than the root, it is added to the left of the root, otherwise to the right. Apply the same rule at the root of each sub-tree. ​These are used to represent information for binary searches​.

A hash table is an array that uses the hash function. It is a data structure which will find any record in the dataset almost instantly, no matter how large the dataset is. It enables access to data that is not stored in a structured manner.

The hash function is Address = key mod TableSize. A hash function takes an input (key) and computes a numerical index within the bounds of a hash table. Large data sets can be organised so each record is assigned a unique address.