LinkedList

Linked list is a great choice when you need a flexible collection that allows frequent insertions and deletions without shifting elements in memory. Unlike arrays, a linked list stores data in nodes that are linked to one another, allowing efficient memory usage for dynamic changes. This is especially helpful when you don’t know how many elements you’ll need to manage or when you frequently add/remove data from the beginning or end of a collection.

You may consider a linked list as a chain of elements (nodes), where each node is connected to its previous and next neighbor. All elements are not stored sequentially in memory, but they are logically connected. In Java, the linked list class is implemented as a doubly linked list and belongs to the java.util package. It is also a part of the Java Collections Framework.

All elements in a linked list are objects that have three fields: the element itself, the previous, and the next node. The size of a linked list can grow or shrink dynamically as needed, making it more flexible than arrays in scenarios involving frequent additions or removals.

Characteristics

In Java, a linked list has the following important characteristics:

• It implements the List, Deque, and Queue interfaces, allowing it to be used as a list, stack, or queue.

• It maintains the order in which elements are inserted, ensuring predictable iteration. This means that when you iterate through a linked list, you'll encounter the elements in the same sequence they were added.

• It allows duplicate elements, meaning the same value can appear multiple times.

• It supports null values, so null can be stored as a valid element just like any other valid data type.

• It is not thread-safe; it's not designed to be accessed and modified by multiple threads simultaneously without causing data corruption or unexpected behaviour.

• Synchronisation is required for linked list to be used in multi-threaded contexts (e.g., via Collections.synchronizedList()):

  List<String> synchronizedList = Collections.synchronizedList(new LinkedList<>());

• Its elements are not stored contiguously in memory; instead, each element is contained in a separate node connected via links.

  Non-contiguous memory allocation means each element occupies separate blocks rather than a single sequence, allowing nodes to reside anywhere in RAM without requiring one large free block.

• Each node maintains references to both the next and previous nodes, supporting bidirectional traversal and efficient insertions/removals at both ends.

• It is not optimized for index-based access, as accessing an element by index requires linear traversal from the head or tail.

Node structure

Internally, a linked list is made up of small objects called nodes, and each node holds a piece of data (called the item) and two references: one to the next node and one to the previous node in the list. These nodes are defined using a private static inner class inside the LinkedList class. The following diagram illustrates a doubly linked list, where each node stores data and a reference to both the next and previous nodes, allowing bidirectional traversal.

The structure of looks like this:

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

Here, E item is the actual value stored in the node. It can be any object or data type, depending on the type specified for your list. Node<E> next refers to the node that comes after the current one, and Node<E> prev refers to the node that comes before the current one. This setup makes it a doubly linked list, which means you can move through the list in both directions — from the first node to the last (forward), and from the last to the first (backwards).

Declaring a LinkedList

In Java, LinkedList is a generic class, which means you specify the type of elements it will store using angle brackets (<>). This ensures type safety, allowing only elements of the specified type. Here's a simple example of declaring a linked list of integers:

LinkedList<Integer> numbers = new LinkedList<>();

Creating a LinkedList from an existing collection

Besides creating an empty linked list, you can also initialise a linked list with elements from any collection that implements the Collection<E> interface by passing it to the LinkedList constructor. This approach is especially useful when you already have data stored in an ArrayList, a fixed-size list from List.of(), or any other type. The newly created LinkedList will automatically contain all the elements from the provided collection in their insertion order.

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

public class Main {
    public static void main(String[] args) {
        // Example 1: Copying from an ArrayList
        ArrayList<String> arrayList = new ArrayList<>(List.of("X", "Y", "Z"));
        LinkedList<String> linkedFromArray = new LinkedList<>(arrayList);
        System.out.print(linkedFromArray);  // Output: [X, Y, Z]

        // Example 2: Using List.of() directly
        LinkedList<String> linkedFromListOf = new LinkedList<>(List.of("A", "B", "C"));
        System.out.print(linkedFromListOf);  // Output: [A, B, C]
    }
}

This technique lets you seamlessly convert between collection types or bootstrap a linked list with known values in a single step, avoiding multiple add() calls.

Operations

LinkedList supports a variety of core operations—adding, accessing, modifying, removing, and searching elements. Below are the most common methods for each category.

Adding elements to a LinkedList

We can insert elements into the list using several methods provided by the LinkedList class:

• add(E element): adds the element to the end of the list.

• addFirst(E element): adds the element at the beginning of the list.

• addLast(E element): adds the element at the end (same as add()).

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

Here is an example using the names linked list that we declared earlier:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Alice");  // [Alice]
        names.addFirst("Bob");  // [Bob, Alice]
        names.addLast("Charlie");  // [Bob, Alice, Charlie]
        names.add(1, "David");  // [Bob, David, Alice, Charlie]
        System.out.print("After adds: " + names);
    }
}

Each method changes the position of the elements within the list according to where the new element is inserted.

Accessing elements in a LinkedList

Similar to adding elements to the list, we can use multiple methods to get elements.

• get(int index): Returns the element at the specified index.

• getFirst(): Retrieves the first element in the list.

• getLast(): Retrieves the last element in the list.

Here is an example using the names linked list (considering our list has the names we added previously):

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Bob");
        names.add("David");
        names.add("Alice");
        names.add("Charlie");
        System.out.print(names.get(2));  // Alice
        System.out.print(names.getFirst());  // Bob
        System.out.print(names.getLast());  // Charlie
    }
}

Modifying elements in a LinkedList

To modify an element in linked list, we can use set(int index, E element). It replaces the element at the specified index with a new value. Here is an example using names linked list:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Bob");
        names.add("David");
        names.add("Alice");
        names.add("Charlie");
        names.set(1, "Max");
        System.out.print(names);  // [Bob, Max, Alice, Charlie]
    }
}

