Array Vs Linked List Performance

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

References

Leave a Reply

avatar
  Subscribe  
Notify of