3 ms·
Right. 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
by smarks 4y ago
Right. 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.)