Lists and Linked Lists

Question 1

Lists

Answer 1

• an expandable array
• indexes contents
• automatically resizes its array
• resizings are kept to a minimum by increasing the size more than needed

Question 2

Amortized time

Answer 2

• as the list increases in size, the time spent copying arrays over is less than the actual number of elements
• Resizing is O(n) but as the number of resizing increases, the time until the next one is reduced and the time cost having to resize decreases.

Question 3

List Resizing time

Answer 3

• worst-case O(n)

- Expected O(1)

Question 4

Linked Lists

Answer 4

• expandable like a list
• no backed by an array, no memory adjacency
• node based data-structure
• node holds value of the actual element and store memory address of the next node in the list
• inserts and deletes are O(1)
• Searching is O(n)