Data Structures

• What is an array and its features?

  A variable that can contain more than 1 data item, but all homogenous (the same) data type

  - index (relative to address where array starts) used to access array contents, so ordered collection of items

  - contiguous section of memory allocated to store that data

  
  

  Features:

  - static data structure - size/length of structure cannot change at run-time

  - mutable - structure/data can be changed at run-time
• What is a one-dimensional (1D) array?

  Array where elements are stored linearly and accessed individually/through 1 index
• What is a two-dimensional (2D) array?


  Array where elements stored similar to a table, accessed through 2 indexes (like rows and columns)

  - e.g. Countries[0][0] = "Angola"
• What is a three dimensional (3D) array?


  Array where elements stored/accessed through 3 indexes (visually similar to a cube)

  - e.g. Countries[2,2,2] = "USA"
• What is a list and its features?

  Variable that can contain more than 1 data item, and heterogenous (differing) data types

  - splits up data and stored in varying chunks of memory locations (non-contiguous), ordered/connected through pointers

  
  

  Features:

  - Mutable - structure/data can be changed at run-time

  - Dynamic - structure size can change at run-time
• What is a record data structure?

  A collection of related fields (variables) linked to a single entity

  - each field in record can be a different data type (i.e. records can have heterogenous data types)
• How do you construct a record data structure?


  1) Define record structure - what fields will be in record?

  2) Declare a variable/array to be used with record structure (e.g. Car1 = (record structure) TCar)

  3) Assign and retrieve data from the variable inside record structure
• What is a tuple and its features?

  Similar to an array - variable that can contain more than 1 data item and referenced by an index (so ordered collection), but immutable + can store heterogenous data types

  
  

  Features:

  - Static - size/length of structure cannot change at run-time

  - Immutable - structure/data it contains cannot be changed at run-time
• What are the key features of a stack data structure?

  - Linear data structure - all data stored in order added

  - Last In First Out (LIFO) data structure - last item to be added to stack at the top of it, and are first ones to be removed from it

  - has a stack pointer that indicates the node/item at the top of it

  - "push" = adding to stack, "pop" = removing from stack

  - "peeking" = viewing the item at the top of the stack without removing it from the stack
• What is stack overflow/underflow?

  Stack overflow - attempting to push an item onto a full stack

  Stack underflow - attempting to pop an item off of an empty stack
• How are stacks implemented?

  Using a linked lists/array, but can use OOP
• What are some examples of the uses of stacks?

  Used by processors to track the flow of programs

  - when subroutine called, PC stores instruction it has to return to once subroutine completed onto stack

  Performing depth-first searches on graph data structures

  Keeping track of user inputs for undo operations

  Backtracking algorithms

  Evaluating mathematical expressions without brackets
• What are the key features of a queue data structure?

  - Linear data structure - all data stored in order added

  - FIFO data structure - first item added to queue first one to be removed

  - "enqueued" = adding to queue, "dequeue" = removing from queue

  - can peek at front of queue like stacks can

  - Has both a back/tail pointer (always points to last item in queue) and a front/head pointer (always points to first item in queue)

  - Can have priority queue where important items jump to front spaces in queue
• What is queue overflow/underflow?

  Queue overflow - attempting to enqueue an item onto a full stack

  Queue underflow - attempting to dequeue an item off of an empty stack
• How can queues be implemented?

  Using an array or OOP

  - implementing with array can cause problems - front + back pointers move in same direction as are added/removed and gradually move away from front of array, so it runs out of space
• What are circular queues and how can they be useful?


  A type of queue where the back pointer cycles back to the front of an array when it reaches the end of it

  Solves the issues of implementing a queue in a normal linear array and useful if you want to restrict the number of items in an array + have a known memory footprint (e.g. sprites in game design)
• What are the uses of queues?


  Processor scheduling

  Transferring data between processors and printers

  Performing breadth-first searches on graph data structures
• What is a linked list?

  A type of list where the order of items/nodes is determined by a series of pointers linking them together (not by their physical order in memory)

  - start pointer identifies first node in list

  - has the same features as a normal list - dynamic + mutable
• What is a doubly/circular linked list?

  Doubly linked list - linked list where nodes have extra pointer to point back to previous item

  Circular linked list - linked list where the last node points back to the first node
• How do you implement linked lists and the what are the benefits of each implementation?

  Can implement with a static array:

  - in static arrays data stored contiguously in relation to base address, so linked lists can change the logical order of this data in the array while its still stored contiguously physically

  Can also implement with OOP (much more beneficial):

  - linked lists that use object can use any available memory address to store data (doesn't need to be contiguous in any way)

  - can change data dynamically through this (unlike static array)
• What are the uses/applications of a linked list?

  OSs managing a processor can store process blocks in a ready state (no need to fetch)

  Image viewers can switch between previous + next images

  Music players can store tracks in a playlist

  Web browsers can navigate backwards + forwards via list of visited pages

  Hash table collision resolution (as an overflow)

  Maintaining a file allocation table of linked clusters on secondary storage
• What are the operations you can perform on a linked list?

  Add - adds node to a linked list

  Delete - removes node from a linked list

  Next - moves to next item in a list

  Previous - moves to previous in a doubly linked list

  Traverse - a linear search through the linked list
• What are the steps to add an item to a linked list?

  1) Check data structure to see if there's free memory for new node - if not output error + stop

  - when list implemented as array, have second linked list to keep track of free storage in the first list

  2) Create new node + insert data into it, or (if array) insert data into node indicated by free storage pointer

  3) (If array) Update free pointer to next available storage space
