Fundamental of Data Structures - C2 Flashcards
(13 cards)
Define an array
An array is a fixed-size, indexed data structure that stores a collection of elements of the same data type, in contiguous memory locations.
Describe a static data structure, name a disadvantage, and list two examples
- They allocated a set amount of memory, which is fixed and cannot be changed, usually defined by the programmer.
- Accessing individual elements of data within the data structure are very quick because their memory location is fixed.
- They will still take up memory even if the data structure is empty and not holding any data.
- Records and arrays.
Describe a dynamic data structure, name a advantage, and list three examples
- The amount of memory they use varies based on their need.
- They take memory as and when needed from a heap.
- Much more efficient and flexible, elements can be add/removed quicker.
- Stacks, queues, binary trees.
Compare static and dynamic data structures
Static data structures:
-Memory is allocated at compile-time and may be wasted (inefficient).
-Fast access: memory addresses are fixed and contiguous.
-Fixed size: easier to predict and manage.
-The relationship between elements is fixed and doesn’t change.
Dynamic data structures:
- Memory is allocated at runtime, making it more efficient.
-Slower access: memory may be scattered (non-contiguous).
-Can grow/shrink: need extra mechanisms to track size.
-Relationships between elements can change during execution.
Describe a stack
A stack is a Last In, First Out (LIFO) data structure where the most recently added item is the first to be removed.
Data is added using pushing and removed using popping.
- Pushing = adding an item to the top of the stack
- Popping = removing the top item from the stack
- Peek = viewing the top item without removing it
- A stack pointer keeps track of the index of the current top item
- Stacks are used in recursion, undo features, and expression evaluation (RPN).
Describe stack overflow vs underflow
A stack overflow or underflow typically occurs in a static stack, where the size is fixed in advance.
-Overflow happens when pushing to a full stack.
- Underflow happens when popping from an empty stack.
In a dynamic stack (like one using a linked list), overflow usually doesn’t occur unless system memory is exhausted.
Describe a queue
A queue is a First In, First Out (FIFO) data structure where the first item added is the first to be removed.
Data is added at the rear and removed from the front.
- Enqueue = adding an item to the rear of the queue.
- Dequeue = removing an item from the front of the queue.
- A queue pointer keeps track of the front and rear positions.
- Queues can be linear, circular, or priority-based.
- Used in scheduling, buffering, and print queues.
What should you look out for when making an adjacency matrix for weighted graph?
Remember, instead of writing 0s you write the infinity sign for weighted graphs, and instead of 1s you write the weights (e.g. 30)
Adjacency list vs Adjacency Matrix
Adjacency List:
- Only stores data where there is an adjacency (edge), so requires less memory.
- The list has to be parsed to identify whether particular adjacencies exist, which increases the time taken to process the data.
- Where there are not that many edges (few adjacencies), this method would be more suitable for the reasons stated above. This is known as a sparse graph.
Adjacency Matrix:
- Stores a value for every combination of node adjacencies, so requires more memory.
- Adjacencies can be identified more quickly as every combination is already stored. Effectively, the matrix forms a look-up table of each node to every other node.
- Where there are many edges (lots of adjacencies), this method would be more suitable for the reasons stated above. This is known as a dense graph.
Describe a ‘tree’, and what are they useful for?
- Graph where every node must be connected, and all connections are undirected. There must be no cycles or loops.
- They are useful for storing data with an inherent hierarchical structure, e.g. family trees, file directories.
- They are dynamic, so it’s easy to add/delete nodes.
What is a binary tree and how is it implemented?
- A binary tree is a hierarchical data structure where each node has at most two children: a left and a right child.
- It is commonly used for searching, sorting, and hierarchical storage.
Describe a circular queue
- The rear and front wrap around to the beginning of the queue when they reach the end of the allocated space.
- A front and rear pointer keep track of positions and wrap around using modulo arithmetic
- Prevents unused slots after dequeues — perfect for systems with constant cycling data.
- Makes efficient use of fixed-size memory (no wasted space when queue wraps)
- Used in memory-limited systems, buffering, and real-time scheduling
