Functional programming languages heavily use linked lists because of immutability. If you need to add an item to the list, you can create a new tail and re-use the existing list. It's extremely good for performance. Also, head/tail pattern matching works really well on linked lists.
Also another way to implement "linked lists" is to create two arrays:
values = [5,6,2,4,8]
next = [1,2,3,4, null]
Here the next array basically stores the pointers to the next "node".
My parallel processing professor says this is the "correct way" to do linked lists because it allows much greater levels of concurrency. But really its kind of a hybrid between the array list / dynamic array and the classical disjoint linked list approach. One big advantage is its MUCH better cache behavior and its ability to store the data in a compact form that is better with the cache.
Finally, this approach allows you to have several "next" arrays holding links in different order (which is useful for atomic behavior during parallel or concurrent processing).
Conceptually, linked lists are a good first step for learning trees/graphs (and hashmap implementation).
Practically, linked lists are essentially useless unless you're doing interviews or some niche low level programming.
A *very* seasoned software engineer, I wrote my first basic game, a lunar landing game, in Basic in 1969. Currently I am doing web development in Ruby on Rails, JavaScript, Elm.
I'd say linked lists are overrated. Instead learn about dynamic arrays (aka ArrayLists).
Others to learn are:
For extra credit learn about:
Tell that to a Lisper.
Does Lisp mandate a LinkedList implementation?
Also I don't think the designers of Lisp were very concerned about performance issues, or cache misses, etc..
Functional programming languages heavily use linked lists because of immutability. If you need to add an item to the list, you can create a new tail and re-use the existing list. It's extremely good for performance. Also, head/tail pattern matching works really well on linked lists.
True.. immutability is hard to achieve with a growing dynamic array. Link list implementations do that better.
Linked lists are not over-rated, in fact they provide a conceptual foundation for block-chain (as do graphs)
They've also been used in file systems and skip lists (which are super awesome).
But dynamic arrays often got ignored in intro data structures classes. (Maybe not anymore with the advent of Java)
Also another way to implement "linked lists" is to create two arrays:
values = [5,6,2,4,8]
next = [1,2,3,4, null]
Here the next array basically stores the pointers to the next "node".
My parallel processing professor says this is the "correct way" to do linked lists because it allows much greater levels of concurrency. But really its kind of a hybrid between the array list / dynamic array and the classical disjoint linked list approach. One big advantage is its MUCH better cache behavior and its ability to store the data in a compact form that is better with the cache.
Finally, this approach allows you to have several "next" arrays holding links in different order (which is useful for atomic behavior during parallel or concurrent processing).
This is really cool! Thank you for sharing!
Conceptually, linked lists are a good first step for learning trees/graphs (and hashmap implementation).
Practically, linked lists are essentially useless unless you're doing interviews or some niche low level programming.
reread the first two paragraphs