2.14 Data Structures Flashcards
Arrays
Arrays: Ordered, finite set of elements of a single type
1D Array: Linear array, always taken to be zero-indexed (first element in the array is considered to be at position 0)
- E.g oneDimensionalArray = [1, 23, 12, 14, 16, 29, 12] // creates a 1D array
2D Array: Visualised as table or spreadsheet. When searching through 2D array, first go down then across the columns to find given position
- E.g twoDimensionalArray = [[123, 28, 90, 38, 88, 23, 47],[1, 23, 12, 14, 16, 29, 12]]
- print(twoDimensionalArray[1,3]) // Goes down then across, returns 14
3D Array: Visualised as multi-page spreadsheet, thought of as multiple 2D arrays
- Selecting element in a 3D array: threeDimensionalArray[z,y,x]
- z = array no., y = row no., x = column no.
- threeDimensionalArray = [[[12,8],[9,6,19]],[[241,89,4,1],[19,2]]]
- print(threeDimensionalArray[0,1,2]) // Returns 19
Records
Record: Commonly referred to as row in a file, is made up of fields. Records are used in databases, as shown in the table below:
| ID | 1Name | 2Name |
| 002 | Tyson | Fury |
| 003 | Deonte | Wilder |
Above is file containing 3 records, each record has three fields
- Declaring a Record:
*fighterDataType = record
integer ID
string FirstName
string Surname
end record
*
- Each field in the record can be identified by recordName.fieldName
- Creating a Record:
fighter : fighterDataType
- To access attributes:
fighter.FirstName
001 | Antony | Joshua |
Lists
List: Data structure w/ no. of ordered items, items can occur more than once
- Lists similar to 1D arrays, elements accessed in the
same way
- The difference is that list values are stored non contiguously (do not have to be stored next to each other in memory, as data in arrays is stored)
- Lists can also contain elements of more than one data type, unlike arrays.
Tuples
Tuples: Ordered set of values of any type. Is immutable, cannot be changed, elements cannot be added or removed once it has been created
- tupleExample = (“Value1”, 2, “Value3”)
- Elements in a tuple are accessed in a similar way to elements in an array, with the exception that values cannot be changed or removed. Attempting to do so will result in a syntax error
print(tupleExample[0])
» Value1 :
tupleExample[0] = “ChangedValue”
» Syntax Error
Linked Lists
Linked List: Dynamic data structure used to hold an ordered sequence. Items do not have to be contiguous
- Each item is called a node, contains data field w/ another address called pointer field
Graphs
Graph: Set of vertices/nodes connected by edges/arcs
- Directed Graph: Edges only traversed in one direction
- Undirected Graph: Edges traversed in both directions
- Weighted Graph: Cost attached to each edge
- Computers able to process graphs using an adjacency matrix or adjacency list
Adjacency Matrix
O|A|B|C
A|
B|
C|
- Convenient to work with due to quicker access times
- Easy to add nodes
Ajacency List
A → {B:4, C:18, D:12}
B → {A:4, C:5, E:8}
C → {A:18, B:5, D:5}
-More space efficient for large, sparse networks
Stacks
- Stack: Last In First Out (LIFO) data structure
- Items can only be added to or removed
from top of stack, used to reverse an action, (E.g ‘undo’ buttons) - Either static or dynamic
- Maximum size known in advance = static, easier to implement & make more efficient use of memory
- Implemented using a pointer, points to top of stack, where next piece of data is inserted
Manipulating A Stack
Queues
Queue: First In First Out (FIFO) data structure; items added to end of queue & removed from the front of queue
- Used in printers, keyboards & simulators
-
Linear Queue: 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 - Queues make use of two pointers: one pointing to the front of the queue & one pointing to the back of the queue, where the next item can be added
Manipulating A Queue
Trees
Tree: Connected form of a graph. Consist of root node connected to other nodes using branches
Binary Tree
Binary Tree: Tree in which each node has a maximum of 2 children
- Used to represent information for binary searches, as information in these trees is easy
to search through
- Represented by storing each node with a left & right pointer within a 2D array
Pre Order Traversal
Pre-order Traversal: Follows the order: root node, left subtree, then right subtree
- (Basically Depth First)
In Order Traversal
In-order Traversal: follows the order: left subtree, root node, right subtree. Traverses nodes in sequential order
Post Order Traversal
Post order Traversal: Follows the order: left subtree, right subtree, root node
- Nodes are traversed in the order in which you pass them on the right
