Select a data structure that you have seen previously, and discuss its strengths and limitations.
Strengths of Linked List
- Simpler addition and removal of elements, \(O(1)\) time complexity
- Does not need contiguous memory space
- New element can be easily inserted in any location
Limitations of Linked List
- Accessing an element by index or by value means traversing the list, \(O(n)\) time complexity
- Additional memory is required for storing the address (pointer) of the next/previous element.
Strengths of Array
- Accessing any element by index is simple, \(O(1)\) time complexity
- No additional memory required to store address
Limitations of Array
- Addition or removal of elements from any index but the last means re-arranging the whole list, \(O(n)\) time complexity
- Accessing an element by value means traversing the list, \(O(n)\) time complexity
- Needs contiguous memory