CODEWITHSUNDEEP
pythonarrayslistdata-structureslinked-list
rank1psysuck
rank1psysuck

Reputation: 57

When are linked lists preferred over lists?

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?

Upvotes: 4

Views: 1427

Answers (1)

ti7
ti7

Reputation: 18930

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

Upvotes: 3

Related Questions