- 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 List||Time Complexity||Space Complexity|
|Removing Element||O(n/2), from start or end would be O(1)|
|Retreving Element at Position||O(n/2)|