Are there other advantages to linked lists over arrays other than constant time removals of the first element?
$\begingroup$
$\endgroup$
1
-
11$\begingroup$ Constant time insertion or removal of any element at a known location. Constant time list concatenation or splitting. In-place MergeSort. $\endgroup$– user16034May 13, 2022 at 13:22
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
1
Linked lists can work well even if memory is fragmented. Arrays usually require a continuous piece of memory. For large piece of data finding this large continuous piece of memory might be hard.
Most of benefits of linked lists requires to remember more links than just the head. For example. If you are doing some sequential checks and deletions or insertions, you can keep this link of the last checked element. Then all of this insertions or deletions are O(1), you have all the data needed, and memory required for insert is small. In other words linked lists are good for local operations. Like text. If you would try to implement a text editor and rewrite the whole array when user adds another letter in the middle, it will be slower than with a linked list, if linked list remembers last edit points and most edits are a bit further than it. Upgrade to this idea are skip list and rope.
Another useful feature of links is atomicity of small edits. With an array you could achieve atomicity by replacing the link to the array itself, but only after making a whole new copy. But with linked list you can build another subchain, and then replace the link to it, changing the small portion of the linked list this way, keeping all the data consistent and not spending lots of memory on another copy.
-
7$\begingroup$ That last paragraph is an excellent point. Lock-free techniques such as read-copy-update work extremely well on linked lists if they are mostly read-only. Ask your favourite search engine about it. $\endgroup$– Pseudonym ♦May 13, 2022 at 2:01
$\begingroup$
$\endgroup$
6
This isn't really about "advantages", but appropriateness. Sometimes it's more appropriate to use an array, and sometimes to use a linked list.
If it helps, take a look at this large table of the complexity of various operations of a bunch of data structures from the C++ standard library so you can compare them. If you're not familiar with C++, vector is a growable array, deque is a double-ended queue (essentially a chunked array), and list is a linked list. What you can see is that the main tradeoff is:
- Dereferencing an element of an array, from a position index, is $O(1)$ operation, and linked lists don't really support that.
- Insertion and deletion of an arbitrary element of a linked list is $O(1)$, and $O(n)$ for an array.
answered May 13, 2022 at 1:57
-
5$\begingroup$ note: O(1) if you already have a reference to the position. If you want to insert at position n in a linked list, it's still O(n) because you have to find the position before you can insert. $\endgroup$ May 13, 2022 at 9:22
-
$\begingroup$ @user253751 not if you have a doubly linked list $\endgroup$– RusselMay 13, 2022 at 17:21
-
7$\begingroup$ @Russel You still have to find the position from either direction. $\endgroup$– iBugMay 13, 2022 at 18:52
-
6$\begingroup$ One important thing to note here is that Bjarne himself (as the author of C++) has made a lot vector (array) vs. list comparisons and benchmarks including completely random insert/delete, and realized that you need massive N in order for the linked list to outperform arrays, because the hardware we use are very fast at moving large chunks of memory around compared to randomly following pointers. $\endgroup$– pipeMay 14, 2022 at 7:52
-
3$\begingroup$ @pipe that applies only to trivially moveable objects. Many objects are, but not all. $\endgroup$– ojsMay 15, 2022 at 11:19
$\begingroup$
$\endgroup$
1
An important consideration missing from the other answers: It's easier and more performant to use immutable linked lists than immutable arrays, which is especially important in functional programming languages.
For example, to add an element to an array in an immutable language, you actually create a new array with the extra element added to it, which entails copying the entire array. The compiler might be able to optimize this out (it might detect that the original array is never read again, and just append in-place), but not in general.
Adding an element to an immutable linked list is easy, as long as you're willing to add to the front: Create the new head node, and link it to the old head. The old head still represents the old list, and the new head represents the new list!
This implies another benefit of linked lists: Two lists that differ only in the first few elements can share most of their memory.
-
$\begingroup$ +1. If this is driving your choice of data structure, though, then there are some other purely functional data structures that may be worth considering instead, such as purely functional AVL trees, or such as finger trees. (Though linked lists are definitely simpler, if you don't already have a library handy for one of the others.) $\endgroup$– ruakhMay 16, 2022 at 4:37
$\begingroup$
$\endgroup$
1
If you make the elements stored in the list already contain the next/prev pointers (called an intrinsic or intrusive linked list) than the list doesn't need to do allocations and risk fragmenting memory further just to store 3-pointer sized structs or an array of pointer that needs reshuffling every time you pull out an element.
This is very handy if you expect the elements to move lists frequently and/or a possibly failing allocation means a panic. Like for example the thread descriptor object moving between various wait queues in the kernel depending on why the thread was interrupted.
With an intrinsic list which is doubly linked then if you can acquire a pointer to the object directly then you can pull the object out of the list without needing to find it in the list or array.
answered May 13, 2022 at 13:03
-
$\begingroup$ Re: "called an intrinsic linked list": That phrase gets very few hits on Google. [link] Another term I've encountered for this is "intrusive linked list", which is still pretty rare, but not as rare. I'm not sure if there's a truly common name for this. $\endgroup$– ruakhMay 16, 2022 at 4:31
$\begingroup$
$\endgroup$
4
A linked list is appropriate for many use cases independent of performance considerations. In addition to examples given by other answers here, consider that a given object (an instance) can be in more than one linked list (internally linked as well as externally linked) but can only be in one array (it can be pointed to by multiple arrays, but that's not the same, for many use cases).
Consider these diagrams from the book The Design Of An Optimizing Compiler (Wulf, Johnsson, Weinstock, Hobbs) (1973) - first is the multiply-internally-linked symbol table, second is the multiply-internally-linked "graph table" used for recognizing common subexpressions - the "threads" are multiple semantically different, semantically important traversals of the same data structure implemented by separate linked lists into the same objects each representing a symbol or a syntax tree node.
BTW, IMO it is a design mistake to consider performance of a data structure before considering appropriateness. But I can see that it frequently happens, probably because of the way CS/programming is taught, in many cases by teachers and textbooks, in which performance characteristics are prioritized over appropriateness, and in fact, appropriateness is given short shrift. See for example many industry "interview questions" which are considered properly answered by discussions of O-bounded performance, where the data structure to use is just assumed to be "obvious". Or in many many examples in textbooks, websites, and language libraries that have good support for external data structures (linked lists, arrays, dictionaries, hash tables) and never mention at all much less support internally linked data structures as used above. (Note that as in the diagrams above hash tables and trees can be represented using internal links if that is appropriate - it's just never done anymore not because it is wrong by mainly because there's no language or library support.)
-
1$\begingroup$
can only be in one array (it can be pointed to by multiple arraysThere are (programming) languages where this distinction is valid, in others, it doesn't exist. What you call internally linked has been dubbed intrusive elsewhere. $\endgroup$ May 14, 2022 at 5:33 -
$\begingroup$ An object can't be in more than one list. A reference to it can be in multiple lists, just as it can, as you say, be in multiple arrays. But, as you say, that's not the same thing. $\endgroup$– Rosie FMay 14, 2022 at 5:42
-
$\begingroup$ @greybeard - yes, it is commonly called "intrusive" $\endgroup$– davidbakMay 14, 2022 at 8:39
-
$\begingroup$ @RosieF - yes it can - if you use internally linked lists - as greybeard says commonly called "intrusive" lists - where the links are part of your data structure, then you can have an object participate in as many different linked lists as you need. Not a reference to it, the actual object. Here's a reasonable article that describes it. They used to be very commonly used, as they also save space compared to externally linked lists. You also find them in operating system kernel structures. $\endgroup$– davidbakMay 14, 2022 at 8:42
$\begingroup$
$\endgroup$
Donald Knuth’s “dancing links” algorithm is a well-known one that uses the constant-time insertion and deletion of items in a linked list for performance. You can hear him discuss it, twenty-four years later, here.
An important optimization for linked lists, in a lazy functional language with immutable linked lists, is to treat them just as a sequence and avoid ever actually creating the list itself, compiling to something much like yield return in C#.
$\begingroup$
$\endgroup$
I don't have an exhaustive list (pun intended), but off the top of my head:
- You can also perform constant time operation at the tail (for a circular doubly linked list).
- You can implement the move-to-front heuristic (MTF) efficiently.
- No need to perform costly expansion/contraction (there is a way to prevent this in an array but requires extra memory)
$\begingroup$
$\endgroup$
2
If you mean fixed arrays (whose lengths are fixed in advance) versus linked lists, then linked lists have the advantage that they use up memory only on an as needed basis - a new cell is allocated each time a new insert operation is done. Whereas, arrays would require you to specify the maximum length of the list in advance, and any unused space is wasted, and you can’t insert more elements than this maximum length even if you encounter more data. So, if you don’t know in advance how many elements will be inserted into the list, a linked list would be a better data structure to use.
-
$\begingroup$ Systems with virtual memory can allow efficient growth of arrays without allocate+copy, for example Linux's
mremapsystem call tries to allocate new virtual pages after an existing one. But if there isn't space there, it can (if you let it) also find a big enough range of virtual address space somewhere else, and map the early part of it to the same physical pages holding your data. It's unfortunate that some languages (like C++) make it very inconvenient for an implementation to use that forstd::vector::reserve()for example. $\endgroup$ May 15, 2022 at 16:24 -
$\begingroup$ Of course that only works for large arrays, where page granularity is ok for allocations. Re: failure C++ failure to use
reallocto try to grow even without virtual-memory tricks, see Is it guaranteed that C++ standard library containers call the replaceable new functions?. But those are just C++ implementation details, not theoretical problems with arrays, which can be left room to grow if needed. (But of course for that space not to be wasted, you do eventually have to allocate it to something else, imposing a growth limit.) $\endgroup$ May 15, 2022 at 17:09