ArrayList Vs LinkedList in Java

ArrayList and LinkedList are the Collection classes , and both of them implements the List interface. LinkedList implements it with a doubly-linked list while ArrayList implements it with a dynamically re-sizing array.

Search Operation
Manipulation
Behaviour
Memory Overhead

Search Operation

Search Operation in ArrayList is pretty fast when compared to the LinkedList search operation. ArrayList Method get(int index) gives the performance of O(1) while LinkedList performance is O(n). This is because ArrayList allows random access to the elements in the list as it operates on an index-based data structure while LinkedList does not allow random access as it does not have indexes to access elements directly, it has to traverse the list to retrieve or access an element from the list.

Manipulation

Manipulation with ArrayList is slow because it internally uses array. If We need to insert or delete element in ArrayList, it may take O(n), as it internally uses array and we may have to shift elements in case of insertion or deletion. On the other hand manipulation with LinkedList is faster than ArrayList because it uses doubly linked list so no bit shifting is required in memory. If We need to insert or delete element in LinkedList, it will take O(1), as it internally uses doubly.
ArrayList Vs LinkedList in Java

An ArrayList is a simpler data structure than a LinkedList . An ArrayList has a single array of pointers in contiguous memory locations. It only has to be recreated if the array is expanded beyond its allocated size. But, LinkedList consists of a chain of nodes; each node is separated allocated and has front and back pointers to other nodes. So, unless you need to insert in the middle, splice, delete in the middle etc. an ArrayList will usually be faster. It needs less memory allocations, has much better locality of reference (which is important for processor caching) etc.

Behaviour

ArraylList behaves as List as it implements list. LinkedList behaves as List a well as the Queue as it implements List and Queue both.

Memory Overhead

ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbour nodes hence the memory consumption is high in LinkedList comparatively.

ArrayList Implementation

import java.util.*; class TestClass { public static void main (String[] args) { // create an array list Object ArrayList aList = new ArrayList(); aList.add("Sunday"); //adding item aList.add("Monday"); aList.add("Tuesday"); Iterator ir=aList.iterator(); while(ir.hasNext()){ System.out.println(ir.next()); } }

Output

Sunday Monday Tuesday

LinkedList Implementation

import java.util.*; class TestClass { public static void main (String[] args) throws java.lang.Exception { //create a new linked list object LinkedList days = new LinkedList(); // add elements to the linked list days.add("Monday"); days.add("Tuesday"); days.add("Wednesday"); days.add("Thursday"); days.addLast("Friday"); //Display all the contents of the LinkedList Iterator < String > itr=days.iterator(); while(itr.hasNext()){ System.out.println(itr.next()); } /*Add First and Last Element in linked list*/ days.addFirst("Sunday"); days.addLast("Saturday"); System.out.println("After Addition: " + days); //Insert an element in linked list days.add(0, "Days in a Week"); //add start of linked list days.add(4,"Middle"); //add in the middle of linked list days.add(9, "End"); //add in the lst of linked list System.out.println("After Insertion: " + days); } }

Output

Monday Tuesday Wednesday Thursday Friday After Addition: [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday] After Insertion: [Days in a Week, Sunday, Monday, Tuesday, Middle, Wednesday, Thursday, Friday, Saturday, End]

Next : What is the difference between List and Set in Java

Related Topics