Linear Data Structures

Question 1

Key applications of Arrays?

Answer 1

• Fixed-size sequential data (temperatures, grades)
• Grid/matrix data (game boards, pixels)
• Direct index access needed
• Base for other data structures

Question 2

Key applications of ArrayLists?

Answer 2

• Dynamic collections (shopping carts)
• Growing lists (todo lists)
• When size is unknown
• Need random access + flexibility

Question 3

Key applications of Linked Lists?

Answer 3

• Undo/redo features
• Music playlists
• Browser history
• Frequent middle insertions/deletions

Question 4

Key applications of Stacks?

Answer 4

• Expression evaluation
• Browser back/forward
• Function calls
• Undo/redo operations

Question 5

Key applications of Queues?

Answer 5

• Task scheduling
• Print spoolers
• Request handling
• Customer service systems

Question 6

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

Answer 6

(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.

Question 7

What are the Array operation complexities for adding, searching and deleting?

Answer 7

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]

Question 8

What are the ArrayList operation complexities?

Answer 8

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)

Question 9

What are the LinkedList operation complexities?

Answer 9

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)

Question 10

What are the Stack operation complexities?

Answer 10

Add:
Push: O(1)

Search:
Top element: O(1)
Other elements: Not supported

Delete:
Pop: O(1)

Question 11

What are the queue operation complexities?

Answer 11

Add:
Enqueue: O(1)

Search:
Front element: O(1)
Other elements: Not supported

Delete:
Dequeue: O(1)

Question 12

What are the pros/cons of Arrays

Answer 12

Pros:
* Fast random access O(1)
* Memory efficient
* Cache friendly
Cons:
* Fixed size
* Slow insertions/deletions in middle
* Wastes space if oversized

Question 13

What are the ArrayList core pros/cons?

Answer 13

Pros:
* Dynamic sizing
* Fast random access O(1)
* Fast add to end
Cons:
* Slow insertions in middle
* Resizing overhead
* More memory than arrays

Question 14

What are the LinkedList core pros/cons?

Answer 14

Pros:
* Easy insertion/deletion anywhere
* Dynamic size
* No wasted space
Cons:
* No random access
* Extra memory for pointers
* Not cache friendly

Question 15

What are the stack core pros/cons?

Answer 15

Pros:
* Perfect for LIFO
* Fast push/pop O(1)
* Simple to use
Cons:
* No random access
* LIFO only
* Can’t access middle

Question 16

What are the queue core pros/cons?

Answer 16

Pros:
* Perfect for FIFO
* Fast enqueue/dequeue O(1)
* Good for ordering
Cons:
* No random access
* FIFO only
* Can’t access middle