Key applications of Arrays?
- Fixed-size sequential data (temperatures, grades)
- Grid/matrix data (game boards, pixels)
- Direct index access needed
- Base for other data structures
Key applications of ArrayLists?
- Dynamic collections (shopping carts)
- Growing lists (todo lists)
- When size is unknown
- Need random access + flexibility
Key applications of Linked Lists?
- Undo/redo features
- Music playlists
- Browser history
- Frequent middle insertions/deletions
Key applications of Stacks?
- Expression evaluation
- Browser back/forward
- Function calls
- Undo/redo operations
Key applications of Queues?
- Task scheduling
- Print spoolers
- Request handling
- Customer service systems
What is an advantage of a circular array queue implementation over an array implemen-
tation where the front of the queue is always stored at index 0?
(a) enqueue() has a better time complexity using a circular array queue
(b) first() has a better time complexity using a circular array queue
(c) dequeue() has a better time complexity using a circular array queue
(d) There is no advantage in using a circular array queue
(c) dequeue() has a better time complexity using a circular array queue
Looking at the options:
a) enqueue() - Same O(1) for both
b) first() - Same O(1) for both
c) dequeue() - O(1) vs O(n), better with circular
d) No advantage - False, there is an advantage
The key advantage of the circular array queue is that dequeue() operations are O(1) instead of O(n), as they don’t require shifting all remaining elements.
What are the Array operation complexities for adding, searching and deleting?
Adding:
End (with space): O(1)
Middle/Start: O(n) [shifting needed]
End (no space): impossible [fixed size]
Search:
By index: O(1)
By value: O(n)
Delete:
End: O(1)
Middle/Start: O(n) [shifting needed]
What are the ArrayList operation complexities?
Add:
End (no resize): O(1)
End (with resize): O(n) [amortized O(1)]
Middle/Start: O(n)
Search:
By index: O(1)
By value: O(n)
Delete:
End: O(1)
Middle/Start: O(n)
What are the LinkedList operation complexities?
Add:
Start: O(1)
End (with tail): O(1)
End (no tail): O(n)
Middle (after finding position): O(1)
Middle (including find): O(n)
Search:
By position: O(n)
By value: O(n)
Delete:
Start: O(1)
End (with tail): O(1)
Middle (after finding): O(1)
Middle (including find): O(n)
What are the Stack operation complexities?
Add:
Push: O(1)
Search:
Top element: O(1)
Other elements: Not supported
Delete:
Pop: O(1)
What are the queue operation complexities?
Add:
Enqueue: O(1)
Search:
Front element: O(1)
Other elements: Not supported
Delete:
Dequeue: O(1)
What are the pros/cons of Arrays
Pros:
* Fast random access O(1)
* Memory efficient
* Cache friendly
Cons:
* Fixed size
* Slow insertions/deletions in middle
* Wastes space if oversized
What are the ArrayList core pros/cons?
Pros:
* Dynamic sizing
* Fast random access O(1)
* Fast add to end
Cons:
* Slow insertions in middle
* Resizing overhead
* More memory than arrays
What are the LinkedList core pros/cons?
Pros:
* Easy insertion/deletion anywhere
* Dynamic size
* No wasted space
Cons:
* No random access
* Extra memory for pointers
* Not cache friendly
What are the stack core pros/cons?
Pros:
* Perfect for LIFO
* Fast push/pop O(1)
* Simple to use
Cons:
* No random access
* LIFO only
* Can’t access middle
What are the queue core pros/cons?
Pros:
* Perfect for FIFO
* Fast enqueue/dequeue O(1)
* Good for ordering
Cons:
* No random access
* FIFO only
* Can’t access middle
