data structures comp sci y1
Elementary data type | base level - lowest form of data |
|---|---|
Structured data type | data type made of other data types |
Static data structure | cannot change size after initialisation |
Dynamic data structure | can change size after initialisation |
Array | a static data structure where all elements are the same data type |
Index | position of an element in a data structure |
Multi-dimensional array | an array within an array |
Element | one value/item in a data structure |
Record | an immutable static data structure of mixed data types (could be a tuple, could be an object) |
Tuple | an immutable static data structure of mixed data types |
Immutable | elements cannot be changed after initialisation |
Composite data type | data type made of other data types |
|---|---|
Abstract data type | data type that does not physically exist - but is constructed out of other data structures |
Queue | abstract FIFO static data structure where items are removed from the front and added to the rear |
Circular queue | abstract FIFO static data structure where dequeued slots are reused (using MOD to change pointer) |
Priority queue | abstract FIFO dynamic data structure where items are enqueued in order of priority |
First In, First Out (FIFO) | items are removed in order of entry |
Enqueue | add item to the end of a queue |
Dequeue | remove and return item from start of queue |
isEmpty | check if queue is empty (size == 0) |
isFull | check if queue is full (size == maxSize) |
Queue | abstract FIFO static data structure where items are removed from the front and added to the rear |
|---|---|
Circular queue | abstract FIFO static data structure where dequeued slots are reused (using MOD to change pointer) |
Priority queue | abstract FIFO dynamic data structure where items are enqueued in order of priority |
First In, First Out (FIFO) | items are removed in order of entry |
Enqueue | add item to the end of a queue |
Dequeue | remove and return item from start of queue |
isEmpty | check if queue is empty (size == 0) |
isFull | check if queue is full (size == maxSize) |
List | an abstract dynamic data structure which is mutable and contains mixed data types |
Linked list | a dynamic abstract data structure implemented using nodes (data/pointer pairs) |
Append | adds an item to the end of the list |
Push | adds an item to the end of the list |
Pop | remove an item from the end of a list (or by position if passed in) |
Stack | abstract LIFO data structure where items are added to and removed from the top |
|---|---|
Last In, First Out (LIFO) | the last item added is the first item to be removed |
Call stack | system level data structure used for calling functions and managing return addresses and parameters |
Stack frame | parameters, return addresses and local variables of one function call |
Parameter | value passed into a function |
Return address | location in memory where the result of a function is stored |
Heap | memory allocated for use by dynamic data structures |
Overflow | attempting to push onto a stack that is full |
Underflow | attempting to pop from a stack that is empty |
Stack overflow error | when a program tries to add a stack frame onto a full call stack (no memory left available) |
Hashing | creating an address out of a key to be placed in a hash table (typically use mod) |
|---|---|
Hash table | result of a hashing algorithm - abstract data structure where addresses for data are assigned by hashing |
Collision | when a hashing algorithm generates an address for a key that is already in use |
Mid-square method | square the key, find middle two values and mod by table size |
Folding method | divide into equal parts, add parts together, mod result by table size |
Dictionary | data structure made up of key:value pairs |
Graph | abstract data structure representing complex relationships |
|---|---|
Edge | line that connects nodes |
Arc | line that connects nodes |
Vertex | data within a graph/tree |
Node | data within a graph/tree |
Directed graph | a graph where the edges point in only one direction |
Digraph | a graph where the edges point in only one direction |
Undirected graph | a graph where the edges are bidirectional (point in both directions) |
Weighted edge | an edge which has a value associated with it |
Adjacency matrix | 2D list used to represent a graph |
Adjacency list | dictionary used to represent a graph |
Tree | abstract data structure which is a graph with no cycles |
|---|---|
Root | starting node, has no parent nodes |
Child | has a parent node |
Parent | has a child node |
Subtree | subsection of a larger tree |
Leaf node | node with no further child nodes |
Binary search tree | tree where each node can only have a maximum of two children |
Pre-order traversal | Root, left subtree, right subtree |
In-order traversal | Left subtree, root, right subtree |
Post-order traversal | Left subtree, right subtree, root |