Java Data Structures Linked List

How to Create a `Linked List` Data Structure in `Java`

Creating a data structure that effectively manages a collection of elements can be a challenge in programming. One of the most commonly used structures is the Linked List. In this blog post, we will walk you through the process of creating a Linked List in Java, even if there’s already a built-in class available in the Java standard library.

Understanding the Problem

When you think of data structures, you might think about arrays, but sometimes they fall short. This is where linked lists come into play. A Linked List allows you to efficiently insert and delete elements without needing to resize an array. It consists of a sequence of nodes where each node contains data and a reference to the next node.

The Built-in Option

Java provides a built-in LinkedList class in the java.util package, which is convenient and suitable for many situations. However, being able to create your own implementation can deepen your understanding and give you more control over the behavior of the data structure.

Creating Your Own `Linked List`

Below, we will explore building our own simple Linked List from scratch. For this tutorial, we’ll focus on a singly linked list that allows inserting and deleting nodes from the beginning.

Step 1: Define the Link Class

First, we need to create a Link class to represent each element in the list. Here’s how it looks in code:

class Link {
    public int data1;
    public double data2;
    public Link nextLink;

    // Link constructor
    public Link(int d1, double d2) {
        data1 = d1;
        data2 = d2;
    }

    // Print Link data
    public void printLink() {
        System.out.print("{" + data1 + ", " + data2 + "} ");
    }
}

Step 2: Define the LinkList Class

Next, we need a class for the entire list itself:

class LinkList {
    private Link first;

    // LinkList constructor
    public LinkList() {
        first = null;
    }

    // Returns true if list is empty
    public boolean isEmpty() {
        return first == null;
    }

    // Inserts a new Link at the beginning of the list
    public void insert(int d1, double d2) {
        Link link = new Link(d1, d2);
        link.nextLink = first;
        first = link;
    }

    // Deletes the link at the front of the list
    public Link delete() {
        Link temp = first;
        if (first == null) {
            return null; // or throw Exception
        }
        first = first.nextLink;
        return temp;
    }

    // Prints all links in the list
    public void printList() {
        Link currentLink = first;
        System.out.print("List: ");
        while (currentLink != null) {
            currentLink.printLink();
            currentLink = currentLink.nextLink;
        }
        System.out.println("");
    }
}

Step 3: Testing the LinkList

Finally, let’s implement a main method to test our Linked List:

class LinkListTest {
    public static void main(String[] args) {
        LinkList list = new LinkList();

        // Insert some elements
        list.insert(1, 1.01);
        list.insert(2, 2.02);
        list.insert(3, 3.03);
        list.insert(4, 4.04);
        list.insert(5, 5.05);

        // Print the list
        list.printList();

        // Delete elements
        while (!list.isEmpty()) {
            Link deletedLink = list.delete();
            System.out.print("deleted: ");
            deletedLink.printLink();
            System.out.println("");
        }
        list.printList();
    }
}

Conclusion

In this blog post, we explored how to create a custom Linked List in Java, complete with essential methods for inserting, deleting, and printing nodes. While the native LinkedList class in Java’s standard library may suffice for many applications, implementing your own can be a rewarding experience that enhances your programming skills.

Further Enhancements

Upon mastering this basic implementation, consider adding:

Double-linked List: Each node should have references to both next and previous nodes.
Insert/Delete Middle/End: Methods for adding or removing nodes from various positions.
Get and Sort Methods: Functions to retrieve specific elements or sort the linked list.

Getting familiar with these enhancements can take your skill set to the next level. Happy coding!

How to Create a Linked List Data Structure in Java