An In-depth Guide to the List Interface

List Interface

The List interface is a part of the Java Collections Framework and extends the Collection interface. It represents an ordered collection of elements where duplicate values are allowed. The key feature of a list is that elements are stored in a specific order, and you can access elements by their index.

Common Implementations of List

Java offers several implementations of the List interface, each with its own characteristics. The most commonly used List implementations are:

1. ArrayList: This implementation uses an array to store elements. It provides fast random access to elements but can be slower for insertions and removals in the middle.

   • Synchronization: Not synchronized (not thread-safe).

   • Performance: faster than Vector due to lack of synchronization.

   • Data Structure: It uses a dynamic array to store elements, allowing for fast random access but slower insertions/removals in the middle.

   • Usage: Suitable for most use cases where synchronization is not required.

   • Dynamic Sizing: Unlike regular arrays in Java, ArrayList does not have a fixed size. It can automatically resize itself as elements are added or removed. This makes it very convenient for managing collections of data of varying sizes.

   • Ordered: ArrayList maintains the order of elements based on the order in which they were added. You can access elements by their index, and they are stored sequentially in memory.

   • Concurrency: ArrayList is not synchronized, meaning it is not thread-safe. If you need to work with ArrayList in a multi-threaded environment, consider using Collections.synchronizedList() to create a synchronized version or use java.util.concurrent alternatives like CopyOnWriteArrayList.

   • Null Elements: ArrayList can store null elements. This can be useful but also requires extra care when iterating or performing operations on the list.

2. LinkedList: In a LinkedList, elements are stored as nodes, connected by pointers. It's efficient for insertions and removals but slower for random access.

   • Synchronization: Not synchronized by default (not thread-safe).

   • Performance: Efficient for insertions and removals, especially at the beginning or end of the list, but slower for random access.

   • Data Structure: Elements are stored as nodes linked together, which allows for efficient insertions/removals but slower access.

   • Usage: Useful when frequent insertions/removals are needed, or when implementing certain data structures like queues or double-ended queues (Deque).

   • Dynamic Sizing: Like ArrayList, LinkedList can grow or shrink as elements are added or removed. However, it does not use a single contiguous block of memory like an array; instead, each element is stored in a separate node, which is linked to the next and previous nodes.

   • Doubly Linked Structure: A LinkedList is composed of nodes where each node contains both data and a reference (or link) to the next node (forward link) and the previous node (backward link). This structure allows for efficient insertion and deletion of elements at both the beginning and end of the list.

   • Methods for Adding and Removing: LinkedList provides methods for adding (add()) and removing (remove()) elements at various positions, including the beginning and end of the list.

       LinkedList<Integer> numbers = new LinkedList<Integer>();
       numbers.add(1);         // Adds 1 to the end of the list.
       numbers.addFirst(0);     // Adds 0 to the beginning of the list.
       numbers.removeFirst();  // Removes the first element.
     

   • Accessing Elements: You can access elements by their index using the get(index) method. However, accessing elements in the middle of a LinkedList is less efficient compared to an ArrayList because it requires traversing the list from the beginning or end.

       String first = names.getFirst();  // Retrieves the first element.
       String last = names.getLast();    // Retrieves the last element.
     

   • Null Elements: LinkedList can store null elements, just like ArrayList.

   • Specialized Variants: Java offers specialized LinkedList implementations like java.util.LinkedList and java.util.LinkedList.Node. The former is a general-purpose doubly linked list, while the latter provides more fine-grained control over individual nodes and can be useful in specific situations.

3. Vector: Similar to ArrayList, but it's synchronized, making it thread-safe. However, this synchronization can introduce performance overhead.

   • Synchronization: Synchronized (thread-safe).

   • Performance: Slower compared to ArrayList .

   • Data Structure: Similar to ArrayList, it uses a dynamic array to store elements.

   • Usage: Useful in multi-threaded environments where thread safety is a concern, but it comes with a performance trade-off.

   • Dynamic Array: Vector is essentially a dynamic array, like ArrayList. It can dynamically grow or shrink to accommodate elements.

   • Enumeration: Vector provides an Enumeration interface, which allows you to traverse its elements. This feature is a legacy from earlier versions of Java before iterators were introduced.

       Enumeration<String> enumeration = names.elements();
       while (enumeration.hasMoreElements()) {
           String name = enumeration.nextElement();
           System.out.println(name);
       }
     

