Still I believe that linked lists are one of the most overrated data structures and that in practice there are very few use cases where they really perform better than dynamic arrays.
The main reason is that modern hardware has very efficient caches and that caching doesn't really work for linked lists.
While it's super efficient (O(1)) to get an item at an index, it's less efficient to insert or delete items from the array -- we would need to move everything to a different block in memory. It's not guaranteed that there's space before or after that array to insert the new item.
True, but caches are extremely good at moving blocks of memory around.
For a long time I believed myself that linked lists have huge advantages when inserting or deleting items and that this makes up for their difficult handling. But after doing some performance testing I did not find any practical case where they actually make sense.
At least I found that to be the case for C++ and Java. It might be different for certain interpreted languages where caching behaves differently.
One case where they do make sense, is sharing the same (potentially very long) tail among various heads. This is useful when you want to trace something that splits up a lot.
In certain edge-cases a combination of both may also be useful; that is, a linked list of arrays. I haven't come across any use case where this really makes sense though.
The main reason I use linked lists are for queue structures where you frequently need to add to the end or pop the beginning, it's very bad if either of these operations are O(n). Instead you can use a simple singly-linked list.
When using a language like Java though, the LinkedList class isn't that good. The entire point of using a LinkedList over an ArrayList is that you can control certain things to make sure that the list operates as efficiently as possible, but Java's implementation doesn't allow for this.
Agreed, especially since dynamic languages pre-allocate space so insertion and deletion is more efficient. They come in most handy for implementing stacks and queues IMO.
One thing that people forget so often is that "linked list" as data structure doesn't have to mean the exact in-memory representation. When you use a LinkedList class, you don't care for its implementation details: it could actually be storing elements sequentially like a traditional array, but exposing only the methods so you see it like a linked list.
When talking about data structures, it's all about the public interface.
When you use a LinkedList class, you don't care for its implementation details
But linked list is the name of a specific implementation of a list. When a class is named LinkedList, I expect it to be implemented this way.
If you don't care about the implementation, it would be better to declare and use an interface named List that is implemented by classes named LinkedList or ArrayList.
Indeed, I should've used the term Abstract Data Type (ADT), not data structure.
Still, I don't think that LinkedList refers to the way it's implemented. For example, it's not uncommon for a tree to be implemented as two arrays: one to hold the index of the parent and the other to store the actual data. Such data structure could still expose all public methods as a tree, and you wouldn't have to know how it's implemented.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
That's a good introduction to linked lists.
Still I believe that linked lists are one of the most overrated data structures and that in practice there are very few use cases where they really perform better than dynamic arrays.
The main reason is that modern hardware has very efficient caches and that caching doesn't really work for linked lists.
True, but caches are extremely good at moving blocks of memory around.
For a long time I believed myself that linked lists have huge advantages when inserting or deleting items and that this makes up for their difficult handling. But after doing some performance testing I did not find any practical case where they actually make sense.
At least I found that to be the case for C++ and Java. It might be different for certain interpreted languages where caching behaves differently.
One case where they do make sense, is sharing the same (potentially very long) tail among various heads. This is useful when you want to trace something that splits up a lot.
In certain edge-cases a combination of both may also be useful; that is, a linked list of arrays. I haven't come across any use case where this really makes sense though.
The main reason I use linked lists are for queue structures where you frequently need to add to the end or pop the beginning, it's very bad if either of these operations are O(n). Instead you can use a simple singly-linked list.
When using a language like Java though, the LinkedList class isn't that good. The entire point of using a LinkedList over an ArrayList is that you can control certain things to make sure that the list operates as efficiently as possible, but Java's implementation doesn't allow for this.
Agreed, especially since dynamic languages pre-allocate space so insertion and deletion is more efficient. They come in most handy for implementing stacks and queues IMO.
One thing that people forget so often is that "linked list" as data structure doesn't have to mean the exact in-memory representation. When you use a
LinkedListclass, you don't care for its implementation details: it could actually be storing elements sequentially like a traditional array, but exposing only the methods so you see it like a linked list.When talking about data structures, it's all about the public interface.
But linked list is the name of a specific implementation of a list. When a class is named
LinkedList, I expect it to be implemented this way.If you don't care about the implementation, it would be better to declare and use an interface named
Listthat is implemented by classes namedLinkedListorArrayList.Indeed, I should've used the term Abstract Data Type (ADT), not data structure.
Still, I don't think that
LinkedListrefers to the way it's implemented. For example, it's not uncommon for a tree to be implemented as two arrays: one to hold the index of the parent and the other to store the actual data. Such data structure could still expose all public methods as a tree, and you wouldn't have to know how it's implemented.