Difference Between ArrayList and LinkedList

Posted in

Difference Between ArrayList and LinkedList
vinaykhatri

Vinay Khatri
Last updated on February 28, 2024

    The list is an abstract data type available in functional programming languages that stores ordered values. It is analogous to arrays in object-oriented programming languages. Lists allow us to store, manipulate, and retrieve data easily.

    Programming languages that support list data types have their ways of creating lists. We can create a list by inserting data items sequentially within a pair of delimiters, like braces ‘{ }’, brackets ‘[ ]’, parentheses ‘( )’, or angular brackets ‘< >’, where items are separated by spaces, commas, or semicolons.

    The primary drawback of the traditional array is its fixed size, and we need to define the size of an array before using it. ArrayList and LinkedList both these data structures overcome the problem of an array’s fixed size. They both implement the List interface and allow us to insert objects of any type.

    This article will highlight the differences between ArrayList and LinkedList. But before proceeding, we shall make you familiar with ArrayList and LinkedList. So, let us get started.

    What is ArrayList?

    An ArrayList is a growable array that can store data of different types, and it is a dynamic array whose size increases as we add elements to it. Despite being slower than the traditional array, ArrayList is useful when an application requires performing a lot of manipulations in the array.

    Let us see how ArrayList overcomes the problem of an array with an example. Consider an array named ‘studNames’, which stores the name of students, as given below:

    String[] studNames = new String[5]
    studNames[0] = "John";
    studNames[1] = "Oliver";
    studNames[2] = "Brown";
    studNames[3] = "Sam";
    studNames[4] = "George";

    In the above example, the array size is fixed. It does not allow inserting more than 5 elements. But this is not the case with ArrayList, as it is a dynamic array. There is no need to define the size initially while creating ArrayList. Let us create an ArrayList and store the same data.

    ArrayList<String> studNames = new ArrayList<String>();
    studNames.add("John");
    studNames.add("Oliver");
    studNames.add("Brown");
    studNames.add("Sam");
    studNames.add("George");

    ArrayList lets us add as many elements as we wish. Also, it becomes easier to retrieve and manipulate any element from the ArrayList using its index. It is essential to remember that the first index is always zero. When we print the above ArrayList, it gives the output as:

    [John, Oliver, Brown, Sam, George]

    Features of ArrayList

    • ArrayList can store duplicate values, i.e., we can insert two elements of the same name in ArrayList.
    • It can store a null value.
    • Sorting an ArrayList in ascending or descending order is simple using the ‘sort’ method present in the Java.util.Collections class.
    • ArrayList allows random access, as it works on an index basis.
    • It is not synchronized.
    • ArrayList in Java can be thought of as Vector in C++.

    Hierarchy of ArrayList

    The below diagram represents the hierarchy of ArrayList:

    Hierarchy of ArrayList

    This diagram depicts that the ArrayList class extends the AbstractList class, which implements the List interface. Further, the List interface extends the Collection and Iterable interfaces in the given order.

    What is LinkedList?

    A LinkedList is a linear data structure, where every element is known as a node consisting of the actual data and pointers to the previous and the next nodes. Although Java supports a Singly Linked List, it implements LinkedList as a Doubly-Linked List (DLL) internally. Below is the diagram of a Doubly-Linked List.

    LinkedList

    Here, the demarcation on the left of each node represents a pointer to the previous node, and on the right represents a pointer to the next node. The left of Item 1 is null, as there is no previous node and the right points to Item 2. Item 2 contains a pointer to its previous node, Item 1, and a pointer to its next node, Item 3. Finally, Item 3 has a pointer to its previous node, Item 2, and the next pointer is null, as it is the last node in a list.

    Features of LinkedList

    • In LinkedList, we use the get(<index>) method to retrieve elements. Also, we can add and remove as many elements as we need, like ArrayList.
    • LinkedList also supports null values and duplicate values.
    • It is not synchronized.
    • We can use a LinkedList in Java as a stack, queue, and list.

    Hierarchy of LinkedList

    The below diagram represents the hierarchy of LinkedList:

    Hierarchy of LinkedList

    As shown in the diagram, LinkedList extends the AbstractSequentialList, which implements the List interface, and implements the Deque interface, which extends the Queue interface. Furthermore, the List and Queue interfaces extend the Collection interface, which further extends the Iterable interface.

    ArrayList vs LinkedList: A Head-to-Head Comparison

    Here are some key differences between ArrayList and LinkedList.

    ArrayList LinkedList
    It is implemented as a dynamic array and stores elements in a sequential manner. It is implemented as a doubly-linked list and has pointers to previous and next nodes.
    ArrayList acts like a list as it implements the List Interface. LinkedList acts like a list and queue, as it implements the List Interface and the Deque interface.
    It is ideal when an application requires storing and retrieving data. It is perfect when an application involves the manipulation of stored data.
    The storage and retrieval of data are faster in ArrayList using the index. The storage and retrieval of data are relatively slower in LinkedList than ArrayList, as it traverses through each node to identify the correct element.
    Manipulating an ArrayList, like inserting or removing elements, takes a bit longer time, as elements have to be moved left or right accordingly. Manipulation in LinkedList is more efficient and faster than ArrayList, as there is no concept of shifting elements.
    We cannot use ArrayList as a Stack. We can use LinkedList as a Stack, as it implements the Deque interface, and Deque supports push(), pop(), and peek() methods.

    ArrayList or LinkedList — Which One to Use?

    When an application or project requires a lot of manipulations, like adding or deleting elements, LinkedList is an ideal data structure over ArrayList. ArrayList would be a great choice when an application or project requires searching and retrieving elements because the time complexity of search operation in ArrayList is O(1). In contrast, it is O(n/2) in LinkedList.

    ArrayList and LinkedList Examples in Java

    ArrayList

    import java.io.*;
    import java.util.*;
    class students
    {
    public static void main(String[] args)
    {
    ArrayList<String> studNames = new ArrayList<String>();
    studNames.add("John");
    studNames.add("Oliver");
    studNames.add("Brown");
    studNames.add("Sam");
    studNames.add("George");
    System.out.println("Initial ArrayList:" +studNames);
    studNames.remove(2);
    System.out.println("After removing an element from ArrayList:" +studNames);
    studNames.add(1, "Harry");
    System.out.println("ArrayList after adding an element:" +studNames);
    studNames.set(2, "Henry"):
    System.out.println("Final ArrayList:" +studNames);
    }
    }

    Output

    Initial ArrayList: [John, Oliver, Brown, Sam, George]
    After removing an element from ArrayList: [John, Oliver, Sam, George]
    ArrayList after adding an element: [John, Harry, Oliver, Sam, George]
    
    Final ArrayList: [John, Harry, Henry, Sam, George]

    LinkedList

    import java.util.*;
    class employees
    {
    public static void main(String[] args)
    {
    LinkedList<String> empNames = new LinkedList<String>();
    empNames.add("Mary");
    empNames.add("Liam");
    empNames.add("Charlotte");
    empNames.add("Elijah");
    empNames.add("Ava");
    empNames("Emma");
    System.out.println("Initial LinkedList:" +empNames);
    empNames.remove(3);
    System.out.println("After removing an element from LinkedList:" +empNames);
    empNames.add(3, "Anna");
    System.out.println("LinkedList after adding an element:" +empNames);
    empNames.removeFirst();
    empNames.removeLast();
    System.out.println(“LinkedList after removing the first and last elements:" +empNames);
    
    empNames.set(3, “Evelyn”);
    
    System.out.println(“Final LinkedList:” +empNames);
    }
    }

    Output

    Initial LinkedList: [Mary, Liam, Charlotte, Elijah, Ava, Emma]
    After removing an element from LinkedList: [Mary, Liam, Charlotte, Ava, Emma]
    
    LinkedList after adding an element: [Mary, Liam, Charlotte, Anna, Ava, Emma]
    
    LinkedList after removing the first and last elements: [Liam, Charlotte, Anna, Ava]
    
    Final LinkedList: [Liam, Charlotte, Anna, Evelyn]

    Conclusion

    Both ArrayList and LinkedList overcome the problem of the traditional array, as they are dynamic. As LinkedList implements the Deque interface, it offers more features than ArrayList. ArrayList is faster if you only need to store and retrieve data, whereas LinkedList is faster if there are a lot of manipulations. We hope that this article has helped you to understand the differences between ArrayList and LinkedList. Choosing either ArrayList or LinkedList entirely depends on an application’s requirements.

    People are also reading:

    FAQs


    While ArrayList is faster in storing and accessing data, LinkedList is better in the manipulation of data.

    Internally, an ArrayList stores elements in a dynamic array, whereas LinkedList uses a doubly LinkedList to store elements.

    When there is a frequent modification, like addition or subtraction, to the collection, a LinkedList is far better than an ArrayList. An ArrayList is ideal to use when the collections require rare modifications or the collections are read-only.

    An ArrayList is faster in retrieval because it stores elements in an array where users can directly refer to the element they want to retrieve.

    Leave a Comment on this Post

    0 Comments