How to Implement LinkedList in Java?

Linkedlists are among the essential data structures in computer science. They have versatile applications, from serving as the underlying structure for stacks and queues to more complex data storage models. While Java offers a built-in LinkedList class through its Collections Framework, understanding how to implement one from scratch can provide valuable insights into data structures.

In this article, we’ll explore how to implement a singly linked list in Java, incorporating functionalities like node insertion, deletion, and traversal.

Table of Contents

1. The Node Class
2. LinkedList Class
3. Basic Operations
4. Inserting an Element
5. Deleting an Element
6. Example Usage
7. Conclusion
8. External Resources

The Node Class

In a singly linked list, each element is a node that contains data and a reference to the next node. Here’s how we represent a node:

public class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

For a deeper understanding of how nodes function, you can refer to this Node in LinkedList article.

LinkedList Class

The LinkedList class encapsulates our list’s logic and holds the head node.

public class LinkedList {
    Node head;

    // Insert at the end
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Insert at the beginning
    public void prepend(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // Delete a node
    public void delete(int data) {
        if (head == null) return;

        if (head.data == data) {
            head = head.next;
            return;
        }

        Node temp = head;
        while (temp.next != null && temp.next.data != data) {
            temp = temp.next;
        }

        if (temp.next != null) {
            temp.next = temp.next.next;
        }
    }

    // Print the list
    public void printList() {
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("null");
    }
}

For detailed class tutorials, check this Java Classes and Objects tutorial.

Basic Operations

Inserting an Element

• At the beginning (prepend method): Inserting at the beginning is an (O(1)) operation.
• At the end (append method): Inserting at the end involves traversing the list, making it an (O(n)) operation.

For an in-depth discussion on time complexity, refer to Big O Notation Guide.

Deleting an Element

• If it’s the head node, set the head to the next node.
• Otherwise, traverse to the node preceding the one to be deleted and update its next reference.

For more detailed steps, you can check Deleting a Node in LinkedList.

Example Usage

Here’s an example to use our LinkedList class:

public class Main {
    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.append(5);
        linkedList.append(10);
        linkedList.printList(); // Output should be: 5 -> 10 -> null
        // ... further operations
    }
}

Conclusion

This article covered the basics of implementing a singly linked list in Java, from defining the Node class to creating a LinkedList class that supports various operations. Understanding these fundamentals will make it easier to grasp more complex data structures and algorithms.

External Resources

• Java LinkedList class documentation
• GeeksforGeeks LinkedList tutorials
• Big O Notation Explained

Happy coding!