02. Lists, Stacks, and Queues

Question 1

What are the main ways to implement a list?

Answer 1

Array (resizable, which is a vector)

Linked List
Singly Linked List
Doubly Linked List

Question 2

Runtimes of Linked List vs. Arrays

Answer 2

http://prntscr.com/jfybax

Question 3

Array Resize Strategy

Answer 3

Make sure that the resize strategy for an array is to double the size of the array each time, or else the cost for inserting goes up.

O(1)* cost per insert() if the resize strategy is to double the array each time

O(n)* if resize strategy is to incrementally increase the size of the array by 2 each time.

Also remember that it takes O(n) time to update an element in a Linked List, but O(1) in an array.