Quick Summary Data Structures

Question 1

Array

Answer 1

Strengths:
-Fast lookups
-Fast appends

Weaknesses:
-Fixed size (unless dynamic)
-Costly inserts and deletes

Worst Case
Space: O(n)
Lookup: O(1)
Append: O(1)
Insert: O(n)
Delete: O(n)

Question 2

Hash Table

Answer 2

Strengths:
-Fast lookups
-Flexible keys (most data types can be used)

Weaknesses:
-Slow worst-case lookup
-Unordered
-Single-directional lookups (looking up key given value is O(n))
-Not cache friendly (often use linked lists, which don’t put data next to each other in memory)

Average Case
Space: O(n)
Lookup: O(1)
Insert: O(1)
Delete: O(1)

Worst Case
Space: O(n)
Lookup: O(n)
Insert: O(n)
Delete: O(n)

Question 3

Linked List

Answer 3

Strengths:
-Fast operations on the ends
-Flexible size

Weaknesses:
-Costly lookups

Worst Case
Space: O(n)
Prepend: O(1)
Append: O(1)
Lookup: O(n)
Insert: O(n)
Delete: O(n)

Question 4

Queue

Answer 4

Strengths:
-Fast operations

Uses:
-Breadth-first search
-Printers
-Web servers
-Processes (CPU scheduler)

Worst Case
Space: O(n)
Enqueue: O(1)
Dequeue: O(1)
peek: O(1)

Question 5

Stack

Answer 5

Strengths:
-Fast Operations

Uses:
-Call stack
-Depth-first search
-String parsing

Can make with linked list or array- push/pop or insert/remove head

Worst Case
Space: O()
Push: O(1)
Pop: O(1)
peek: O(1)

Question 6

Binary Tree