Arrays: 1)Accessing/Searching : fast due to random access of any element in array (remember address of array element will be computed as base address + offset, so its just memory fetch along with one addition operation) — O(1)
2)Inserting/Deleting at end — fast — O(1)
3)Even sequential access on arrays are fast — due to locality of reference, for linked lists this may not well applied
1) The size of the array is fixed. Most often this size is specified at compile time however the size of the array can be deferred until the array is created at runtime (from heap), but after that it remains fixed. This causes to waste memory eventhough e may not use.
2) Inserting/Deleting elements at the front is potentially expensive because existing elements need to be shifted over to make room — O(n)
3)When array was full, to insert more data, it need to be resized, this operation is quite expensive, even may not be possible if in case memory got fragmented. Linked lists performs well where arrays fail to do it.
Linked Lists: 1)Accessing/Searching: sequential access - O(n)
2)Inserting/Deleting at the end — fast — O(1)
3)Inserting/Deleting at the beginning — fast — O(1)
4)It makes good persistent data structure (because two or more lists can have a common tail, so several versions of a data can be maintained, new data comes at the beginning of a new list)
5)No space problems, memory effectively used.
6)Inserting/Deleting in the middle — O(n)
7)can not make use of locality of reference
reference: http://www.cpp-programming.net/c-tidbits/linked-lists/
http://stackoverflow.com/questions/166884/array-vs-linked-list
ไม่มีความคิดเห็น:
แสดงความคิดเห็น