Linked List in Java

A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations, and they can dynamically grow or shrink in size. The basic operations on a linked list include insertion, deletion, and traversal. Here's an explanation of these operations:

1. Insertion: To insert a new node into a linked list, you typically have three scenarios:

   • Insertion at the beginning: Create a new node with the desired value and update its next pointer to point to the current head of the list. Then, update the head pointer to the new node, making it the new first node of the list.

   • Insertion at the end: Traverse the linked list until you reach the last node. Create a new node with the desired value and update the next pointer of the last node to point to the new node, making it the new last node of the list.

   • Insertion at a specific position: Traverse the linked list until you reach the node before the desired position. Create a new node with the desired value and update its next pointer to the next node. Then, update the next pointer of the previous node to point to the new node, effectively inserting it into the desired position.

2. Deletion: To delete a node from a linked list, you typically have three scenarios:

   • Deletion of the first node: Update the head pointer to point to the next node, effectively removing the first node from the list.

   • Deletion of the last node: Traverse the linked list until you reach the second-to-last node. Update its next pointer to null, effectively removing the last node from the list.

   • Deletion of a specific node: Traverse the linked list until you reach the node before the node is deleted. Update its next pointer to skip the node to be deleted, effectively removing it from the list.

3. Traversal: To traverse a linked list, you start from the head node and follow the next pointers until you reach the end of the list (where the next pointer is null). During traversal, you can access and process the value of each node.

Linked lists are particularly useful when you need efficient insertions and deletions at arbitrary positions within the list, as these operations can be performed in constant time (O(1)) with appropriate pointers manipulation. However, accessing an element by index in a linked list takes linear time (O(n)), as you need to traverse the list from the beginning to the desired position.

It's important to note that there are different variations of linked lists, such as singly linked lists (with a reference to the next node only) and doubly linked lists (with references to both the next and previous nodes). Doubly linked lists allow for efficient traversal in both directions but require additional memory to store the previous pointers.

Code Snippet

Here is the basic code to create a LinkedList in java

public class LinkedList<T> {
    private Node<T> head;
    private Node<T> tail;
    public void insert(T data) {
        Node<T> node = new Node<T>(data);

        if (this.head == null)
            this.setHead(node);
        else
            this.getTail().setNext(node);
        this.setTail(node);
    }

    public void show() {
        Node<T> n = this.head;
        System.out.print("[");
        while (n.getNext() != null) {
            System.out.print(n.getData().toString() + ", ");
            n = n.getNext();
        }
        System.out.println(n.getData().toString() + "]");
    }

    public Node<T> getHead() {
        return head;
    }

    public void setHead(Node<T> head) {
        this.head = head;
    }

    public Node<T> getTail() {
        return tail;
    }

    public void setTail(Node<T> tail) {
        this.tail = tail;
    }

    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.insert("Tiger");
        linkedList.insert("Lion");
        linkedList.insert("Dog");
        linkedList.show();
    }

}

class Node<T> {
    private T data;
    private Node<T> next;    
    public Node() {
    }    
    public Node(T data) {
        this.data = data;
        this.next=null;
    }

    public T getData() {
        return data;
    }
    public void setData(T data) {
        this.data = data;
    }
    public Node<T> getNext() {
        return next;
    }
    public void setNext(Node<T> next) {
        this.next = next;
    }    
}

OUTPUT:

[Tiger, Lion, Dog]

Java Provides a predefined LInkesList Class in the Collection framework, here is an example.

import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("TeleVision");
        list.add("Mobile");
        list.add("EarPhone");        
        System.out.println(list.toString());
    }
}

OUTPUT:

[TeleVision, Mobile, EarPhone]