1

According to what Bjarne Stroustrup said, we must avoid using linked list due to several reasons. No matter how bad linked list is such as cache miss and prefetching issues, in which algorithms or circumstances is linked list the only option or at least much easier to fit the real case?

Community
  • 1
  • 1
Kevin Dong
  • 5,001
  • 9
  • 29
  • 62
  • 1
    Java-targeted thread, but a lot of this applies in general: http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist – Thilo Feb 04 '17 at 08:06
  • @Thilo The thread does not give any possible algorithms that linked list is preferred than other data structures. – Kevin Dong Feb 04 '17 at 08:14
  • Here is another related thread: http://stackoverflow.com/questions/7496251/what-is-the-advantage-of-linked-list-over-an-array-and-vice-versa – Thilo Feb 04 '17 at 08:16
  • 1
    I believe there are always *several* options when choosing a data structure, not just one. It is mostly about knowing each data structure's specific performance characteristics, then choosing an option that suits your situation. That being said, I haven't myself used (doubly) linked lists for maybe more than 15 years. I've found better data structures in pretty much every single situation. – stakx - no longer contributing Feb 04 '17 at 08:17
  • I've always used [doubly connected edge lists](https://en.wikipedia.org/wiki/Doubly_connected_edge_list) for planar graph algorithms. Not sure if that counts as a linked list and there probably are alternative data structures to represent this, but it would still be my first choice. – Vincent van der Weele Feb 04 '17 at 09:11

1 Answers1

0

  • I imagine any kind of lazy list (the tail of which gets evaluated on demand) can only be done as a linked list (unless you already happen to know the length in advance).

  • A (singly-) linked list can be cyclic (completely or at the "tail").

  • Multiple (singly-) linked list can share memory for their tails.

Thilo
  • 257,207
  • 101
  • 511
  • 656