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).
They definitely aren't. Compare the efficiency of removing the head of a linked list to removing the first element of an array/arraylist, and you'll understand why they're used. Linked lists take advantage of pointers to efficiently insert and delete nodes. Arrays don't have that luxury because memory is allocated in consecutive blocks, and thus removing an element requires the remaining elements to be shifted.
Its interesting you'd say that. But one factor many people seem to forget is cache misses. ArrayLists are cached to the point that huge portions of the array stay in the cache while using it, while LinkedLists can often lead to many cache misses increasing the time to access quite a bit.
Linked lists consume a lot more memory as well since you ALWAYS pay a 2x penalty when creating a node (3x penalty if you have a doubly linked list like in Java).
Some benchmarks have surprisingly shown ArrayList to beat LinkedList even when you'd expect LinkedList to win (like shift scenarios). I think there's a case to use LinkedList if you do heavy removals in the middle of the list often. But that is an extremely rare use case. Usually the benefits of ArrayList far outweigh LinkedList. Namely:
I uses at lot less memory (so less memory pressure)
Is compact and contiguous so it often fits in the cache and results in a lot less cache misses
Allows for indexed random access
Here's a more detailed analysis if you're interested:
springframework.guru/java-arraylis...
(and this code tests worst case scenarios and doesn't make use of tricks to force the ArrayList to avoid resizing too much)
ps. the case of adding and removing to the head of a linkedlist can often be reproduced by storing your list backwards in an ArrayList and adding/removing from the end. But even in the shift scenario many times ArrayList may win because caches matter!
A lot of the criticisms of linked lists vs ArrayList are language-specific...
In languages like C and Java, arrays (and the underlying arrays in ArrayLists) have to be created with a fixed size. This memory is allocated in a block. If you need to insert more items than your array has, you have to request a larger block of memory and copy things across. You also have the problem where the array is taking up memory even if it's not actually being used, although with modern tech this is largely irrelevant.
The linked list addresses this problem by allowing you to create a list by storing the items in disparate pieces of memory, and storing references. The memory allocation per item is higher, since you also have to store references, but the list can happily grow to any size and has a constant insertion/deletion cost.
The big tradeoff of Linked Lists is that you lose the ability to randomly access the list. If you want the nth element, you have to traverse the entire chain until you get there. This is actually a perfectly good tradeoff for setups where you need to constantly access the first element of the list, like a queue or stack.
Like all data structures, whether it's correct for you depends heavily on your situation. In languages like JavaScript that have dynamic arrays anyway, it's probably not worth thinking about.
But you're forgetting the cache tradeoff.. the cache tradeoff of linked lists vs dynamic arrays (aka. ArrayLists) is considerable.
It can make a very large performance difference if every time you access a new item in the list you have to suffer a cache miss.
Also I don't think these "criticisms" (I prefer comparison) are language specific. Underlying it all is the concept of a fixed block of memory you allocate for an array or for a node. How you do those allocations and what their dispositions in RAM are is very relevant when figuring out the practical performance behaviors.
It may be that Python or Javascript hides this from you by implementing the dynamic array outright, however, its the very selection of the data structures used in these languages that will dictate their performance characteristics.
I'm using Java as an example. But the underlying notions of how you create lists are the same.
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!
They definitely aren't. Compare the efficiency of removing the head of a linked list to removing the first element of an array/arraylist, and you'll understand why they're used. Linked lists take advantage of pointers to efficiently insert and delete nodes. Arrays don't have that luxury because memory is allocated in consecutive blocks, and thus removing an element requires the remaining elements to be shifted.
Its interesting you'd say that. But one factor many people seem to forget is cache misses. ArrayLists are cached to the point that huge portions of the array stay in the cache while using it, while LinkedLists can often lead to many cache misses increasing the time to access quite a bit.
Linked lists consume a lot more memory as well since you ALWAYS pay a 2x penalty when creating a node (3x penalty if you have a doubly linked list like in Java).
Some benchmarks have surprisingly shown ArrayList to beat LinkedList even when you'd expect LinkedList to win (like shift scenarios). I think there's a case to use LinkedList if you do heavy removals in the middle of the list often. But that is an extremely rare use case. Usually the benefits of ArrayList far outweigh LinkedList. Namely:
Here's a more detailed analysis if you're interested:
slideshare.net/jpaumard/linked-to-...
Here's another:
springframework.guru/java-arraylis...
(and this code tests worst case scenarios and doesn't make use of tricks to force the ArrayList to avoid resizing too much)
ps. the case of adding and removing to the head of a linkedlist can often be reproduced by storing your list backwards in an ArrayList and adding/removing from the end. But even in the shift scenario many times ArrayList may win because caches matter!
Did not know about those points!
A lot of the criticisms of linked lists vs ArrayList are language-specific...
In languages like C and Java, arrays (and the underlying arrays in ArrayLists) have to be created with a fixed size. This memory is allocated in a block. If you need to insert more items than your array has, you have to request a larger block of memory and copy things across. You also have the problem where the array is taking up memory even if it's not actually being used, although with modern tech this is largely irrelevant.
The linked list addresses this problem by allowing you to create a list by storing the items in disparate pieces of memory, and storing references. The memory allocation per item is higher, since you also have to store references, but the list can happily grow to any size and has a constant insertion/deletion cost.
The big tradeoff of Linked Lists is that you lose the ability to randomly access the list. If you want the nth element, you have to traverse the entire chain until you get there. This is actually a perfectly good tradeoff for setups where you need to constantly access the first element of the list, like a queue or stack.
Like all data structures, whether it's correct for you depends heavily on your situation. In languages like JavaScript that have dynamic arrays anyway, it's probably not worth thinking about.
But you're forgetting the cache tradeoff.. the cache tradeoff of linked lists vs dynamic arrays (aka. ArrayLists) is considerable.
It can make a very large performance difference if every time you access a new item in the list you have to suffer a cache miss.
Also I don't think these "criticisms" (I prefer comparison) are language specific. Underlying it all is the concept of a fixed block of memory you allocate for an array or for a node. How you do those allocations and what their dispositions in RAM are is very relevant when figuring out the practical performance behaviors.
It may be that Python or Javascript hides this from you by implementing the dynamic array outright, however, its the very selection of the data structures used in these languages that will dictate their performance characteristics.
I'm using Java as an example. But the underlying notions of how you create lists are the same.
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