Java LinkedList

The Java LinkedList Class

The LinkedList class is another common implementation of the List interface. Unlike ArrayList, which uses a dynamic array, LinkedList stores its elements in a doubly-linked list.

How LinkedList Works

A LinkedList is made up of a sequence of nodes. Each node contains three pieces of information:

1. The actual element (the data).
2. A reference (or "link") to the previous node.
3. A reference (or "link") to the next node.

The list keeps track of the first node (the "head") and the last node (the "tail"). To add an element, it just needs to create a new node and update the links of its neighbors.

Key Characteristics of LinkedList

• Fast Insertion/Deletion: Adding or removing elements from the beginning, end, or even the middle of a LinkedList is very fast. The operation doesn't require shifting other elements; it only involves updating a few node references. This is an O(1) operation if you are at the head or tail.
• Slow Random Access: Accessing an element at a specific index using get(index) is slow. To get to the element at index i, the list has to traverse from the beginning (or end) node by node until it reaches the i-th element. This is an O(n) operation.
• Implements Deque: LinkedList also implements the Deque (double-ended queue) interface, which provides efficient methods for adding/removing elements from both ends (addFirst, addLast, removeFirst, removeLast).

When to Use LinkedList

LinkedList is the best choice when your primary operations are adding and removing elements. If you frequently insert or delete items from the beginning or middle of your list, LinkedList will provide much better performance than ArrayList.

It's also a great choice if you need the functionality of a Queue or a Deque.

ArrayList vs. LinkedList

*Note: While the insertion/deletion itself is fast in a LinkedList, finding the position to insert/delete still takes O(n) time.

LinkedList Example

The LinkedList class has all the same methods as the ArrayList class because they both implement the List interface. It also has additional methods for adding/removing from the head and tail.

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList cars = new LinkedList();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    // Add an element to the beginning
    cars.addFirst("Mazda");
    System.out.println(cars);
    // Add an element to the end
    cars.addLast("Bugatti");
    System.out.println(cars);
    // Remove the first element
    cars.removeFirst();
    System.out.println(cars);
    // Get the first element
    System.out.println("First element is: " + cars.getFirst());
  }
}