4

I'm learning data structures and algorithms using Python. I've learnt that the advantage of linked list is that it does not have a maximum number of nodes, unlike arrays in other languages.

  1. Since Python automatically resizes our lists for us, the advantage has been abstracted away for us.

  2. Therefore, I've always thought that the only advantage linked lists have was that adding a node at the front or back of the linked list was O(1), whereas adding an element to a list could end up being O(n) from Python having to resize the array and copying every element over.

However, I've just learnt that amortized time complexity is a thing today, and that appending to a list takes amortized O(1). So, adding an element to a list is actually quicker than adding a node to a linked list, since adding a node at anywhere other than the front/back of a linked list takes O(n) time complexity.

So then, what is the point of using linked lists over arrays/lists?

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
rank1psysuck
  • 57
  • 2
  • 2
    You don't always want to append to the end of a list. For a task that involves inserting at arbitrary points, or moving items around (e.g. pulling an item off the end and moving it to the start), linked lists are O(1) whereas arrays are O(n). Different data structures have benefits and drawbacks in different situations. Note that this is in no way specific to Python! – Samwise Dec 13 '21 at 15:42
  • 5
    Linked lists are, generally speaking, rarely used these days. With how much caching and readahead modern processors use memory locality is extremely important. Cache misses and page faults are painfully expensive. Linked lists with their non-contiguous access patterns just don't perform well in practice, even if on paper their O(1) operations should be faster than arrays' O(n). – John Kugelman Dec 13 '21 at 15:48
  • There *are* use cases for linked lists, but they're a lot rarer than use cases for dynamic arrays. – user2357112 Dec 13 '21 at 16:13
  • You don't ever in practice use a linked list in Python as a practitioner. The point of understanding linked lists _as a concept_ is so you can recognize and use them if you're writing code in a different, non-Python language. – Charles Duffy Dec 13 '21 at 17:00
  • 1
    @CharlesDuffy [deques use linked lists](https://github.com/python/cpython/blob/9130a4d62032468e0d4949aaa49c29afb0d854ca/Modules/_collectionsmodule.c#L31), are you saying deques aren't used in practice? – Kelly Bundy Dec 14 '21 at 09:49

1 Answers1

3

While it's certainly possible to craft some example where they could be useful (in a contrived case, perhaps an industrial ASIC you're working with requires them), but especially trivial implementations of linked lists largely exist as an example rather than a practical structure, and are often realistically a performance tar pit as they manufacture processor cache misses1, leading to orders of magnitude worse performance than they would appear to on paper

However, they're a great example of

  • a clear, complete, and minimal teaching demonstration of pointers
  • some much more useful, generalizable concepts
    • intermediate data insertion without moving a significant amount of adjacent data is possible
    • it's not necessary to know how long a data structure is to work with it
    • it's often not necessary to immediately store more than where the active and next data is

Linked lists are also potentially useful outside of "hard" computer science, where they may model, for example, biological processes effectively

Notes
1. hunting for a precise example for this, but I recall a great presentation from Google on why they don't use some stdlib internally to prevent accidental use of linked lists and perhaps a few other types due to lowered performance / increased bugs

ti7
  • 16,375
  • 6
  • 40
  • 68
  • Can you explain what you mean by biological processes that are modelled by/as linked lists? I’m somewhat versed in biological network analysis but I don’t understand what you’re referring to. – Konrad Rudolph Dec 13 '21 at 17:19
  • @KonradRudolph Oh, I'm quite jealous and you would certainly know better than I, so it perhaps does not! Still, I suspect some uses of synthetic DNA make sense as a linked list, though likely far more in terms of understanding and studying the behavior and performance of it than how a representation of that same structure would be backed in a computational model! – ti7 Dec 13 '21 at 17:36