• Internally implemented as doubly linked list

The Problem of Linked-List

Unlike array, which is a cache-friendly data structure because its elements are placed right next to each other, elements of linked-list can be placed anywhere in the memory. So when iterating through linked-list, it will cause a lot of cache miss (since we can’t make use of locality of reference), and introduce lots of performance overheads.

Complexity of Linked List

Linked ListTime ComplexitySpace Complexity
Adding ElementO(1)
Removing ElementO(n/2), from start or end would be O(1)
Iterating ElementsO(n)
Retreving Element at PositionO(n/2)

Leave a Comment