Array List
|
Linked List
|
1) ArrayList implements
it with a dynamically re-sizing array.
|
1) LinkedList
implements it with a doubly-linked list.
|
2)
There is no descendingIterator() in ArrayList , so we need to write our own
code to iterate over the ArrayList in reverse direction.
|
2)
LinkedList can be iterated in reverse direction using descendingIterator()
|
3)
If the constructor is not overloaded , then ArrayList creates an empty list
of initial capacity 10
|
3)
LinkedList only constructs the empty list without any initial capacity.
|
4)
In ArrayList each index only holds the actual object(data).
|
4)
Memory overhead in LinkedList is more as LinkedList needs to maintain the
addresses of next and previous node.
|
5)
Performance
get(int
index) is O(1) <--- main benefit of ArrayList<E>
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)
|
5)
Performance
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) <---
main benefit of LinkedList<E>
ListIterator.add(E
element) is O(1) <--- main benefit of LinkedList<E>
|
When
to Use ArrayList and LinkedList :
In real world applications, you will more frequently
use ArrayList than LinkedList. But in very specific situations LinkedList can
be preferred.
1. ArrayList is preferred when there are more get(int) or search operations need to be performed as every search operation runtime is O(1).
2. If application requires more insert(int), delete(int) operations then the get(int) operations then LinkedList is preferred as they do not need to maintain back and forth like arraylist to preserve continues indices.
1. ArrayList is preferred when there are more get(int) or search operations need to be performed as every search operation runtime is O(1).
2. If application requires more insert(int), delete(int) operations then the get(int) operations then LinkedList is preferred as they do not need to maintain back and forth like arraylist to preserve continues indices.
public class ArrayLinkedList {
public static void main(String[] args) {
/*
* transient Object[] elementData= DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
//
* non-private to simplify nested
class access private static final
* Object[]
DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
* Constructs an empty list with an
initial capacity of 10.
*/
ArrayList arrayList = new ArrayList();
arrayList.add("Life is Awesome");
arrayList.add("Intern is a good movie");
// Doubly LInked list implemented and not singly
implemented
LinkedList<String> linkedList
= new LinkedList<String>();
linkedList.add("Life is Awesome");
linkedList.add("Intern is a beautiful
movie");
System.out.println("ArrayList is "+ arrayList);
System.out.println("LinkedList is "+ linkedList);
}
}
Output:
ArrayList is [Life is Awesome, Intern is a good movie]
LinkedList is [Life is Awesome, Intern is a beautiful
movie]
