Exercise 1.1-3

Select a data structure that you have seen previously, and discuss its strengths and limitations.

Strengths of Linked List

1. Simpler addition and removal of elements, \(O(1)\) time complexity
2. Does not need contiguous memory space
3. New element can be easily inserted in any location

Limitations of Linked List

1. Accessing an element by index or by value means traversing the list, \(O(n)\) time complexity
2. Additional memory is required for storing the address (pointer) of the next/previous element.

Strengths of Array

1. Accessing any element by index is simple, \(O(1)\) time complexity
2. No additional memory required to store address

Limitations of Array

1. Addition or removal of elements from any index but the last means re-arranging the whole list, \(O(n)\) time complexity
2. Accessing an element by value means traversing the list, \(O(n)\) time complexity
3. Needs contiguous memory