Case Study
Deques (ArrayDeque & LinkedDeque)
2024
- Java
- Data Structures
- JUnit/Testing
Implemented two representations of the Deque abstract data type: an array-based version with front/back indices and a node-based version using sentinel nodes. Focused on correctness, invariants, and performance.
Problem & Motivation:
The provided ArrayListDeque implementation was simple but had degraded performance for some operations. I needed to build two alternative representations of Deque and compare their behavior.
Data & Approach:
- Completed ArrayDeque by using an array where elements do not need to start at index 0 and are positioned based on the front and back fields.
- Identified and fixed the bug in ArrayDeque by reading test failures, forming hypotheses, and tracing through the resize logic.
- Implemented LinkedDeque using two sentinel nodes and maintained the required invariants before and after each method.
- Used the provided DequeTests and checkInvariants method to debug edge cases.
Results:
- ArrayDeque supported constant-time front/back operations without shifting elements, improving performance over ArrayListDeque.
- LinkedDeque maintained correct next/prev relationships and used memory proportional to the number of elements.
- Passed the full test suite, including confusingTest and the runtime experiments.
Limitations:
Does not include additional features like fail-fast iterators; focused strictly on the Deque interface methods defined in the project.