Difference between an array and a linked list
Anónimo
"Not really..we can create an array dynamically as well using malloc.." Eh? Typically, when referring to an array, we assume fixed size. Having a resizable array implies a dynamic array. http://en.wikipedia.org/wiki/Array_data_structure#Array_resizing As for the question: An array is of a fixed size; to expand or shrink an array, you must allocate a new array of the desired size, and copy the elements from the original array, which takes O(n) time and cannot deallocate the original space until copying is done. Whereas in a linked list, you can just add a node to the list in O(1) time at the head (or O(n) time if inserting to the tail without a tail pointer), and requires only the space allocated for the new node. The linked list is less costly for resizing, in this sense (dynamic arrays, however, are amortized O(1)). Secondly, an array is sequential in memory, whereas a linked list consists of pointers, and can be scattered throughout memory. This makes arrays better for caching and localization. Third, an array is always indexed, which makes retrieval/insertion O(1) time, whereas a linked list is O(n) for retrieval, and O(n) for insertion to the tail (without a tail pointer).