Varibale size data structures Flashcards
(19 cards)
Why aren’t fixed-size arrays always sufficient?
Because we often don’t know in advance how much data we’ll need, and predicting the required size is generally undecidable.
What is an Abstract Data Type (ADT)?
A specification of data operations (like add, get, isEmpty) independent of implementation.
What makes a stack different from a queue?
A stack uses LIFO (last-in, first-out); a queue uses FIFO (first-in, first-out).
What is the main advantage of linked lists over arrays?
They can grow dynamically and use non-contiguous memory, making them efficient in fragmented memory environments.
What does each node in a singly linked list contain?
A data item and a reference to the next node.
Why are null pointers dangerous in linked lists?
They can cause NullPointerExceptions if dereferenced; forgetting to check for null is a common bug.
What does loitering mean in memory management?
Holding a reference to an unused object, preventing garbage collection and wasting memory.
How do you prevent loitering in array-based stacks?
Explicitly set the array slot to null after removing an item.
What is the advantage of using a resizable array over a fixed-size one?
It allows the data structure to grow as needed, handling dynamic data sizes.
What is the amortized cost of resizing an array by doubling its size?
O(1) — the cost of resizing is spread across many insertions.
Why is shrinking arrays tricky?
Frequent shrinking can lead to performance degradation; it should be done cautiously, e.g., when the array is <25% full.
How does a circular buffer help implement a queue?
It allows reuse of array space using modular arithmetic, avoiding the need for shifting elements.
What is the typical complexity of linked list operations?
O(1) for add, get, and isEmpty (at head); O(n) for random access.
What are the benefits of linked lists in memory-constrained systems?
They allocate nodes individually and can better utilize fragmented memory.
What is the amortized time complexity of adding to a resizable array?
O(1) — due to occasional resizing.
Why can’t we generally decide the maximum size a program needs?
Because determining program behavior like loop bounds or halting conditions is undecidable.
What happens if you don’t null out references in arrays after removal?
Objects may linger in memory due to loitering, causing memory leaks.
What is the main downside of linked lists?
Slower random access compared to arrays — must traverse linearly.
Why are null pointer bugs common in Java?
Java allows uninitialized references; dereferencing them causes runtime crashes if not checked.
