Array Vs Linked List Performance : Datastructures
In our previous articles Simple Linked List and Double-Ended List we have seen how fast and easy it is to insert and delete at the beginning of the linked list. You only have to change one or two references as shown in those examples, which takes O(1) time.
Array Vs Linked List Performance
Finding, deleting or inserting next to a specific item requires searching through an average, half the items of the list. This requires O(N) comparisons.
Array also requires O(N) for these operations. But the linked list is faster because nothing needs to be moved when items are inserted or deleted in linked list.
So the efficiency is significant over array if copy takes much longer than comparisons.
Another important advantage of linked list over array is, it uses exactly as much as memory as it needs and can expand to fill all of available memory. Whereas the size of array is fixed when it is created; leads to inefficiency.
Note:
Arraylist and Vector are expandable, but usually expand in fixed-sized increments. This solution is not as efficient when compared to linked list.
Recommended Posts
- Simple Linked List Example
- Double-Ended Lists Example
- Find and delete specified ‘Link’ from Linked List
- Priority Queue: Array Based Example
- Deque: Double-ended queue is a versatile data structure
- Queue No-count approach and Implementation
- Circular Queue using Array (Wrapping Around)
- Reverse a string or word using Stack
- Delimiter Matching using Stack