java - When to use LinkedList over ArrayList? -

i've been 1 use:

list<string> names = new arraylist<string>(); 

i use interface type name portability, when ask questions such these can rework code.

when should linkedlist used on arraylist , vice-versa?

tl;dr arraylist arraydeque preferable in much more use-cases linkedlist. not sure — start arraylist.

---

linkedlist , arraylist 2 different implementations of list interface. linkedlist implements doubly-linked list. arraylist implements dynamically re-sizing array.

as standard linked list , array operations, various methods have different algorithmic runtimes.

for linkedlist<e>

• get(int index) o(n/4) average
• add(e element) o(1)
• add(int index, e element) o(n/4) average
       but o(1) when index = 0 <--- main benefit of linkedlist<e>
• remove(int index) o(n/4) average
• iterator.remove() o(1) <--- main benefit of linkedlist<e>
• listiterator.add(e element) o(1) <--- main benefit of linkedlist<e>

^{note: o(n/4) average, o(1) best case (e.g. index = 0), o(n/2) worst case (middle of list)}

for arraylist<e>

• get(int index) o(1) <--- main benefit of arraylist<e>
• add(e element) o(1) amortized, o(n) worst-case since array must resized , copied
• add(int index, e element) o(n/2) average
• remove(int index) o(n/2) average
• iterator.remove() o(n/2) average
• listiterator.add(e element) o(n/2) average

^{note: o(n/2) average, o(1) best case (end of list), o(n) worst case (start of list)}

linkedlist<e> allows constant-time insertions or removals using iterators, sequential access of elements. in other words, can walk list forwards or backwards, finding position in list takes time proportional size of list. javadoc says "operations index list traverse list beginning or end, whichever closer", methods o(n/4) on average, though o(1) index = 0.

arraylist<e>, on other hand, allow fast random read access, can grab element in constant time. adding or removing anywhere end requires shifting latter elements over, either make opening or fill gap. also, if add more elements capacity of underlying array, new array (1.5 times size) allocated, , old array copied new one, adding arraylist o(n) in worst case constant on average.

so depending on operations intend do, should choose implementations accordingly. iterating on either kind of list practically equally cheap. (iterating on arraylist technically faster, unless you're doing performance-sensitive, shouldn't worry -- they're both constants.)

the main benefits of using linkedlist arise when re-use existing iterators insert , remove elements. these operations can done in o(1) changing list locally only. in array list, remainder of array needs moved (i.e. copied). on other side, seeking in linkedlist means following links in o(n/2) worst case, whereas in arraylist desired position can computed mathematically , accessed in o(1).

another benefit of using linkedlist arise when add or remove head of list, since operations o(1), while o(n) arraylist. note arraydeque may alternative linkedlist adding , removing head, not list.

also, if have large lists, keep in mind memory usage different. each element of linkedlist has more overhead since pointers next , previous elements stored. arraylists don't have overhead. however, arraylists take memory allocated capacity, regardless of whether elements have been added.

the default initial capacity of arraylist pretty small (10 java 1.4 - 1.8). since underlying implementation array, array must resized if add lot of elements. avoid high cost of resizing when know you're going add lot of elements, construct arraylist higher initial capacity.