Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

ArrayList or LinkedList?

DZone's Guide to

ArrayList or LinkedList?

Learn everything you need to know to choose your sequential data structure.

· Java Zone ·
Free Resource

Java-based (JDBC) data connectivity to SaaS, NoSQL, and Big Data. Download Now.

This article provides guidance to Java developers in choosing the appropriate sequential data structure.

ArrayList and LinkedList are two classes of the Java Collection Framework used for storing lists of object references. ArrayList and  LinkedList both implement the List interface. Let's first try to understand their most important parent interface List (which).

List Interface

A list is simply an ordered collection of elements (also known as a sequence). It adds position-oriented operations useful for quickly accessing, adding, and removing elements at a specific index position on the list. List interface has Collection and Iterable as super-interfaces. It can allow storing duplicates and null values. It provides indexed access to its element.

Usage

Below is the code snippet of declaring ArrayList and LinkedList using the List interface.

import java.util.*;

public class MyClass {

  // Unsynchronized or Not thread safe
  List<Object> arrayList = new ArrayList<>(); // declares an array list
  List<Object> linkedList = new LinkedList(); // declares a linked list   

    // ensures thread safety 
  List<Object> tsArrayList = Collections.synchronizedList(new LinkedList<>());
  List<Object> tsLinkedList = Collections.synchronizedList(new LinkedList<>());   
}


Vector is similar to ArrayList except they are provided with automatic synchronization, which makes them thread safe but causes some performance overhead. 

Internal Implementation 

Linked List

The LinkedList data structure contains an ordered set of data elements (know as nodes) such that each element contains a link or reference to its successor (next element). The last element (or tail) of the sequence points to a null element. The linked list itself contains a reference to the first element of the list, which is called the head element. LinkedList in Java is a doubly-linked list implementation of the List interface. In a doubly-linked list, every node points to its previous and next node. Other interfaces it implements are Serializable, Cloneable, and Deque (with super-interface as Queue). 

ArrayList

ArrayList is a resizable-array implementation of the List interface. It is internally implemented as an object array, which can increase the size as necessary to support more number of elements in the collection. It is possible to specify the initial capacity of an ArrayList through the constructor ArrayList(int initialCapacity)  and later increases the capacity using  void ensureCapacity(int minCapacity), if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.

It also includes a method void trimToSize()to reduce the size based on existing elements.

// calling constructure ArrayList<type>(initialCapacity)
List arr = new ArrayList<Integer>(10);


By default, an ArrayList creates a list of initial capacity 10, while LinkedList only constructs an empty list without any initial capacity.  LinkedList does not implement the RandomAccess interface, whereas ArrayList implements the RandomAccess interface (instead of Deque interface).

Space and Time Complexity of Various Operations

Characteristic

ArrayList

LinkedList

Adding (or removing) an element

This involves moving all the existing elements back (or forward) by one place requiring copying of items done via a call to  System.arraycopy(). -- best case time complexity is O(1).

average case time complexity O(n) as System.arraycopy() would be linear time. 

This involves allocating (or deallocating) an internal record for the element and then realigning a couple of links and has a fixed cost. -- time complexity is O(1). Adding (or removing) an element at the middle of the list would have a time complexity of O(n) as it would involve iterating over the list.

Appending an element

Typically, this involves setting an internal array location to the element reference with time complexity of O(1)., but occasionally for the case of an overflow, it results in the array being reallocated and has a fixed averaged cost again involving triggering a call to System.arrayCopy(), with worst case time complexity of O(n).

This just involves allocating an internal object, and the cost is uniform. 

Memory space Overhead

It has a memory space overhead as the list of objects has to be preallocated which means empty elements at the end of the list.

It has a memory space overhead for storing the references to the previous and next element in the list for every element.

Random Access to its elements

Random access has a fixed time -- time complexity is O(1). 

The time to do random access is proportional to the size of the list (unless this is the first or the last element where the cost is fixed) -- average case time complexity is O(n).

Null Values Yes, it can be stored Yes, it can be stored
Duplicates Yes, it can be stored

Yes, it can be stored


Tips

Consider the following code examples for traversing aLinkedList The code below would be very slow as doesLinkedList not support random access and there is a huge overhead while traversing for each iteration.

LinkedList ll = new LinkedList();
…
…
Object o = null;   
for (int i = 0; i < list.size(); i++)
{       
  o = list.get(i);
  …
} 

A better approach for improved performance would be to use the following code instead.

LinkedList ll = new LinkedList(); 
… 
…   
Object o = null;    
ListIterator li = list.listIterator(0);   
while (li.hasNext()){
  o = ll.next();
  …    
} 

Conclusion

An ArrayList is faster and better as it supports random access to its elements. Traversing a linked list or inserting an item in the middle is very expensive as you have to iterate over each item and is very likely to have cache misses. If you need to perform processing on multiple items of the list in a single iteration then the overhead of iterations can be lesser inLinkedList  than that of anArrayList  which involves copying array element multiple times.

To share your experience and more insights on this topic, please leave your thoughts in the comments section below.

Connect any Java based application to your SaaS data.  Over 100+ Java-based data source connectors.

Topics:
java ,java 1.8 ,data structure using java

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}