Sorted Linked List Program in Java — Step by Step Explanation

In this article, we will break a large Java program into multiple small programs so that students can understand the concept of Linked List gradually and clearly.

The final goal is to learn how to insert a node into a Sorted Linked List.

---

Step 1: Understanding a Node

A Linked List is made up of multiple nodes. Each node contains:

• Data — stores the value
• Link — stores the reference/address of the next node

class Node {
    int data;
    Node link;

    Node() {
        data = 0;
        link = null;
    }

    Node(int d) {
        data = d;
        link = null;
    }
}

class TestNode {
    public static void main(String[] args) {
        Node n1 = new Node(10);

        System.out.println("Data: " + n1.data);
        System.out.println("Link: " + n1.link);
    }
}

Explanation

The Node class represents a single node of the linked list.

Here:

• data stores the value
• link stores the reference of the next node

Since there is only one node, the link part contains null.

---

Step 2: Linking Two Nodes

Now we will create two nodes and connect them together.

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkTwoNodes {
    public static void main(String[] args) {
        Node first = new Node(10);
        Node second = new Node(20);

        first.link = second;

        System.out.println(first.data);
        System.out.println(first.link.data);
    }
}

Explanation

The statement:

first.link = second;

connects the first node to the second node.

Now the structure becomes:

10 → 20

---

Step 3: Creating a Linked List Class

A Linked List needs a starting point. That starting point is called start.

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {
    Node start;

    LinkedList() {
        start = null;
    }

    boolean isEmpty() {
        return start == null;
    }
}

class TestList {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        if (list.isEmpty()) {
            System.out.println("List is empty");
        }
    }
}

Explanation

The variable start stores the reference of the first node of the linked list.

If start is null, the list is empty.

---

Step 4: Inserting the First Node

When the list is empty, the new node becomes the first node.

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {
    Node start;

    LinkedList() {
        start = null;
    }

    void insertFirst(int value) {
        Node newNode = new Node(value);
        start = newNode;
    }

    void display() {
        System.out.println(start.data);
    }
}

class TestInsertFirst {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertFirst(10);
        list.display();
    }
}

Explanation

The method insertFirst() creates a node and stores its reference in start.

---

Step 5: Inserting a Node at the Beginning

To insert a node at the beginning:

1. The new node points to the current first node
2. start becomes the new node

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {
    Node start;

    void insertAtBeginning(int value) {
        Node newNode = new Node(value);

        newNode.link = start;
        start = newNode;
    }

    void display() {
        Node ptr = start;

        while (ptr != null) {
            System.out.print(ptr.data + " -> ");
            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestBeginning {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertAtBeginning(30);
        list.insertAtBeginning(20);
        list.insertAtBeginning(10);

        list.display();
    }
}

Output

10 -> 20 -> 30 -> NULL

---

Step 6: Inserting a Node at the End

To insert a node at the end:

• Move to the last node
• Store the new node reference in the last node’s link part

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {
    Node start;

    void insertAtEnd(int value) {
        Node newNode = new Node(value);

        if (start == null) {
            start = newNode;
            return;
        }

        Node ptr = start;

        while (ptr.link != null) {
            ptr = ptr.link;
        }

        ptr.link = newNode;
    }

    void display() {
        Node ptr = start;

        while (ptr != null) {
            System.out.print(ptr.data + " -> ");
            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestEnd {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);

        list.display();
    }
}

Output

10 -> 20 -> 30 -> NULL

---

Step 7: Inserting a Node into a Sorted Linked List

In a sorted linked list, values remain in ascending order.

The new node must be inserted at the correct position.

class Node {
    int data;
    Node link;

    Node(int d) {
        data = d;
        link = null;
    }
}

class LinkedList {
    Node start;

    void insertSorted(int value) {
        Node newNode = new Node(value);

        if (start == null || value <= start.data) {
            newNode.link = start;
            start = newNode;
            return;
        }

        Node save = start;
        Node ptr = start.link;

        while (ptr != null && value > ptr.data) {
            save = ptr;
            ptr = ptr.link;
        }

        save.link = newNode;
        newNode.link = ptr;
    }

    void display() {
        Node ptr = start;

        while (ptr != null) {
            System.out.print(ptr.data + " -> ");
            ptr = ptr.link;
        }

        System.out.println("NULL");
    }
}

class TestSortedInsert {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        list.insertSorted(5);
        list.insertSorted(3);
        list.insertSorted(8);
        list.insertSorted(9);
        list.insertSorted(2);

        list.display();
    }
}

Output

2 -> 3 -> 5 -> 8 -> 9 -> NULL

---

How Sorted Insertion Works

Suppose the linked list contains:

3 -> 5 -> 8 -> NULL

Now we want to insert 6.

The program checks where 6 fits correctly.

Since:

5 < 6 < 8

the node containing 6 is inserted between 5 and 8.

3 -> 5 -> 6 -> 8 -> NULL

---

Important Concepts Used

• Class and Object
• Constructor
• Reference Variable
• Node Traversal
• Linked List
• Insertion at Beginning
• Insertion at End
• Sorted Insertion

---

Recommended Teaching Sequence

1. Understand what a node is
2. Create one node
3. Connect two nodes
4. Create a linked list using start
5. Insert the first node
6. Insert at beginning
7. Insert at end
8. Insert into sorted linked list

---

Key Learning

A linked list stores elements dynamically using nodes. Each node contains data and a link to the next node.

In sorted insertion, the correct position is found first, and then the new node is inserted while maintaining the sorted order of the list.