• What are some special situations you may come across when adding to a linked list and their solutions?

  If linked list empty - new node become first item, create start pointer there

  If new node should be placed before first node/at front of list - new node become 1st node (change start pointer to it) + points to 2nd node

  If new node to be placed inside linked list:

  1) Start at 1st node, if value of current node < value of new node follow list along until correct position for new node found or reach end of list

  2) Set new node to point where former node for that position pointed

  3) set previous node in list to point to new node
• What are the steps to remove an item to a linked list?

  1) Check if linked list empty - if so output error + stop

  2) If 1st item to delete, set start pointer to next node then remove

  3) If item to delete inside linked list - start at 1st node + follow along until item found/end of list reached, if current node to delete found set previous node's pointer to next node

  4) If using array, update free pointer to current node's memory address
• What are the steps to traversing a linked list?

  1) Check if linked list empty, if so stop + output error

  2) Start at node start pointer pointing to + output item in it

  3) Follow pointer to next node and output item

  4) Repeat until end of linked list reached
• What is a graph data structure and its features?

  Data structure made up of nodes/vertices + pointers/edges

  - differs from linked list + binary tree because each vertex can have 2+ edges and point to any vertex in data structure (non-linear)

  - directed graph - edges point in a certain direction (from 1 vertex to another)

  - undirected graph - edges have no specified direction between nodes

  - graphs can be weighted - each edge can be given a value representing the relationship between vertices (e.g. distances)
• How can you implement a graph?

  Most common = adjacency lists (objects/a dictionary)

  Can be stored as adjacency matrixes - 2D array, rows and columns representing vertices and data in each section representing connecting edges

  - rows and columns not usually labelled with vertices
• What are the uses/applications of graphs?

  Mapping road networks for navigation systems

  Storing social media network data

  Resource allocation in OS

  Representing molecular structures + geometry
• What are the standard operations you can perform on a graph?

  Adjacent - returns whether an edge connects 2 vertices or not

  Neighbours - returns all vertices between 2 vertices

  Add/remove vertex

  Add/remove edge

  Get/set vertex value

  Get/set edge value (for weighted graphs only)
• What are the search operations you can perform on a graph?

  Depth-first search - starting at root vertex and visit each vertex/explores each branch before backtracking

  Breadth-first search - starts at root vertex and visits each neighbouring node before moving to vertices at next depth

  
  

  (can also be deemed traversal)
• What are the traversal operations you can perform on a graph/binary tree?

  Pre-order traversal

  In-order traversal - outputs content of data structure in order (sorts structure without need for insertion sort)

  Post-order traversal - used to delete from binary tree/graph

  
  

  (All types of depth first search)
• What are the rules/basic steps for adding to a graph?

  Traverse graph to find specific node you need to connect to, then link the two nodes with an edge/pointer

  
  

  Other steps dependent on graph you are using, what you want to add and current node connections
• What are the rules/basic steps for removing from a graph?

  Traverse graph to find specific node you need to delete, then remove node and any connecting edges to it

  
  

  Like adding, other steps dependent on graph are using and situation
• What are the steps for a breadth-first search?

  Overview = nodes at each level visited and marked/stored before moving onto next level, makes use of queues/FIFO method

  1) Set root vertex as current vertex

  2) Add current vertex to list of visited vertices if not already in it

  3) For every edge connected to vertex

  - if linked vertex not in visited list, enqueue and add to list

  - if in visited list, go to next edge or step 4)

  4) Dequeue and set vertex removed from queue as current vertex

  5) Repeat from 2) until queue empty, then output all visited vertices
• What are the steps for a depth-first search (iterative approach)?

  Overview = edge-based technique, follows each path before backtracking, makes use of stacks and LIFO method

  1) Set root vertex as current vertex

  2) Add current vertex to list of visited vertices if not already in it

  3) Go to every edge connected to current vertex, if linked vertex not in visited list, push to stack and add to visited list

  4) When all linked vertices visited, pop off stack and set removed item as current node

  5) Repeat from 2) until all vertices visited (stack empty), then output visited nodes

  - Outputs can be in different orders depending on which vertex linked to root node the algorithm went to first (most exam boards start at left-most vertex, but all valid nonetheless)
• What are the steps for a depth-first search (recursive approach)?

  Same overview as iterative approach, just different method

  1) Set root vertex as current vertex

  2) Output vertex

  3) Add current vertex to list of visited vertices if not already in it

  4) If vertex has linked vertex that's not visited, follow edge and linked vertex become current vertex

  5) Repeat from step 2) until all vertices visited

  - Like iterative depth-first, outputs can be in different orders depending on which vertex linked to root node the algorithm went to first
• What are the differences between breadth-first search and depth-first search?

  Breadth-first:

  - Uses queue to find shortest path through unweighted graph

  - Reaches nodes with minimum number of edges from source/root node

  - Most suitable for searching nodes close to source

  - Considers all neighbouring nodes first (not good for decision trees)

  
  

  Depth-first:

  - Uses stacks

  - Traverses through several edges to reach destination node from a source

  - Suitable when solutions further away from source

  - Suitable for decision-making - make decision and follow path leading on from that (no consideration of alternative decisions like in breadth-first)
• What is a tree data structure and its features?

  Like a graph, data structure made up of nodes + pointers/edges connecting them, but has a unique 'root node' which serves as the base node all nodes indirectly/directly connect to

  - child nodes - nodes stemming from the root node (but are not the terminating nodes)

  - leaf nodes - the nodes at the bottom of the tree, therefore the terminating nodes

  - subtree - set of nodes/edges from any single node down through its descendants (up until the leaf nodes connecting to it)
• What are the applications/uses for rooted trees?

  Storing and managing file/folder structures

  Implementation of a A* pathfinding algorithm

  Storing and manipulating hierarchal data (that requires a parent node to have 0, 1, or 1+ child nodes)

  - e.g. family trees and corporate structures