ArrayList VS Linked List

Both the ArrayList and LinkedList implements the List interface, and they have some differences as well as some similarities between them. The internal working and performance of both vary significantly.

Let’s see both the differences and similarities between ArrayList and LinkedList.

  LinkedList   ArrayList
Elements in the LinkedList are known as nodes, where each node consists of three parts -(1)reference to the previous element, (2)the actual value of the elements and (3) the address to the next element. In the ArrayList element is associated with the index. Because ArrayList is an index based data structure.
We can use LinkedList as ArrayList, Stack, Queue, Singly LinkedList and Doubly LinkedList,  once it is defined. We are unable to use ArrayList as a Stack or Queue.
It requires more memory if we compare it to the ArrayList. Because each node in the LinkedList holds data and reference to the previous and next element in the list. On the other hand, ArrayList requires less memory as compared to LinkedList. Because it holds only actual data and it’s index value.
Inserting and removing an element from the LinkedList is faster than the ArrayList. Because the shifting of the elements is not required after each insertion and deletion, in LinkedList, only the reference of previous and next elements are to be changed. Space and Time Complexity of LinkedList is O(n). Inserting and removing an element in the middle of the ArrayList is very slow. Because after every insertion or deletion, values in the ArrayList need to be shifted. Space and Time Complexity of Arraylist is O(1).
The elements in the LinkedList cannot be accessed randomly. We need to traverse from start to end to reach a particular element. In the ArrayList, the elements can be accessed randomly.
LinkedList is suitable to use for the insertion and deletion of the element than the retrieval. ArrayList is suitable to use more likely for the retrieval of the values than insertion and deletion.

Similarities between LinkedList And ArrayList:

  • LinkedList and ArrayList, both implements the List Interface.
  • Both are Cloneable and Serializable.
  • Both are non-synchronised.

Example code for LinkedList:

Output:

Example code for ArrayList:

Output:

ArrayList VS Vector

Both the ArrayList and Vector implements the List Interface. Both provide simple methods to store and get the object. But they are different in many aspects.

ArrayList Vector
ArrayList is introduced in JDK 1.2 release, so it is not a legacy class. Vector is a legacy class, i.e., it came along with the first version of JDK
To traverse the elements, ArrayList uses iterator interface. Vector uses the Enumeration interface. However, we can also use the Iterator interface to traverse the elements.
ArrayList is non-synchronized, that makes it fast. Vector is slow because it is synchronized. In a multithreading environment, it keeps the other threads in the runnable or non-runnable state until the current thread releases the lock over the object.
If there is no need for the thread-safe operation, ArrayList is a better choice as it gives better performance because of the concurrent processes. If there is a need to perform a thread-safe operation, Vector is the best choice.
Size of the ArrayList grows by half of its size when resized. Size of the Vector increases by double its size by default when resized.
ArrayList is fail-fast due to the iterator. If we modify the ArrayList structure, the iterator will throw ConcurrentModificationException error. But if we modify the vector over enumeration, it does not fail because iterator is fail-fast and enumeration is not.

Sample code to demonstrate the difference in fail-fast behavior of ArrayList and Vector:

Output:

Pin It on Pinterest

Share This