ArrayList vs LinkedList in Java

Introduction

Have you ever come across a situation where you were expected to store similar details of an object ? Example marks of students studying in your class or salaries of employees working in your office. Also you should not face any difficulty in searching and updating the existing values.

In such situations where we need to store multiple values of the same data type and we also need to access and modify it efficiently we mostly use Arraylist and Linkedlist. If we use the conventional file system for the same purpose then we do not have a track of all the values stored. If we want to update/search any existing data we would need to search the complete data stored.

Storing data in data structures provided in the programming languages enables us to overcome all these difficulties and reduce both human effort and time complexity of the processes. These data structures allow us fast search, insertion and deletion of the objects stored. These data structures can also be used to store the data in file systems through file handling. This helps us to maintain a data recovery operation in case our system crashes.

On studying both of them we observe both of them are providing us the same functionality w. Such as the data is stored linearly in both of them, they store values of the same data type in them. In this article we will be studying the fine details of both ArrayList and LinkedList that distinguish them and make a big difference between them.

Both Araylist and Linkedlist are a part of the Collections Framework in java.

The Collections Framework in Java is a framework that provides an architecture to store and manipulate the group of objects. Java Collections enable us to easily perform all the general operations on the objects stored in the structures. on data such as searching, sorting, insertion, manipulation, and deletion.

What is ArrayList?

Arraylist is a class which is a part of the Collections Frameworks in java. It implements the List interface hence all the methods of the List class can be used here. We need to import the java.util package for using the Arraylist class.

As the name suggests ArrayList provides us with a dynamic array( resizable array which can change its size whenever required) for storing data items of the same data type. The Arraylist implemented here is different from the fixed sized array in terms of size and speed as well.

Working of an ArrayList

When ArrayList is declared in the program the JVM(Java Virtual Machine) allocates a memory block of contiguous memory locations according to the size given in the declaration. While filling the ArrayList just when 75% of the ArrayList gets filled a new and bigger memory block is allocated and all the previous values are copied to it.

The ArrayList is a part of the collections framework in Java .They are present in the java.util package in Java. They implement the list interface that allows us to work on a dynamic array that increases its size whenever needed. This array is slower than the conventional static size array. This makes ArrayList analogous to vectors in C++.

Syntax:

An arraylist can be dynamically declared using the following syntax

ArrayList<data_type> name = new ArrayList<data_type>();

Inserting data in the ArrayList

We can insert new values into the ArrayList either at a specific position in the or at the end of the existing Arraylist just like vectors in C++.

For inserting new elements we have two methods which are both named ‘add’. Furthermore add(object) – It adds the given object at the end of the list

add(int index,object) – It adds the given object at the index specified in the argument. The elements from the given index upto the end are shifted right in order to create space. After this process the element is assigned to the index. This overhead makes the overall process’ time complexity large to O(N) where N is the size of the list.

ArrayList<String> values = new ArrayList<String>();
        values.add("apple");
        values.add("boy");
        values.add("cat");
        values.add("dog");
        values.add("elephant");
        //apple boy cat dog elephant
        values.add(1,"xyz");
        //apple xyz boy cat dog elephant

Accessing and Searching values in the ArrayList

The objects stored in the ArrayList can be accessed by the index where they are stored in the list using the ‘get’ method function.

get(int index) – This function returns the object stored at the given index in the list. This method takes constant time, due to the use of indices this process is very fast.

for(int i=0;i<values.size();i++){
            System.out.print(values.get(i));
        }
        //apple xyz boy cat dog elephant
        System.out.println();
        for(String temp: values){
            System.out.print(temp);
        }
        //apple xyz boy cat dog elephant
        Iterator<String> itr=values.iterator();  
        while(itr.hasNext()){ 
         System.out.print(itr.next());
        }
        //apple xyz boy cat dog elephant

Modifying the ArrayList

The objects in the ArrayList can be modified using the ‘set’ method function. This function assigns a new value to the index which it refers to.

set(int index,object) – The new object in the argument is assigned to the vector at the given index.

//apple xyz boy cat dog elephant
values.set(1,"girl");
//apple girl boy cat dog elephant

Deleting in the ArrayList

The objects in the ArrayList can be deleted using two functions both named ‘remove’.

remove(object) – This function deletes the given object in the ArrayList. If the object appears multiple times then the first occurrence of the object is deleted.
remove(int index) – This function deletes the data value stored at a given index. After doing so all the elements that lie on the right of the deleted element are shifted to left. This overhead makes the overall process’ time complexity large to O(N) where N is the size of the list.

