Java Program to Implement LinkedList

Introduction

A LinkedList in Java is a fundamental data structure that consists of a series of elements called nodes. Each node holds data and a reference to the next node, making it a dynamic and efficient structure for various applications like managing ordered data and implementing queues and stacks. LinkedLists are particularly useful in scenarios where frequent addition and removal of elements are required.

In this article, you will learn how to effectively implement a LinkedList from scratch in Java. Discover the core operations involved in this data structure through step-by-step examples, including the insertion, deletion, and traversal of nodes.

Implementing a Simple LinkedList

Basic Structure of a Node

1. Define a Node class that will represent each element in the LinkedList.

2. Include attributes for the data stored and the reference to the next Node.

   java Copy

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

   This code defines a Node class with a constructor to initialize the node's data. The next attribute is used to point to the next node in the list.

Creating the LinkedList Class

1. Declare a LinkedList class with the initial head of the list.

2. Implement the add method to insert new elements.

   java Copy

   class LinkedList {
       Node head; // head of the list
   
       // Method to insert a new node
       public void add(int data) {
           Node newNode = new Node(data);
           if (head == null) {
               head = newNode;
           } else {
               Node last = head;
               while (last.next != null) {
                   last = last.next;
               }
               last.next = newNode;
           }
       }
   }
   

   The add method creates a new node with the given data and adds it to the end of the list. If the list is empty, the new node becomes the head.

Implementing Method to Display the List

1. Define a method in the LinkedList class to display all nodes.

2. Traverse from the head to the end, printing each node's data.

   java Copy

   public void display() {
       Node current = head;
       while (current != null) {
           System.out.print(current.data + " -> ");
           current = current.next;
       }
       System.out.println("null");
   }
   

   This method iterates through the list from the head, printing the data in each node, followed by an arrow to indicate the link to the next node.

Enhancing LinkedList Functionality

Adding Nodes at Specific Positions

1. Implement a method to add nodes at a specified index in the list.

2. Consider edge cases such as adding at the start and beyond the current size.

   java Copy

   public void addAtPosition(int index, int data) {
       Node newNode = new Node(data);
       if (index == 0) {
           newNode.next = head;
           head = newNode;
           return;
       }
       Node current = head;
       for (int i = 0; i < index - 1; i++) {
           if (current == null) return; // index out of bounds
           current = current.next;
       }
       newNode.next = current.next;
       current.next = newNode;
   }
   

   This method allows inserting a node at any valid position, with checks to ensure the operation stays within bounds.

Removing Nodes

1. Add a method to remove nodes based on their value.

2. Traverse the list to locate the node and modify links to omit the node.

   java Copy

   public void remove(int data) {
       if (head == null) return;
   
       if (head.data == data) {
           head = head.next;
           return;
       }
   
       Node current = head;
       while (current.next != null) {
           if (current.next.data == data) {
               current.next = current.next.next;
               return;
           }
           current = current.next;
       }
   }
   

   The removal method checks if the node to be removed is the head or elsewhere in the list, adjusting the links accordingly to remove the node.

Conclusion

Implementing a LinkedList in Java helps understand fundamental data structure concepts and provides a strong foundation for more complex data manipulation tasks. By implementing a LinkedList, as shown above, you gain the ability to handle dynamic data effectively. This provides flexibility for operations like adding and removing elements, which are crucial in many real-world applications. Through the examples provided, you now have the tools to craft a LinkedList suited to any particular requirement, ensuring efficient management of data sequences in your Java programs.