ArrayList VS Linked List
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:
import java.util.*;
public class LinkedList1 {
public static void main (String args []) {
LinkedList<String> al=new LinkedList<String> ();
al.add ("java");
al.add ("python");
al.add ("angular");
al.add ("mongo db");
al.addFirst ("R");
Iterator<String> itr=ar.iterator ();
while (itr.hasNext ()){
System.out.println (itr.next ());
} } }
Output:
R java python angular mongo db
Example code for ArrayList:
import java.util.ArrayList;
public class Arraylist {
public static void main(String[] args)
{
// we will see how to add elements
ArrayList al=new ArrayList();
Object cloneList;
al.add("Android");
al.add("Java");
al.add("Arrays");
System.out.println("Size of arraylist:"+ al.size());//It will show the size of the array
System.out.println("Content of al:"+al);//It will show the contents of the array
al.remove("Java");//It will remove java from the list
System.out.println("Size of arraylist after deletion:"+al.size());
System.out.println("Content of al:"+al);//prints content after deletion
cloneList=al.clone();//It will clone the present element in the list
System.out.println("Elements in the cloned list are:"+cloneList);
al.clear();//It will clear the ArrayList
System.out.println("Arraylist after clear:"+al);
}
}
Output:
Size of arraylist:3 Content of al:[Android, Java, Arrays] Size of arraylist after deletion:2 Content of al:[Android, Arrays] Elements in the cloned list are:[Android, Arrays] Arraylist after clear:[]
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:
import java.util.*;
class FailFastDemo {
public static void main(String[] args)
{
//Initializing vector and storing the elements as array
Vector<String> vector = new Vector<>(Arrays.asList("Java","Oracle","Spring"));
//Using Enumeration for traversing
Enumeration<String> vectorEnum = vector.elements();
//Modifying the structure of vector
while(vectorEnum.hasMoreElements()) {
String value = vectorEnum.nextElement();
if("Spring".equals(value)) {
vector.add("Hibernate");
}
//printing the elements after modification
System.out.println(value);
}
System.out.println("----------------");
//Initializing ArrayList
ArrayList<String> list = new ArrayList<>(Arrays.asList("Java","Oracle","Spring"));
//Initializing iterator for traversing
Iterator<String> listItr = list.iterator();
//modifying the ArrayList
while(listItr.hasNext()) {
String value = listItr.next();
if("Oracle".equals(value)) {
list.add("SQL");
}
//printing the values
System.out.println(value);
}
}
}
Output:
Java Oracle Spring Hibernate ---------------- Java Oracle Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$Itr.checkForComodification(Unknown Source) at java.util.ArrayList$Itr.next(Unknown Source) at StackJava.main(StackJava.java:33)