Data Structures Flashcards
Data Structures
Containers within which information is stored
Arrays
- An indexed, finite set of related elements
- Can only contain elements with the same data type
- Can be created in many dimensions
Files
- Used by computers as a series of files
- Made up of records, each comprised of a number of fields
Abstract Data Types
- Don’t exist as data structures in their own right
- Uses other data structures to form a new way of storing data
Queues
- ADT based on an array
- FIFO
- Used in keyboard buffers
Linear Queues
Has 2 points (front and rear)
Circular Queues
A queues where the front and rear pointers can move over the 2 ends of the queue
Queue Operators
Enqueue, Dequeue, IsEmpty, IsFull
Priority Queues
- Items are assigned a priority that determines when they are dequeued
- Uses a FIFO system for items with equal priority
Stacks
- ADT based off an array
- FILO
- Has a single point (the top pointer)
Stack Operations
Push, Pop, Peek, IsFull, IsEmpty
Stack Overflow
Error that occurs when a push command is executed on a full stack
Stack Underflow
Error that occurs when a pop command is executed onto an empty stack
Graph
- ADT used to represent complex relationships between items in a dataset
- Consist of nodes, joined by edges
Weighted Graph
- A graph where each edge has an assigned value
- Represented by adjacency matrices or adjacency lists
Adjacency Matrices
- A tabular representation of a graph
- Each node is assigned a row and column
Adjacency List
- Represents a graph using a list
- Each node has a list of adjacent nodes
Adjacency List vs Matrix
- Adjacency matrices store every possible edge, even those that do not exist
- Adjacency lists are slow to query as each item in a list must be searched sequentially
- Adjacency matrices are suited to dense graphs with high amounts of edges
Tree
A connected, undirected graph with no cycles
Rooted Tree
A tree with a root node
Root Node
The node from which all other nodes stem
Parent Node
A node from which other nodes stem
Child Node
A node with a parent node
Lead Node
A child node with no children
Binary Tree
A rooted node where each parent node has no more than 2 child nodes
Hash Tables
- A way of storing data with constant time complexity
- Uses a hashing algorithm to return a hash
- The hash is the index of the key-value pair
Hashing Algorithm
An algorithm that takes an input and returns a hash
Hash
- Each hash is unique to its input
- They cannot be reversed to retrieve the input value
Collision
- Where different inputs produce the same hash
- Can be avoided by using rehashing
Dictionaries
- Collections of key-value pairs
- Values are accessed by their associated key
Static Data Structures
- Fixed in size
- Declared in memory as a series of sequential, contiguous memory locations
Dynamic Data Structures
- Change in size to store their content
- Store each piece of data alongside a reference to where the next item is stored in memory
