More commonly referred to as a row in a file, made up of fields
Record declaration
fighterDataType = record integer ID string FirstName string Surname end record
Lists
A data structure consisting of a number of ordered items where the items can occur more than once
Lists
Values are stored non-contiguously
Can contain elements of more than one data type
List Operations
isEmpty()
append(value)
remove(value)
search(value)
length()
index(value)
insert(position, value)
pop()
pop(position)
Tuples
An ordered set of values of any type that cannot be changed
Tuple
tupleExample = ("Value1", 2, "Value3")
Linked Lists
A dynamic data structure used to hold an ordered sequence where the items do not have to be in contiguous data locations
Linked Lists
Each item is called a node and contains a data field and a pointer field
Stores the index of the first item and the index of the next available space
Adding to a Linked List
1. Add the new value to the end and update the 'NextFree' pointer
2. Update the pointer field of the previous node to point to the new node
3. Update the pointer field of the new node to point to the next node
Removing from a Linked List
Update the pointer field of the previous node to bypass the deleted node
Linked Lists
Wastes memory as deleted nodes are not truly removed
Require more memory to store pointers compared to arrays
Items can only be traversed in sequence, cannot be directly accessed
Graphs
A set of vertices/nodes connected by edges/arcs
Graph Types
Directed Graph
Undirected Graph
Weighted Graph
Adjacency Matrix
A way for computers to process graphs
Adjacency Matrix
A - 4 18 12 -
B 4 - 5 - 8
C 18 5 - 5 -
D 12 - - - 3
E - 8 - 3 -
Adjacency List
A way for computers to process graphs
Adjacency List
A -> {B:4, C:18, D:12}
B -> {A:4, C:5, E:8}
C -> {A:18, B:5, D:5}
D -> {A:12, E:3}
E -> {B:8, D:3}
Adjacency Matrix
Convenient to work with due to quicker access times
Easy to add nodes
Adjacency List
More space efficient for large, sparse networks
Stacks
A last in first out (LIFO) data structure where items can only be added to or removed from the top
Stacks
Used to reverse an action, such as to go back a page in web browsers
Can be implemented as either a static or dynamic structure
Adjacency Matrix Advantages
Convenient to work with due to quicker access times
Adjacency List Advantages
More space efficient for large, sparse networks
Stacks
A last in first out (LIFO) data structure. Items can only be added to or removed from the top of the stack.
Stacks are key data structures in computer science; they are used to reverse an action, such as to go back a page in web browsers. The 'undo' buttons that applications widely make use of also utilise stacks.
Static stacks
Where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory.
Stacks implemented using a pointer
The pointer points to the top of the stack, where the next piece of data will be inserted.
Stack Operations
isEmpty()
push(value)
peek()
pop()
size()
isFull()
Queues
A first in first out (FIFO) data structure; items are added to the end of the queue and are removed from the front of the queue.
Linear queue
A data structure consisting of an array. Items are added into the next available space in the queue, starting from the front. Items are removed from the front of the queue.