How can I create an array of linked lists in java?

Learn how can i create an array of linked lists in java? with practical examples, diagrams, and best practices. Covers java, graph, linked-list development techniques with visual explanations.
Tags:
Categories:

Mastering Data Structures: Implementing an Array of Linked Lists in Java

Hero image for How can I create an array of linked lists in java?

Explore the concept and practical implementation of an array of linked lists in Java, a versatile data structure often used for adjacency lists in graph representations.

In computer science, combining fundamental data structures can lead to powerful and efficient solutions for complex problems. An 'array of linked lists' is a prime example of such a combination. This structure is particularly useful when you need dynamic storage at each index, such as representing an adjacency list in a graph, where each vertex can have a varying number of neighbors. This article will guide you through understanding, implementing, and utilizing an array of linked lists in Java.

Understanding the Structure: Array of Linked Lists

At its core, an array of linked lists is exactly what it sounds like: an array where each element (or 'bucket') is a reference to the head of a linked list. Instead of storing a single value, each array index points to an entire sequence of values, which can grow or shrink dynamically. This hybrid approach leverages the constant-time access of arrays for initial lookup and the flexible insertion/deletion capabilities of linked lists.

graph TD
    A[Array Index 0] --> B(Linked List Head 0)
    B --> C(Node 1)
    C --> D(Node 2)
    A[Array Index 1] --> E(Linked List Head 1)
    E --> F(Node 1)
    A[Array Index 2] --> G(Linked List Head 2)
    G --> H(Node 1)
    H --> I(Node 2)
    I --> J(Node 3)
    A[Array Index 3] --> K(null)
    style A fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style G fill:#f9f,stroke:#333,stroke-width:2px
    style K fill:#f9f,stroke:#333,stroke-width:2px

Conceptual diagram of an array of linked lists

Implementation in Java

Java provides the java.util.LinkedList class, which simplifies the process significantly. You can declare an array where each element is of type LinkedList<T>, where T is the type of data you want to store in your linked lists. Alternatively, you can implement your own Node and LinkedList classes for more control, though for most applications, using Java's built-in LinkedList is sufficient and recommended.

import java.util.LinkedList;

public class ArrayOfLinkedLists {

    private LinkedList<Integer>[] arrayOfLists;
    private int size;

    public ArrayOfLinkedLists(int capacity) {
        this.size = capacity;
        // Initialize the array with LinkedList objects
        arrayOfLists = new LinkedList[capacity];
        for (int i = 0; i < capacity; i++) {
            arrayOfLists[i] = new LinkedList<>();
        }
    }

    // Method to add an element to a specific linked list
    public void addElement(int arrayIndex, int value) {
        if (arrayIndex >= 0 && arrayIndex < size) {
            arrayOfLists[arrayIndex].add(value);
        } else {
            System.out.println("Invalid array index.");
        }
    }

    // Method to get a linked list at a specific index
    public LinkedList<Integer> getLinkedList(int arrayIndex) {
        if (arrayIndex >= 0 && arrayIndex < size) {
            return arrayOfLists[arrayIndex];
        } else {
            System.out.println("Invalid array index. Returning null.");
            return null;
        }
    }

    // Method to print the entire structure
    public void printStructure() {
        for (int i = 0; i < size; i++) {
            System.out.print("Array Index " + i + ": ");
            if (arrayOfLists[i].isEmpty()) {
                System.out.println("[]");
            } else {
                System.out.println(arrayOfLists[i]);
            }
        }
    }

    public static void main(String[] args) {
        ArrayOfLinkedLists aol = new ArrayOfLinkedLists(5);

        aol.addElement(0, 10);
        aol.addElement(0, 20);
        aol.addElement(1, 30);
        aol.addElement(3, 40);
        aol.addElement(3, 50);
        aol.addElement(3, 60);

        aol.printStructure();

        System.out.println("\nLinked List at index 0: " + aol.getLinkedList(0));
        System.out.println("Linked List at index 2: " + aol.getLinkedList(2));
    }
}

Basic Java implementation of an array of LinkedList objects.

Common Use Cases: Adjacency Lists for Graphs

One of the most prominent applications of an array of linked lists is in representing graphs, specifically as an adjacency list. In this scenario, each index in the array corresponds to a vertex in the graph, and the linked list at that index stores all the vertices adjacent to it. This representation is efficient for sparse graphs (graphs with relatively few edges) because it only stores existing connections, unlike an adjacency matrix which stores all possible connections.

import java.util.LinkedList;

public class GraphAdjacencyList {
    private int V; // Number of vertices
    private LinkedList<Integer>[] adj;

    // Constructor
    public GraphAdjacencyList(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // Function to add an edge into the graph
    public void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's list.
        // For an undirected graph, you would also add: adj[w].add(v);
    }

    // Prints the adjacency list representation of the graph
    public void printGraph() {
        for (int i = 0; i < V; ++i) {
            System.out.print("Vertex " + i + ":");
            for (Integer node : adj[i]) {
                System.out.print(" -> " + node);
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        GraphAdjacencyList g = new GraphAdjacencyList(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Adjacency List representation of the graph:");
        g.printGraph();
    }
}

Implementing a graph using an array of linked lists (adjacency list).