2 ms·
I suspect the problem is that many people think of stuff like Java's LinkedList when they think of linked lists. As a standard list implementation, I think it
by taeric 4y ago
I suspect the problem is that many people think of stuff like Java's LinkedList when they think of linked lists. As a standard list implementation, I think it is easy to see that a doubly linked list just isn't that strong. Especially with how cumbersome the List interface makes it to take advantage of the links.
That said, conceptually, linked items are everywhere; such that you can easily find how to list things following the links. You probably just don't bother keeping that in a "List" structure in your code.
- xxs 4y agoLinkedList is useless in Java. Aside the lock free version of them, Linked Lists are better avoided in any language (Few exceptions)
- taeric 4y agoI'll forever think of this tweet when I see java's LinkeList. https://twitter.com/joshbloch/status/583813919019573248 https://twitter.com/joshbloch/status/583813919019573248 Funny, as I constantly have to tell folks to not bother using it at the office. Everyone always assumes it has to be faster than arraylist for whatever they happen to be doing this time. I think the vast majority of the time it flat doesn't matter, but I also fully expect LinkedList will lose most speed tests.
- xxs 4y agoLinkedList is terrible as the memory overhead is way too high - if you need something better use an ArrayDeque.
- smarks 4y agoRight. The main problem is that Java's List interface affords access by int index, making it seem array-like. Unfortunately get(i) on a LinkedList is O(n). This turns apparently innocuous things quadratic, like looping over a list by index.
- xxs 4y agoNothing to do with the interface - only java.util.RandomAccess guarantees O(1). Iterations using get(int) is a mistake regardless, stick to the java.util.iterator or ListIterator it you need the index. The main issue w/ the LinkedList is its memory footprint (aside being LinkedList w/ an indirection on each access), along with the increased GC costs (the GC has to iterate the nodes too, cache misses - gc pauses), even half empty ArrayList is more memory friendly than any LinkedList. ArrayDeque offers 'adds' at the both ends, if you wish to use LinkedList as a queue.
- smarks 4y agoAgreed that LinkedList memory footprint and locality are serious issues. Fundamentally though the problem is that the LinkedList implementation is at odds with the abstraction provided by List -- access by index. Certainly, straight iteration of every element is better done by a for-each loop (which uses an Iterator under the covers). But the availability of indexed access leads one to use it for a variety of additional circumstances. Consider for example processing every even-numbered element, or finding an element that meets some criterion and then operating on an adjacent element. Iterating over indexes for cases like these is quite natural given the List API. (ListIterator can be used for this sort of stuff, but it's quite cumbersome, and sometimes it doesn't actually help.)
- _ea1k 4y agoI run into people that use LinkedList everywhere in their code "for efficiency". It always confuses me. Are CS professors teaching something that leads to this? In practice, it seems unusual for it to have any advantages over just using an ArrayList in typical JVM applications.
- taeric 4y agoI blame an over reliance on Big O as an arbiter of what is a fast algorithm. Linked lists are commonly taught as having much better insertion speed than arrays. This ignores constant factors and cache coherency, of course. More, it also ignores that most lists that folks will make have a VERY predictable access pattern. Typically just a one way scan, if any traversal at all. With very few inserts, and mostly just appending.
- Narishma 4y agoCache locality, not coherency.