When you use names.set(1, "Max");it replaces the element at index 1 with "Max".

Removing elements in a LinkedList

The following are a few methods we can use to remove an element from a linked list:

• remove(): Removes the first element of the list.

• removeFirst(): Removes and returns the first element.

• removeLast(): Removes and returns the last element.

Here is an example of remove methods in action:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Bob");
        names.add("Max");
        names.add("Alice");
        names.add("Charlie");
        names.remove();  // removes first
        names.removeLast();  // removes last
        System.out.print(names);  // [Max, Alice]
    }
}

Searching elements in a LinkedList

To search for elements, use:

• contains(Object o): checks each node’s item using equals(o) and returns true as soon as a match is found, or false if the entire list is scanned without a match.

• indexOf(Object o): checks each node's item, comparing each node’s item with o via equals(o). Returns the zero-based index of the first matching element, or -1 if not present.

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> names = new LinkedList<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");

        System.out.print(names.contains("Bob"));  // true
        System.out.print(names.contains("David"));  // false

        System.out.print(names.indexOf("Alice"));  // 0
        System.out.print(names.indexOf("David"));  // -1
    }
}

Traversal in a LinkedList

You can traverse a LinkedList using simple loops, enhanced for-loops, or more powerful tools like Iterator and ListIterator. Forward traversal is commonly done using Iterator, which allows moving from the first element to the last. In the following example, we create a new list and iterate through its elements using an Iterator.

import java.util.LinkedList;
import java.util.Iterator;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("One");
        list.add("Two");
        list.add("Three");

        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            // Output: One Two Three
            System.out.print(it.next() + " ");
        }
    }
}

Similarly, forward and backwards traversal can be done using ListIterator, which supports moving in both directions. Using the declared list in the previous example:

import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        // Add elements to the list
        list.add("One");
        list.add("Two");
        list.add("Three");

        // Create a ListIterator
        ListIterator<String> it = list.listIterator();

        // Forward traversal
        System.out.println("Forward traversal:");
        while (it.hasNext()) {
            System.out.print(it.next());
        }

        // Backward traversal
        System.out.println("Backward traversal:");
        while (it.hasPrevious()) {
            System.out.print(it.previous());
        }
    }
}

Practical wrap-up

Now that we've covered individual linked list operations, here's a complete example that demonstrates how to use them together in a small task manager app:

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        // Create a LinkedList of Strings
        LinkedList<String> tasks = new LinkedList<>();

        // Check if the list is empty initially
        if (tasks.isEmpty()) {
            System.out.println("Task list is empty.\n");
        }

        // Add elements to the LinkedList
        tasks.add("Buy groceries");
        tasks.add("Pay bills");
        tasks.addFirst("Check email");  // Add to the beginning
        tasks.addLast("Read book");  // Add to the end

        // Print all tasks
        System.out.println("Task List:");
        for (String task : tasks) {
            System.out.println("- " + task);
        }

        // Access first and last elements
        System.out.println("\nFirst task: " + tasks.getFirst());
        System.out.println("Last task: " + tasks.getLast());

        // Modify a task
        tasks.set(1, "Respond to emails");
        System.out.println("\nAfter modifying task at index 1: " + tasks);

        // Check if a task exists
        if (tasks.contains("Pay bills")) {
            System.out.println("\nFound task: Pay bills");
        } else {
            System.out.println("\nTask 'Pay bills' not found");
        }

        // Remove tasks
        tasks.remove("Pay bills");  // Remove by value
        tasks.removeFirst();  // Remove first task (head)
        System.out.println("\nAfter removing tasks: " + tasks);

        // Clear all tasks
        tasks.clear();

        // Confirm the list is now empty
        System.out.println("\nList cleared.");
        if (tasks.isEmpty()) {
            System.out.println("Task list is now empty.");
        }
    }
}

This example demonstrates how to use various Linked list methods to manage a list of tasks, including adding, modifying, accessing, and removing tasks. You can easily adapt this structure for other applications that require dynamic data handling and sequential operations.

When to use LinkedList

• LinkedList is ideal when your application frequently adds or removes elements from the beginning or end, as these operations have constant-time complexity O(1) because they do not require shifting elements, unlike arrays or ArrayList.

• LinkedList supports operations at both ends, making it a natural fit for implementing abstract data types such as queues (FIFO), stacks (LIFO), and deques (double-ended queues) using addFirst(), addLast(), removeFirst(), and removeLast().

• Simple traversal is not faster in a LinkedList compared to an ArrayList. However, LinkedList is more efficient when you need to insert or remove elements while iterating through the list using an iterator.

Limitations and considerations

• Accessing an element by its index requires traversal from the beginning or end of the list until the index is reached, making it inefficient for large lists where random access is frequent.

• Each node in a LinkedList stores two additional references (to the previous and next node), which increases the memory footprint compared to arrays that only store values.

• Because elements are spread out in memory rather than placed next to each other, accessing them sequentially is slower compared to arrays, which benefit from CPU caching.

• Unlike arrays or ArrayList, where elements can be accessed instantly by index, LinkedList requires walking through the list to find the desired element, making it unsuitable for use cases that demand fast lookups.

Conclusion

The linked list is a dynamic data structure that excels in scenarios requiring frequent, fast insertions and deletions. While it may not be suitable for all use cases—especially those needing fast index-based access—it provides great flexibility and efficiency for sequential operations and complex data handling patterns. With its implementation of List, Deque, and Queue, it is a powerful utility in Java’s collection toolbox.