Linked Lists in Java: Understand and Implement Singly and Doubly Linked Lists with Code Examples

1. What is a Linked List and Why Use It?

A linked list is a linear data structure where elements (nodes) point to the next node, forming a chain. Unlike arrays, they don't require contiguous memory and allow dynamic resizing.

Advantages:

• Efficient insertions and deletions

• No memory waste due to fixed size

• Useful in implementing stacks, queues, and graphs.

2. Structure of a Singly Linked List

A singly linked list consists of nodes, where each node contains:

• data: the value stored

• next: reference to the next node

Example Implementation

class Node {

    int data;

    Node next;

    Node(int data) {

        this.data = data;

        this.next = null;

    }

}

3. Implementing a Singly Linked List in Java

Let's create a simple singly linked list with insert and display functionality.

public class SinglyLinkedList {
    Node head;

    void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
    }

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

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.display(); // Output: 10 -> 20 -> 30 -> null
    }
}

4. Structure and Functioning of a Doubly Linked List

A doubly linked list has nodes with three parts:

• data: value

• prev: pointer to previous node

• next: pointer to next node

This allows traversal in both directions (forward and backward).

Node Example:

class DNode {

    int data;

    DNode prev, next;

    DNode(int data) {

        this.data = data;

    }

}

5. Implementing a Doubly Linked List in Java

public class DoublyLinkedList {
    DNode head;

    void insert(int data) {
        DNode newNode = new DNode(data);
        if (head == null) {
            head = newNode;
            return;
        }
        DNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = newNode;
        newNode.prev = current;
    }

    void displayForward() {
        DNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

6. When to Use Linked Lists Over Arrays?

Feature	Array	Linked List
Memory usage	Fixed, contiguous	Dynamic, scattered
Insert/Delete	Costly	Efficient
Random access	O(1)	O(n)
Search performance	Fast	Slower

Use Linked List:

• When frequent insertions/deletions are required

• When the size of the data is unknown or dynamic

This Content Sponsored by Buymote Shopping app

BuyMote E-Shopping Application is One of the Online Shopping App

Now Available on Play Store & App Store (Buymote E-Shopping)

Click Below Link and Install Application: https://buymote.shop/links/0f5993744a9213079a6b53e8

Sponsor Content: #buymote #buymoteeshopping #buymoteonline #buymoteshopping #buymoteapplication