How to implement my own LinkedList<LinkedList> data structure in Java?

Implementing a Nested LinkedList in Java

Explore how to create a custom LinkedList<LinkedList<T>> data structure in Java, understanding its components and practical applications.

In Java, a LinkedList is a dynamic data structure that stores elements in nodes, where each node contains data and a reference (or link) to the next node in the sequence. While Java's java.util.LinkedList is robust, there are scenarios where you might need a more complex, custom structure, such as a LinkedList where each node itself holds another LinkedList. This article will guide you through implementing such a nested structure, discussing its design, implementation, and potential use cases.

Understanding the Nested LinkedList Concept

A LinkedList<LinkedList<T>> implies a primary linked list where each element is not a simple data type (like an integer or string) but rather an entire LinkedList of type T. This creates a two-dimensional, yet dynamically sized, structure. Think of it as a list of rows, where each row is itself a list of elements. This can be particularly useful for representing sparse matrices, adjacency lists in graph theory, or hierarchical data where each level can grow independently.

graph TD
    Start[Start] --> A(Outer LinkedList Node 1)
    A --> B(Outer LinkedList Node 2)
    B --> C(Outer LinkedList Node 3)
    C --> End[End]

    subgraph Inner LinkedList for Node 1
        A1[Inner Node 1.1] --> A2[Inner Node 1.2]
        A2 --> A3[Inner Node 1.3]
    end

    subgraph Inner LinkedList for Node 2
        B1[Inner Node 2.1] --> B2[Inner Node 2.2]
    end

    subgraph Inner LinkedList for Node 3
        C1[Inner Node 3.1]
    end

    A --- A1
    B --- B1
    C --- C1

Conceptual diagram of a Nested LinkedList structure

Designing the Node Structure

To implement a custom LinkedList<LinkedList<T>>, we first need to define a Node class for the outer linked list. This Node will hold a reference to an inner LinkedList (which can be java.util.LinkedList or another custom implementation) and a reference to the next Node in the outer list. For simplicity, we'll use java.util.LinkedList for the inner lists.

import java.util.LinkedList;

public class NestedLinkedList<T> {

    private Node<T> head;
    private int size;

    // Node class for the outer LinkedList
    private static class Node<T> {
        LinkedList<T> data;
        Node<T> next;

        public Node(LinkedList<T> data) {
            this.data = data;
            this.next = null;
        }
    }

    public NestedLinkedList() {
        this.head = null;
        this.size = 0;
    }

    // Methods for adding, removing, etc., will go here
}

Basic NestedLinkedList class with its Node definition

Implementing Core Operations

Now, let's add some fundamental operations to our NestedLinkedList class. We'll focus on adding new inner linked lists to the outer list and accessing them. For brevity, we'll implement add and get methods.

import java.util.LinkedList;
import java.util.NoSuchElementException;

public class NestedLinkedList<T> {

    private Node<T> head;
    private int size;

    private static class Node<T> {
        LinkedList<T> data;
        Node<T> next;

        public Node(LinkedList<T> data) {
            this.data = data;
            this.next = null;
        }
    }

    public NestedLinkedList() {
        this.head = null;
        this.size = 0;
    }

    /**
     * Adds a new inner LinkedList to the end of the outer list.
     * @param innerList The LinkedList to add.
     */
    public void add(LinkedList<T> innerList) {
        Node<T> newNode = new Node<>(innerList);
        if (head == null) {
            head = newNode;
        } else {
            Node<T> current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    /**
     * Retrieves the inner LinkedList at the specified index.
     * @param index The index of the inner LinkedList to retrieve.
     * @return The LinkedList at the specified index.
     * @throws IndexOutOfBoundsException if the index is out of range.
     */
    public LinkedList<T> get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current = head;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    /**
     * Returns the number of inner LinkedLists in this NestedLinkedList.
     * @return The size of the outer LinkedList.
     */
    public int size() {
        return size;
    }

    /**
     * Example usage to demonstrate the NestedLinkedList.
     */
    public static void main(String[] args) {
        NestedLinkedList<String> nestedList = new NestedLinkedList<>();

        LinkedList<String> list1 = new LinkedList<>();
        list1.add("Apple");
        list1.add("Banana");
        nestedList.add(list1);

        LinkedList<String> list2 = new LinkedList<>();
        list2.add("Carrot");
        nestedList.add(list2);

        LinkedList<String> list3 = new LinkedList<>();
        list3.add("Date");
        list3.add("Elderberry");
        list3.add("Fig");
        nestedList.add(list3);

        System.out.println("Nested List Size: " + nestedList.size()); // Output: 3

        // Accessing inner lists and their elements
        for (int i = 0; i < nestedList.size(); i++) {
            LinkedList<String> inner = nestedList.get(i);
            System.out.println("Inner List at index " + i + ": " + inner);
        }

        // Example of adding to an inner list after retrieval
        nestedList.get(1).add("Grape");
        System.out.println("Inner List at index 1 after modification: " + nestedList.get(1));
    }
}

Complete NestedLinkedList implementation with add, get, size, and a main method for demonstration.

Potential Applications and Considerations

A NestedLinkedList can be a powerful tool for specific data modeling challenges:

• Sparse Matrices: Each outer node could represent a row, and the inner list could store only the non-zero elements along with their column indices.
• Adjacency Lists for Graphs: Each outer node represents a vertex, and its inner list contains the vertices adjacent to it.
• Hierarchical Data: Representing tree-like structures where each level can have a variable number of children, and each child is itself a list.

Considerations:

• Performance: Accessing an element in an inner list requires first traversing the outer list to find the correct inner list, and then traversing the inner list. This can lead to O(N*M) complexity in the worst case for deep access, where N is the outer list size and M is the inner list size.
• Memory Overhead: Each Node in both the outer and inner lists incurs memory overhead for references. For very small inner lists, this might be less efficient than a simple ArrayList<ArrayList<T>>.
• Generics: The use of generics <T> makes the NestedLinkedList type-safe and reusable for any data type.