# 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.

```java
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.

```java
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.

```java
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.

<figure><img src="https://i.stack.imgur.com/pdKaZ.png" alt=""><figcaption><p>List Benchmark</p></figcaption></figure>

***

### Comparison Table

<table><thead><tr><th width="163">Feature</th><th>ArrayList</th><th>LinkedList</th><th>Vector</th></tr></thead><tbody><tr><td><strong>Data structure</strong></td><td>Dynamic array</td><td>Doubly linked list</td><td>Dynamic array</td></tr><tr><td><strong>Default size</strong></td><td>None</td><td>None</td><td>None</td></tr><tr><td><strong>Insertion</strong></td><td>O(1) at end, O(n) elsewhere</td><td>O(1) anywhere in the list</td><td>O(1) at end, O(n) elsewhere</td></tr><tr><td><strong>Deletion</strong></td><td>O(1) at end, O(n) elsewhere</td><td>O(1) anywhere in the list</td><td>O(1) at end, O(n) elsewhere</td></tr><tr><td><strong>Access</strong></td><td>O(1) by index</td><td>O(n) by index</td><td>O(1) by index</td></tr><tr><td><strong>Search</strong></td><td>O(n)</td><td>O(n)</td><td>O(n)</td></tr><tr><td><strong>Space</strong></td><td>Space overhead for array</td><td>Space overhead for node pointers</td><td>Space overhead for array</td></tr><tr><td><strong>Thread safe</strong></td><td>No</td><td>No</td><td>Yes</td></tr><tr><td><strong>Memory Overhead</strong></td><td>Lower</td><td>Higher</td><td>Higher</td></tr><tr><td><strong>Use cases</strong></td><td>Frequent access, fewer modifications</td><td>Frequent insertions and deletions, good for queues and stacks</td><td>Concurrent access/modifications</td></tr></tbody></table>

### 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.