Does a linked list have any value in a language which has dynamic arrays?

85 views Asked by At

Does a linked list have any value in a language which has dynamic arrays, such as Python (which, of course, has the list data structure)?

I currently understand a list in python to really just be a static array which, as more data is inserted, redefines itself as a new array (larger in size) copying the data from the old into the new (thus making it dynamic). is this correct?

I also understand how a list and linked list stores data in memory differently (lists in a contiguous manner and linked lists in a non-contiguous manner), but does this provide any major advantages?

1

There are 1 answers

7
Ami Tavory On BEST ANSWER

Yes, it does. Removing a link from a linked list is O(1), while it is linear for a dynamic array.

Suppose you want to build a data structure for an LRU. Typically, you would have a hash-table for "touch" operations, plus a sequence array to see what has aged. When an item is accessed, the hash table finds it in the sequence, and moves it to the end. If an item needs to be evicted, then the first item in the sequence is used to find the item in the hash table, which is then removed.

In this example, using a linked-list for the sequence operation means that everything works in (expected) O(1) time. With dynamic vectors, everything would be linear. Linked lists still have their uses.