Data Structures

• A data structure is a way of organising data in a computer so that it can be accessed and modified
• Different data will be best suited to different data structures
• Arrays store multiple items of the same data type under one name
• Arrays are static meaning they have a fixed size
• Indexing is 0-based, meaning the first element will be index 0, the second will be index 1 and so on
• Arrays can have multiple dimensions - this can be visualised with a table or cube
• A 1D array can be used to represent a vector
• A 2D array can be used to represent a matrix
• A record is a collection of fields, which are just variables
• You can store multiple different data types in one record
• A serial file stores data in no order, appending data to the end.
• You can read through a file using the StreamReader class, by passing in the file name including .txt, and then going line by line with .ReadLine()
• You can write to a file using the StreamWriter class, by passing in the file name including .txt, and then writing line by line with .WriteLine()
• A static data structure is fixed in size and cannot grow or shrink when the program is running
• A dynamic data structure has no fixed size - memory can be allocated or de-allocated as needed
• Dynamic can be more efficient than static as there is no risk of memory remaining unused
• Static is easier to program as there is no need to track the size and location of data
• Dynamic may lead to overflow errors if too much data is added, or underflow if they are empty
• Dynamic data structures utilise the heap
• A stack is a last in, first out data structure
• A queue is a first in, first out data structure
• A stack uses a single pointer to track where the last element is
• A queue uses two pointers to track where the front and back of the queue are
• To add an item to a stack, you push it. To remove an item from a stack, you pop it.
• You can look at the top of a stack without removing it by using peek.
• You can add an item to the back of a queue by enqueuing it, and remove an item from the front by dequeuing it
• Before pushing, you must check if the stack is full. Before popping, you must check if the stack is empty.
• When an item is popped, it is not deleted off the stack - the pointer simply moves down and the old data may eventually be overridden
• Must also check to see if a queue is empty or full when adding or removing items
• Rather than shuffling elements up in the queue each time, we can implement a circular queue that wraps back around on itself. If both pointers are at the same position, it's empty. If the tail pointer is one less than the head pointer, it's full.
• In a priority queue, the order of items within the queue is at least partially determined by the priority of each element
• A priority queue may be used by a processor to schedule jobs
• Stacks are used in recursion
• A graph is an abstract data structure that represents complex relationships between items
• A graph contains nodes (or vertices) which are connected by edges (or arcs)
• Graphs can be directed, meaning edges have specific directions. In undirected graphs, all edges are bi-directional.
• Weighted graphs have edges with weight or cost associated with them, which may represent things like time or distance. An unweighted graph has edges with no weighting
• Graphs can be represented as an adjacency matrix or adjacency list
• An adjacency list, eg H: {B:40, D:53, T:31}, is memory efficient but takes longer to parse so is time inefficient. It is best suited for sparse graphs
• An adjacency matrix is time efficient as any edge can be queried easily, but is very memory inefficient as it stores edges that may not exist. It is best suited for dense graphs