ArrayList vs. LinkedList in Java: What I Need to Know

The Java programming language offers a rich set of data structures that make it easier for software developers to build Java applications. Understanding the difference between data structures in Java is crucial in order to improve your applications’ performance and efficiency.

ArrayList and LinkedList are two Java data structures that can both be used to store a list of objects. So what’s the difference between ArrayList and LinkedList in Java?

In this article, we’ll go over everything you need to know about the question of LinkedList vs. ArrayList.

What Is ArrayList in Java?

In Java, the ArrayList is a resizable array data structure that implements the List interface.

Resizable arrays, also called dynamic arrays, are data structures that store elements in sequential order and whose size can be increased or decreased by adding or removing elements.

Below, we look at the efficiency of some common ArrayList operations:

• Retrieval: Getting a specific element in the ArrayList is extremely fast with the ArrayList.get(i) method, where i is the element’s index.
• Addition: Adding a new element to the ArrayList is usually extremely fast, as long as you are adding to the end and there is still room in the array. If the array is full, adding a new element requires more time because the array’s size first needs to be expanded.
• Deletion: Deleting an element from the ArrayList is relatively slow, even though the actual deletion can be done quickly. This is because all elements after the deleted element need to be shifted one place to the left to fill the hole in the array left by the deletion.

What Is LinkedList in Java?

In Java, the LinkedList is a doubly linked list data structure that implements the List and Deque interfaces.

Doubly linked lists are data structures that store elements in sequential order, with each element associated with a node in the list.

Each node contains a pointer to the next and previous nodes in the list so that you can easily traverse the list either backward or forwards.

Below, we look at the efficiency of some common LinkedList operations:

• Retrieval: LinkedLists do not have an easy way to retrieve arbitrary elements. In the worst case, getting a specific element in the LinkedList therefore requires you to traverse the entire list to find the element you’re looking for.
• Addition: Adding a new element to the LinkedList can be done in fast constant time if you are appending to the front or end of the list. If you want to insert  a new element in an arbitrary position, you’ll need to spend more time traversing the list.
• Deletion: Deleting an element from the LinkedList, like adding one, is fastest when deleting from the list’s front or end. However, deletion is slower when removing an arbitrary element.

ArrayList vs. LinkedList: Which is Right for Me?

The most important difference between ArrayList and LinkedList is the distinction between contiguous and non-contiguous memory.

ArrayLists use contiguous memory. All elements in the ArrayList are located next to each other in the same memory space.

This is why retrieving an element from an ArrayList is so fast: given the location of the start of the ArrayList, you can know exactly where any element is located in memory.

LinkedLists, on the other hand, use non-contiguous memory. There is no guarantee that two elements “next” to each other in a LinkedList are actually physically close in memory.

This is why retrieving an element from a LinkedList is slower: you need to traverse the list using pointers, instead of automatically predicting where the element is located.

On another note, ArrayLists are better if you have strict memory constraints. Storing an ArrayList requires space for only the data itself.

Storing a LinkedList, however, requires space for the data as well as for the forwards and backward pointers, which can be a significant overhead.

This means that the use cases for ArrayLists and LinkedLists are different in practice:

• ArrayLists are best for cases where you will be retrieving elements (that is, reading from the array) more frequently than modifying the array.
• LinkedLists are best for cases where you will be modifying the list often, especially at the front or end of the list.

For example, LinkedLists are commonly used to implement a queue in which elements are inserted and removed in FIFO (first in, first out) order.

New elements can be quickly added (or “pushed”) to the front of the list, as well as quickly removed (or “popped”) from the front.

Looking for more software development insights?Check out the Adservio blog for the latest news and updates.

If you’re looking for a Java software development partner, Adservio can help.

Our skilled team of IT professionals helps companies achieve digital excellence in use cases from application development to software delivery. ‍

Get in touch with us today to discuss your business needs and objectives.