What is a List in Java? - IT Interview Guide

In Java, a List is an ordered collection of elements, meaning the elements are stored in a sequence, and each element is associated with an index that represents its position in the list. The Java List interface extends the Collection interface and provides more specific methods for working with sequences of elements. Lists are part of the Java Collections Framework, which provides a set of interfaces and classes that deal with data structures and algorithms.

A List allows duplicate elements, meaning the same element can appear more than once. It also supports positional access, meaning you can access, modify, or remove elements based on their index.

Key Features of Lists in Java:

Ordered Collection: Elements in a List are ordered and indexed.
Allows Duplicates: A List can contain duplicate elements, meaning the same value can appear multiple times.
Dynamic Sizing: Lists in Java dynamically adjust their size as elements are added or removed.
Indexed Access: Elements can be accessed or modified by their index, starting from 0.
Multiple Implementations: The List interface has several implementations, such as ArrayList, LinkedList, and Vector.

The List Interface in Java

The List interface is part of the java.util package and is a sub-interface of the Collection interface. It provides several methods for adding, removing, accessing, and manipulating elements in the list.

Here is a simplified view of the List interface:

package java.util;

public interface List<E> extends Collection<E> {
    void add(int index, E element);                // Adds element at a specific index
    boolean addAll(int index, Collection<? extends E> c); // Adds a collection at a specific index
    E get(int index);                              // Retrieves the element at the specified index
    E set(int index, E element);                   // Replaces element at specified index
    E remove(int index);                           // Removes element at specified index
    int indexOf(Object o);                         // Returns the first occurrence of element
    int lastIndexOf(Object o);                     // Returns the last occurrence of element
    ListIterator<E> listIterator();                // Returns a list iterator
    ListIterator<E> listIterator(int index);       // Returns a list iterator starting from index
    List<E> subList(int fromIndex, int toIndex);   // Returns a sublist from fromIndex to toIndex
}

Common List Implementations in Java

Java provides several classes that implement the List interface. The most commonly used implementations are:

ArrayList: A dynamically resizing array implementation of the List interface. It allows fast access to elements but may have slower insertions and deletions compared to a LinkedList.
LinkedList: A doubly linked list implementation of the List interface. It performs better for frequent insertions and deletions but has slower access times compared to ArrayList.
Vector: Similar to ArrayList but synchronized. It is considered obsolete in favor of ArrayList for most purposes.
Stack: A subclass of Vector that represents a stack (LIFO data structure).

In this article, we’ll focus on the two most commonly used implementations: ArrayList and LinkedList.

1. ArrayList in Java

ArrayList is backed by an array and automatically resizes itself when the number of elements exceeds its capacity. It provides constant-time access to elements by index but is relatively slow when adding or removing elements in the middle of the list, as it requires shifting elements.

Here’s a basic example of using ArrayList:

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        // Create an ArrayList of Strings
        ArrayList<String> list = new ArrayList<>();
        
        // Add elements to the list
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // Access elements by index
        System.out.println("Element at index 1: " + list.get(1));  // Output: Banana
        
        // Modify an element
        list.set(1, "Blueberry");
        System.out.println("Modified list: " + list);  // Output: [Apple, Blueberry, Cherry]
        
        // Remove an element
        list.remove("Cherry");
        System.out.println("After removal: " + list);  // Output: [Apple, Blueberry]
        
        // Check if the list contains a specific element
        boolean containsBanana = list.contains("Banana");
        System.out.println("Contains 'Banana': " + containsBanana);  // Output: false
    }
}

Key Methods of `ArrayList`:

add(E element): Adds an element to the end of the list.
get(int index): Retrieves the element at the specified index.
set(int index, E element): Replaces the element at the specified index.
remove(Object o): Removes the first occurrence of the specified element.
size(): Returns the number of elements in the list.

2. LinkedList in Java

LinkedList is implemented as a doubly linked list, where each element (node) contains a reference to both the previous and next element. This allows for faster insertions and deletions compared to ArrayList, but accessing elements by index is slower due to the need to traverse the list.

Here’s an example of using LinkedList:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        // Create a LinkedList of Integers
        LinkedList<Integer> list = new LinkedList<>();
        
        // Add elements to the list
        list.add(10);
        list.add(20);
        list.add(30);

        // Access the first and last elements
        System.out.println("First element: " + list.getFirst());  // Output: 10
        System.out.println("Last element: " + list.getLast());    // Output: 30
        
        // Remove the first and last elements
        list.removeFirst();
        list.removeLast();
        System.out.println("After removal: " + list);  // Output: [20]

        // Add elements at the beginning and end
        list.addFirst(5);
        list.addLast(25);
        System.out.println("After adding elements: " + list);  // Output: [5, 20, 25]
    }
}

Key Methods of `LinkedList`:

addFirst(E e): Adds an element at the beginning of the list.
addLast(E e): Adds an element at the end of the list.
removeFirst(): Removes the first element of the list.
removeLast(): Removes the last element of the list.
getFirst(): Returns the first element in the list.
getLast(): Returns the last element in the list.

Choosing Between `ArrayList` and `LinkedList`

ArrayList is generally preferred when you need fast random access to elements (constant time O(1)), but if you’re frequently inserting or deleting elements, particularly in the middle of the list, LinkedList may be more efficient.
LinkedList is more suitable when you need frequent insertions and deletions, especially at the beginning or end of the list (constant time O(1)), but it has slower random access (linear time O(n)).

List Iteration in Java

Both ArrayList and LinkedList support iteration using several methods:

1. Using For-Loop

ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));  // Outputs each element in the list
}

2. Using Enhanced For-Loop

for (String fruit : list) {
    System.out.println(fruit);
}

3. Using Iterator

import java.util.Iterator;

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

4. Using ListIterator

ListIterator allows traversing the list in both directions and supports modification during iteration:

ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    String element = listIterator.next();
    System.out.println(element);
}

List Operations and Performance

When using lists in Java, it is important to understand the time complexity of common operations:

Operation	ArrayList	LinkedList
Access by index	O(1)	O(n)
Search by element	O(n)	O(n)
Insert at end	O(1)	O(1)
Insert at beginning	O(n)	O(1)
Insert in the middle	O(n)	O(n)
Remove by index	O(n)	O(n)
Remove by element	O(n)	O(n)

Conclusion

In Java, the List interface is an essential part of the Collections Framework, offering a way to store ordered collections of elements. Its flexibility allows you to choose the most appropriate implementation based on your specific needs. ArrayList and LinkedList are the two most widely used classes implementing the List interface, each with its own advantages depending on the type of operations you need to perform.

Understanding when to use ArrayList vs. LinkedList, and how to efficiently iterate and manipulate lists, is crucial for writing optimized Java applications.

Please follow and like us: