A Comprehensive Guide to LinkedList Implementation in Java

Linked lists are fundamental data structures in computer science that provide dynamic memory allocation and efficient insertion and deletion operations. In Java, the LinkedList class from the java.util package is commonly used to implement linked lists. This article will guide you through the implementation of a basic linked list in Java, covering key concepts and operations.

public class Node {
    int data;
    Node next;

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

    void displayNode() {
        System.out.print("{" + data + "} ");
    }
}

public class LinkedList {
    private Node head;
    public void LinkList() {
        head = null;
    }
    public boolean isEmpty() {
     if(head == null) {
         return true;
     } else {
         return false;
     }
    }
    public void insertFirst(int i) {
        Node newNode = new Node(i);
        newNode.next = head;
        head = newNode;
    }
    public Node deleteFirst() {
        Node temp = head;
        head = head.next;
        return temp;
    }
    public void displayList() {
        System.out.println("List (first --> last)");
        Node current = head;
        while(current != null) {
            current.displayNode();
            current = current.next;
        }
        System.out.println();
    }
    public Node find(int key) {
        Node current = head;
        while(current.data != key) {
            if(current.next == null) {
                return null;
            } else {
                current = current.next;
            }
        }
        return current;
    }
    public void delete(int key) {
        Node current = head;
        Node previous = head;
        while(current.data != key) {
            if(current.next == null) {
                System.out.println("Node not found");
            } else {
                previous = current;
                current = current.next;
            }
        }
        if(current == head) {
            head = head.next;
        } else {
            previous.next = current.next;
        }
    }
    public void insertLast(int i) {
        Node current = head;
        while(current.next != null) {
            current = current.next;
        }
        Node newNode = new Node(i);
        current.next = newNode;
    }
    public void insertMiddle(int i) {
        Node current = head;
        int count = 0;
        while(current.next != null) {
            current = current.next;
            count++;
        }
        int middle = count / 2;
        current = head;
        for(int j = 0; j < middle; j++) {
            current = current.next;
        }
        Node newNode = new Node(i);
        newNode.next = current.next;
        current.next = newNode;
    }
}

public class Main {
    public static void main(String[] args) {

        LinkedList myList = new LinkedList();
        myList.insertFirst(100);
        myList.insertFirst(50);
        myList.insertFirst(99);
        myList.insertFirst(88);
        myList.insertFirst(77);
        myList.insertFirst(66);
        myList.insertFirst(55);
        myList.insertFirst(44);
        myList.insertFirst(33);
        myList.insertFirst(22);
        myList.insertFirst(11);
        myList.insertFirst(00);
        myList.displayList();
        myList.delete(99);
        System.out.println("After deleting 99");
        myList.displayList();
        myList.deleteFirst();
        System.out.println("After deleting first");
        myList.displayList();
        System.out.println(myList.find(100).data);
        System.out.println(myList.isEmpty());
        myList.insertLast(9999);
        System.out.println("After inserting 9999");
        myList.displayList();
        myList.insertMiddle(8888);
        System.out.println("After inserting 8888");
        myList.displayList();
    }
}

Output:

List (first → last)
{0} {11} {22} {33} {44} {55} {66} {77} {88} {99} {50} {100}
After deleting 99
List (first → last)
{0} {11} {22} {33} {44} {55} {66} {77} {88} {50} {100}
After deleting first
List (first → last)
{11} {22} {33} {44} {55} {66} {77} {88} {50} {100}
100
false
After inserting 9999
List (first → last)
{11} {22} {33} {44} {55} {66} {77} {88} {50} {100} {9999}
After inserting 8888
List (first → last)
{11} {22} {33} {44} {55} {66} {8888} {77} {88} {50} {100} {9999}

Doubly linked list

A doubly linked list is a type of linked list where each node in the list contains data and two pointers, one pointing to the next node in the sequence (commonly referred to as next or forward pointer) and another pointing to the previous node (commonly referred to as prev or backward pointer). Unlike a singly linked list where each node only points to the next node, a doubly linked list allows for bidirectional traversal.

Doubly linked lists are particularly useful in scenarios where bidirectional traversal is required, and there is a frequent need for insertion and deletion operations. Common use cases include implementing undo/redo functionality in applications, and navigation systems, and managing data structures in certain algorithms.

In Java, the java.util.LinkedList class is an example of a doubly linked list implementation.