//apple xyz boy cat dog elephant
        values.remove(1);
        //apple boy cat dog elephant
        values.remove("dog");
        //apple boy cat elephant

What is LinkedList?

LinkedList are also linear data structures like ArrayList. Here we are not required to specify any size. The objects stored here are not stored in contiguous memory locations like ArrayList. A LinkedList is made up of ‘nodes’. These nodes are the building blocks of the LinkedList just like the cells of an array. A node stores the object data as well as the next node’s address in its p address field.

There are 2 types of Linked List

Singly Linked List – Here every node stores the address of only the next node in the list. We can traverse the list only in one direction( start to end ).
Doubly Linked List – Here every node stores the address of the previous as well as next node in the list. We can traverse the list only in both directions( start to end and end to start ).

Working of a LinkedList

In Java when used in program the LinkedList implements the doubly linked list in the memory in the background of all the logic of the code.

An LinkedList can be dynamically declared using the following syntax

LinkedList<data_type> name = newLinkedList<>();

Inserting values in the LinkedList

We can insert new values into the LinkedList either at a specific position in the vector or at the end of the existing vector.

For inserting new elements we have two methods which are both named ‘add’. Furthermore add(object) – It adds the given object at the end of the list

add(int index,object) – It adds the given object at the index specified in the argument. Unlike ArrayLists we do not get an overhead of shifting elements for every insertion. Here the connection between the nodes helps us greatly to insert a new element in constant time.

LinkedList<String> list = new LinkedList<String>();
        list.add("100");
        list.add("200");
        list.add("300");
        list.add("400");
        list.add("500");
        //100 200 300 400 500

Accessing and Searching values in the LinkedList

The objects stored in the LinkedList can be accessed by the index where they are stored in the list using the ‘get’ method function.

get(int index) – This function returns the object stored at the given index in the list. This method takes constant time due to the use of indices and is very fast.

for(int i=0;i<list.size();i++){
            System.out.print(list.get(i));
        }
        //100 200 300 400 500
        System.out.println();
        for(String temp: list){
            System.
            //100 200 300 400 500
        Iterator<String> itr=list.iterator();  
        while(itr.hasNext()){ 
         System.out.print(itr.next());
        }
        //100 200 300 400 500

Modifying the LinkedList

The objects in the LinkedList can be modified using the ‘set’ method function. This function assigns a new value to the index which it refers to.

set(int index,object) – The new object in the argument is assigned to the vector at the given index.

//100 200 300 400 500
        list.set(2,"1000");
        //100 200 1000 400 500

Deleting in the LinkedList

The objects in the LinkedList can be deleted using two functions both named ‘remove’. remove(object) – This function deletes the given object in the LinkedList. If the object appears multiple times then the first occurrence of the object is deleted.

remove(int index) – This function deletes the data value stored at a given index. Unlike ArrayLists we do not get an overhead of shifting elements for every deletion. Here the connection between the nodes helps us greatly to delete a new element in constant time.

//100 200 300 400 500
        list.remove(1);
        //100 300 400 500
        list.remove("500");
        //100 300 400

Difference Between: Arraylist vs Linkedlist

	ArrayList	LinkedList
Insertion	Slower compared to LikedListTime Complexity : O(N)	Faster than ArrayListTime Complexity : O(1)
Deletion	Slower compared to LikedListTime Complexity : O(N)	Faster than ArrayListTime Complexity : O(1)
Traverse	Bidirectional	Bidirectional
Searching	Fast searching Time Complexity : O(N)	Fast searching Time Complexity : O(N)
Memory Usage	Memory efficient. It only stores the object in the list.	Memory inefficient. It stores the object and the pointers to next and previous nodes.
Memory Allocation	Contiguous memory is allocated to all the objects.	Contiguous memory is not allocated.

Where should we use ArrayList ?

Since searching is fast in ArrayList we should use Arraylist for updation purposes where we have less insertion and deletion and also we need to save memory.

Where should we use LinkedList?

Since insertion and deletion is fast in the list we should use LinkedList wherever we have more insertion and deletion queries.

Conclusion

We have studied the major differences between ArrayList and LinkedList. This can be concluded from the article that although both of them are very similar to each other but if we use them wisely we can get more advantages from them.

Learn on Scaler Topics and get certified.