List

In Java, the Collections Framework provides a set of classes and interfaces that implement common data structures, facilitating the manipulation and storage of collections of objects. Among these, the List interface and its implementations are fundamental components, allowing ordered collections with duplicates.

List Interface

The List interface extends the Collection interface and declares the behavior of a sequence of elements. It supports various operations, including adding, removing, and retrieving elements by their index.

Common Methods

  1. add(E element): Adds the specified element to the end of the list.

  2. add(int index, E element): Inserts the specified element at the specified position in the list.

  3. remove(Object obj): Removes the first occurrence of the specified element from the list.

  4. remove(int index): Removes the element at the specified position in the list.

  5. get(int index): Returns the element at the specified position in the list.

  6. size(): Returns the number of elements in the list.

ArrayList Class

ArrayList is one of the most commonly used implementations of the List interface. It provides a dynamic array that can grow or shrink as needed.

  • Dynamic Sizing: ArrayList automatically adjusts its size, making it suitable for scenarios where the number of elements is unpredictable.

  • Random Access: Elements can be accessed directly using index positions, which results in constant time complexity O(1) for retrieval.

  • Underlying Data Structure: Internally, ArrayList uses an array to store elements.

  • Performance Consideration: Ideal for scenarios where there are more frequent reads and fewer writes.

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        // Creating an ArrayList
        List<String> fruits = new ArrayList<>();

        // Adding elements
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");

        // Accessing elements
        System.out.println("First fruit: " + fruits.get(0));

        // Iterating through the list
        System.out.println("All fruits:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // Removing an element
        fruits.remove("Banana");

        // Size of the list
        System.out.println("Number of fruits: " + fruits.size());
    }
}

LinkedList Class

LinkedList is another implementation of the List interface that is implemented as a doubly-linked list. It provides efficient insertion and removal of elements.

  • Dynamic Sizing: LinkedList also dynamically adjusts its size, making it suitable for scenarios with unpredictable changes in size.

  • Node Structure: Uses nodes to store elements, and each node contains data and references to the next and previous nodes.

  • Insertion and Deletion: Efficient for frequent insertions and deletions due to the ease of adjusting pointers.

  • Performance Consideration: Ideal for scenarios with frequent insertions and deletions but slower for random access compared to ArrayList.

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        // Creating a LinkedList
        List<Integer> numbers = new LinkedList<>();

        // Adding elements
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);

        // Accessing elements
        System.out.println("First number: " + numbers.get(0));

        // Iterating through the list
        System.out.println("All numbers:");
        for (Integer number : numbers) {
            System.out.println(number);
        }

        // Removing an element
        numbers.remove(Integer.valueOf(2));

        // Size of the list
        System.out.println("Number of numbers: " + numbers.size());
    }
}

Vector Class

Vector is an older implementation of the List interface, similar to ArrayList. It is synchronized, which means it is thread-safe but may have performance implications in multi-threaded environments.

  • Synchronization: Vector methods are synchronized, making it suitable for scenarios where multiple threads may access or modify the collection concurrently.

  • Dynamic Sizing: Like ArrayList, Vector adjusts its size dynamically.

  • Performance Overhead: Synchronization introduces overhead, making Vector less efficient in single-threaded scenarios compared to ArrayList.

import java.util.Vector;
import java.util.List;

public class VectorExample {
    public static void main(String[] args) {
        // Create a Vector of Doubles
        List<Double> prices = new Vector<>();

        // Add elements to the Vector
        prices.add(10.5);
        prices.add(15.2);
        prices.add(20.0);

        // Access elements by index
        double firstPrice = prices.get(0); // 10.5

        // Iterate through the Vector
        for (Double price : prices) {
            System.out.println(price);
        }
    }
}

Benchmark

Depending on the use case, one may be more suitable than the other. ArrayList is generally preferred when there are more frequent accesses or when the size is relatively constant. On the other hand, LinkedList is preferred when there are frequent insertions or removals from the middle of the list.

Comparison Table

Feature
ArrayList
LinkedList
Vector

Data structure

Dynamic array

Doubly linked list

Dynamic array

Default size

None

None

None

Insertion

O(1) at end, O(n) elsewhere

O(1) anywhere in the list

O(1) at end, O(n) elsewhere

Deletion

O(1) at end, O(n) elsewhere

O(1) anywhere in the list

O(1) at end, O(n) elsewhere

Access

O(1) by index

O(n) by index

O(1) by index

Search

O(n)

O(n)

O(n)

Space

Space overhead for array

Space overhead for node pointers

Space overhead for array

Thread safe

No

No

Yes

Memory Overhead

Lower

Higher

Higher

Use cases

Frequent access, fewer modifications

Frequent insertions and deletions, good for queues and stacks

Concurrent access/modifications

Which one to choose?

In general, ArrayList is the best choice for most applications. It is efficient for both random access and sequential access, and it is relatively easy to use.

If you need a list that is efficient for frequent insertions and deletions, or if you need to implement a queue or stack, then LinkedList is a good choice.

If you need a thread-safe list, then Vector is a good choice. However, keep in mind that it is slower than ArrayList in single-threaded applications.

In this documentation, we have covered some of the commonly used List implementations in Java, including ArrayList, LinkedList, and Vector. Each implementation has its own characteristics and is suitable for different use cases. Depending on your specific requirements, you can choose the appropriate List implementation to manage ordered collections of elements in your Java applications.

PreviousCollections FrameworkNextSet

Last updated