Data Structures

Question 1

Arrays (strengths, weaknesses, worst cases)

Answer 1

Strengths:
- Fast Lookups
- Fast Appends

Weaknesses:
- Fixed size
- Costly inserts and deletes (have to “scoot over” the other elements)

Worst Case:
space: O(n)
lookup: O(1)
append: O(1)
insert: O(n)
delete: O(n)

Question 2

Queue

Answer 2

Stores items in a first-in, first-out (FIFO) order

Worst Cases:
* space - O(n)
* enqueue - O(1)
* dequeue - O(1)
* peek - O(1)

Strengths:
* Fast operations - All queue operations take constant time O(1)

Uses:
* Breadth-first search uses a queue to keep track of the nodes to visit next
* Printers use queues to manage jobs
* Web servers use queues to manage requests
* Processes wait in the CPU scheduler’s queue for their turn to run

Implementation:
* Queues are easy to implement with Linked Lists:

• To enqueue, insert at the tail of the linked list
• To dequeue, remove at the head of the linked list

Question 3

Stack

Answer 3

A stack stores items in last-in, first-out (LIFO) order.

Think “dirty dishes”

Worst Cases:
* space - O(n)
* push - O(1)
* pop - O(1)
* peek - O(1)

Strengths:
* Fast operations - all stack operations take O(1) time

Uses:
* The call stack - the stack that tracks function calls in a program.
* Depth-first search
* String parsing

Implementation:
* Linked List - insert at head (push); remove at head (pop)
* Dynamic Array - append (push); remove last element (pop)