[Introduction to Algorithms, CLRS] Exercise 1.1-3

This is a solution for Introduction to Algorithms. I write this for my study purpose.

1.1-3

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

Answer:

I would like to introduce 2 data structures: singly linked list and array.

Data structure	Strengths	Limitations
Singly linked list	- It does not need sequential space in memory. - We can insert a new element at any place without moving other elements.	- Random access is O(n). - It takes additional memory for the links.
Array	-  Random accesses: We can access any element of an array using the index value and the base address of the array. Every element can be accessed in O(1) time (assuming whole array is in the main memory). - Serial allocation: Usually, the arrays occupy consecutive memory locations for its elements. So, we can delete the array in one step by deallocating the whole memory area at once. Accessing consecutive elements takes fewer disk seeks than say in linked lists(where elements could be scattered across the memory).	- Deleting/Inserting random elements : When we delete a random element in an array we may need to shift all elements ahead of it left by one place - worst case O(n). Same is the case when we are maintaining a sorted array and want to insert a random element. -  Unsorted Array is not good for searching when we have very large number of elements - as we need to perform Linear search - O(n) time. - Static nature : In most languages, array are statically allocated. So, we may end of reserving extra space then needed or we may not be able to add more elements as needed.

source: http://gateoverflow.in/40943/select-structure-previously-discuss-strengths-limitations

http://clrs.skanev.com/01/01/03.html