4. Stack: A specialized class based on Vector, which follows the Last-In-First-Out (LIFO) principle.

   • Extends Vector: As mentioned, Stack extends the Vector class, which means it inherits all the methods and properties of Vector. However, it's important to note that Vector is considered a legacy class, and its use is discouraged in favor of more modern collections like ArrayList.

   • LIFO: Follows the Last-In-First-Out (LIFO) principle, making it suitable for implementing stacks and undo/redo functionality.

   • Basic Operations:

     • push(E item): Adds an element to the top of the stack.

     • pop(): Removes and returns the top element of the stack. If the stack is empty, it throws an EmptyStackException.

     • peek(): Returns the top element of the stack without removing it. If the stack is empty, it throws an EmptyStackException.

     • empty(): Checks if the stack is empty.

     • search(Object o): Searches for an element in the stack and returns its 1-based position from the top. Returns -1 if the element is not found.

         Stack<Integer> numbers = new Stack<Integer>();
         numbers.push(1);
         int top = numbers.pop(); // Removes and returns 1.
       

   • Usage: Primarily used as a stack data structure.

   • Iteration: While Stack does not provide built-in iterators, you can use the pop() method in a loop to retrieve elements in reverse order (from top to bottom).

   • Considerations: In modern Java development, java.util.Stack is less commonly used in favor of other stack implementations like java.util.LinkedList or the built-in stack data structures provided by the Java Collections Framework. These alternatives provide similar functionality without the baggage of being a legacy class. If you need a stack-like data structure, you might consider using Deque (double-ended queue) implementations such as java.util.ArrayDeque or java.util.LinkedList.

Below is a code where I have used some methods of List.

package com.hk.basic;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.Vector;

public class ListDemo {
    List<String> arrayList;
    List<String> linkedList;
    List<String> vector;
    List<String> stack;

    public static void main(String[] args) {
        ListDemo demo = new ListDemo();

        //create List
        demo.arrayList = new ArrayList<String>();
        demo.linkedList = new LinkedList<String>();
        demo.vector = new Vector<String>();
        demo.stack = new Stack<String>();

        //add element to list
        demo.arrayList.add("arrayList");
        demo.arrayList.add("arrayList1");
        demo.linkedList.add("linkedList");
        demo.linkedList.add("linkedList1");
        demo.vector.add("vector");
        demo.vector.add("vector1");
        demo.stack.add("stack");
        demo.stack.add("stack1");

        //print all elements
        System.out.println(demo.print());

        //iterate list
        demo.iterateList(demo.arrayList);
        demo.iterateList(demo.linkedList);
        demo.iterateList(demo.vector);
        demo.iterateList(demo.stack);

        //size of a list
        System.out.println();
        System.out.println("arrayList size:" + demo.arrayList.size());
        System.out.println("linkedList size:" + demo.linkedList.size());
        System.out.println("vector size:" + demo.vector.size());
        System.out.println("stack size:" + demo.stack.size());

        //accessing the element by index
        System.out.println();
        System.out.println(demo.arrayList.get(0));
        System.out.println(demo.linkedList.get(0));
        System.out.println(demo.vector.get(0));
        System.out.println(demo.stack.get(0));

        //Modifying Elements
        demo.arrayList.set(0, "arrayList_new");
        demo.linkedList.set(0, "linkedList_new");
        demo.vector.set(0, "vector_new");
        demo.stack.set(0, "stack_new");

        //Removing element
        demo.arrayList.remove(1);
        demo.linkedList.remove(1);
        demo.vector.remove(1);
        demo.stack.remove(1);

        //print all elements
        System.out.println(demo.print());

    }    

    public String print() {
        return "\narrayList=" + arrayList + "\nlinkedList=" + linkedList + "\nvector=" + vector + "\nstack="
                + stack + "\n";
    }

    //Iterate a List
    public void iterateList(List<String> list){
        for (String element : list) {
            System.out.println(element);
        }
    }
}

This is all about the List interface, in the next blog we will learn about other implementations of the Collection Interface.

Click here to read about the previous blog i.e java collection framework.

Click here to read about my most popular blog i.e binary search.