ArrayList vs LinkedList

Question 1

Difference between Arraylist and LinkedList.
(or)
When should we use Arraylist and when should we go for LinkedList?
 

Answer

 
LinkedList and ArrayList are two different implementations of the List interface. LinkedList implements it with a doubly-linked list. ArrayList implements it with a dynamically re-sizing array.
 
LinkedList allows for constant-time insertions or removals using iterators, but only sequential access of elements. In other words, you can walk the list forwards or backwards, but finding a position in the list takes time proportional to the size of the list.
 
ArrayList, on the other hand, allow fast random read access, so you can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap.
 
Adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if you add more elements than the capacity of the underlying array, a new array (1.5 times the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average. So depending on the operations you intend to do, you should choose the implementations accordingly.
 
Iterating over either kind of List is practically equally cheap. (Iterating over an ArrayList is technically faster, but unless you’re doing something really performance-sensitive, you shouldn’t worry about this — they’re both constants.)
 
The main benefits of using a LinkedList arise when you re-use existing iterators to insert and remove elements. These operations can then be done in O(1) by changing the list locally only. In an array list, the remainder of the array needs to be moved (i.e. copied). On the other side, seeking in a LinkedList means following the links in O(n), whereas in an ArrayList the desired position can be computed mathematically and accessed in O(1).
 
Also, if you have large lists, memory usage is also different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored. ArrayLists don’t have this overhead. However, ArrayLists take up as much memory as is allocated for the capacity, regardless of whether elements have actually been added. The default initial capacity of an ArrayList is pretty small (10 from Java 1.4 – 1.8). But since the underlying implementation is an array, the array must be resized if you add a lot of elements.
 

Arraylist retrieving elements(get) compared to LinkedList

 
Arraylist get can be done in O(1) time (constant time) because it’s just an offset memory lookup in an array, internally. A linked list, however, must traverse the list to find that element. This takes O(n) time (linear time).
 
Arraylist maintain indices like arrays. So if want more frequent get operations than put then arraylist is best to go.
 
LinkedList maintain pointers to elements. you can’t to a specific index like in arraylist. Get operations in linkedlist are costly as you would have to go through pointers to reach your elements.
 

Arraylist adding elements compared to LinkedList

 
Put operations in linkedList are good as compared to arraylist. you just need to connect to pointers and that’s it.
 

In which case linkedlist should be preferred ?

 
If you do more insert/remove operations than lookup, linked lists can be better in performance than an arraylist. Conversely, if you are doing more lookup operations, the arraylist will probably give you better performance.

For LinkedList
get(int index) is O(n)
add(E element) is O(1)
add(int index, E element) is O(n)
remove(int index) is O(n)
Iterator.remove() is O(1)
ListIterator.add(E element) is O(1)

For ArrayList
get(int index) is O(1)
add(E element) is O(1) amortized, but O(n) worst-case since the array must be resized and copied
add(int index, E element) is O(n – index) amortized, but O(n) worst-case (as above)
remove(int index) is O(n – index) (i.e. removing last is O(1))
Iterator.remove() is O(n – index)
ListIterator.add(E element) is O(n – index)

 

Question 2

 
Why LinkedList is slower compared to ArrayList when adding to the end of list?
 

Answer

 
This is simply due to the implementation. Have a look at the implementation of ArrayList.add:
 

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

 
An ArrayList internally holds an array whose elements are references to the objects you are managing with that list. The method ensureCapacityInternal simply checks whether this internal array is still large enough to add another element. If so, the element is added and the method returns. This is extremely fast (and – btw – is O(1)). If the array is already full, then a new array with a larger size will be allocated, every reference will be copied from the old array to the new array. Afterwards, the element will be added. This – of course – is O(n). But this happens seldom, and because of the resizing strategy (doubling the size) it will become more and more seldom.
 
On the other hand, let’s have a look at the implementation of LinkedList.add:
 public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

 
Here you see that for each added element a new node object must be created which then is added as the last element. No resizing is done, so that method is always O(1), but the creation of a node object takes more time than simply storing a reference.
 

Question 3

 
Why is add at specific index slower in LinkedLists than in ArrayLists ?
 

Answer

 
The idea of a linked list is to make adding or removing at the end or beginning very cheap… or if you have a reference to a node object already, adding around that or removing it is very cheap too.

To add at an index within a linked list, the implementation first has to navigate to the node at that index… which is an O(n) operation. Once it’s got there, the add is cheap. So adding by index near the start (or end with a smart implementation) is cheap, but adding by index near the middle is expensive.

 

Question 4

 
We say that linkedlist is not an indexed based collection, why?
 

Answer

 
The difference is in the underlying implementation. An array is a fixed-size block of memory divided into chunks, with each chunk holding one element. It’s easy to jump to any individual element using its index number, and modifying one element does not affect the rest of the array.
 
Adding an element to an array is expensive, because you essentially need to copy the entire array into a larger space to make room for the new element. (Adding to the end of the array can be made faster by pre-allocating more space than you actually need, but eventually you would need to copy the entire array again.)
 
A linked list, on the other hand, is made of independent blocks of memory, each of which contains the element to store and a pointer to the next item in the list. Adding to such a list (given a pointer to the location where you want to add) is fast, because you just need to grab a new block of memory and modify the pointers of a small number of nodes, independent of the size of the list as a whole. The cost is that in order to get a pointer to an arbitrary node in the middle, you need to walk the length of the list from the beginning.
 
This is a bit of a simplification, but the main idea is that each underlying data type is suitable for different applications of the abstract concept of a “list”, and you need to consider the types of operations (lookups, additions, deletions, etc) you want to perform before choosing which is more suitable.
 

Question 5

 
Choosing between using a LinkedList or ArrayList for iteration
 

Answer

 
The performance trade-offs between ArrayList and LinkedList have been discussed before, but in short: ArrayList tends to be faster for most real-life usage scenarios. ArrayList will cause less memory fragmentation and will play nicer with the Garbage Collector, it will use up less memory and allow for faster iteration, and it will be faster for insertions that occur at the end of the list. So, as long as the insertions in the list always occur at the last position, there’s no reason to pick LinkedList – ArrayList is sufficient.

 
 

© 2016, https:. All rights reserved. On republishing this post, you must provide link to original post

Leave a Reply.. code can be added in <code> </code> tags