Skip to main content

The List Interface

The List interface extends the Collection interface. It represents an ordered collection of elements, meaning it maintains the insertion order. Furthermore, unlike Sets, Lists allow duplicate elements.

The java.util package provides several concrete classes that implement the List interface. The most commonly used are ArrayList and LinkedList.

1. ArrayList​

The ArrayList class is the most widely used collection in Java. It uses a dynamic array to store elements.

Key Characteristics​

  • Dynamic Resizing: It automatically grows its capacity as new elements are added.
  • Fast Random Access: Because it is backed by an array, retrieving an element by its index (list.get(index)) is extremely fast ($O(1)$).
  • Slow Insertions/Deletions: Inserting or deleting an element in the middle of the list requires shifting all subsequent elements, which is slow ($O(n)$).

Example​

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

public class LabList1 {

  public static void main(String args[]) {
    // Creating an ArrayList of Strings
    List<String> list = new ArrayList<>();

    // Adding elements
    list.add("Apple");
    list.add("Banana");
    list.add("Apple"); // Duplicates are allowed

    // Accessing an element by index
    System.out.println("Element at index 1: " + list.get(1));

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

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

2. LinkedList​

The LinkedList class uses a doubly-linked list data structure to store elements.

Key Characteristics​

  • Fast Insertions/Deletions: Because it uses pointers to connect nodes, inserting or deleting elements (especially at the beginning or middle) is very fast. It only requires updating pointers, not shifting elements.
  • Slow Random Access: Retrieving an element by its index requires traversing the list from the beginning to the specified index, which is slow ($O(n)$).
  • Memory Overhead: Every element requires extra memory to store the pointers to the next and previous nodes.

Example​

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

public class LabList2 {

  public static void main(String args[]) {
    List<String> linkedList = new LinkedList<>();

    linkedList.add("John");
    linkedList.add("Doe");

    // LinkedList specific methods (requires LinkedList reference, not List)
    LinkedList<String> queue = new LinkedList<>();
    queue.addFirst("First");
    queue.addLast("Last");

    System.out.println(queue);
  }
}

3. Vector and Stack (Legacy)​

Vector​

Vector is very similar to ArrayList as it also uses a dynamic array. The core difference is that Vector is synchronized (thread-safe). Because of the synchronization overhead, it is generally much slower than ArrayList. In modern Java, if you need a thread-safe list, it's better to use CopyOnWriteArrayList.

Stack​

Stack is a subclass of Vector. It implements the standard Last-In-First-Out (LIFO) data structure. It provides specific methods like push(), pop(), and peek().

[!TIP] Summary: When to use what?

  • If you primarily need to search/read data by index, use ArrayList.
  • If you primarily need to insert/delete data frequently in the middle of the collection, use LinkedList.