ISC Practicals and Theory - Singly Linked List

A singly linked list is a chain of nodes in which each node stores a value and a reference to the next node, so elements can be added and removed without shifting any array. This is the classic ISC form: class Node for one node, class SinglyList with a head reference, void methods that read their own input and print their own messages, and a menu in main.

Definition

A single linked list is a data structure made of nodes. Each node has two parts: data (the value) and next (a reference to the following node). The reference head points to the first node, and the next of the last node is null. An empty list has head == null. Nodes are created one at a time with new Node(...), so the list has no fixed size.

For example, the list holding 10, 20 and 30 is shown as:

10 -> 20 -> 30 -> null

Here head refers to the node holding 10.

Algorithm

1. In main, create obj = new SinglyList(); the constructor sets head = null. Repeat the menu until the choice is 8: print the menu, read choice and call the matching method. Any other number prints Invalid choice. Enter 1 to 8.
2. insertFront(): read v, create p = new Node(v), set p.next = head, then head = p.
3. insertEnd(): read v and create p.
   • If head == null, set head = p.
   • Otherwise start with t = head and move t = t.next while t.next != null; then set t.next = p.
4. deleteFront(): if head == null print a message; otherwise save head.data, set head = head.next and print the value.
5. deleteValue(): read v.
   • If the list is empty, print a message.
   • If head.data == v, set head = head.next.
   • Otherwise move t from head while t.next != null and t.next.data != v. If t.next == null, print that v is not found; else set t.next = t.next.next. Only the first node holding v is deleted.
6. search(): read v, start with t = head and pos = 1. Move along the list, increasing pos, until the value is found or t becomes null. Print the position or a not-found message.
7. display(): if head == null print a message; otherwise print each t.data followed by -> from the head, then null.
8. countNodes(): walk from head to null adding 1 to c for every node and print c.
9. Choice 8 prints Program ended. and the loop stops.

Program

Node builds one node. In SinglyList, the insert methods change head or the last next, the delete methods bypass a node by changing one reference, and search, display and countNodes only walk the list. One Scanner is a data member shared by main and all methods, because two Scanners on the same input can lose typed data. main is in the class SinglyList, which is the public class.

import java.util.Scanner;

// A node of the list: holds one integer and a reference to the next node
class Node
{
    int data;     // the value stored in the node
    Node next;    // reference to the next node; null for the last node

    // Constructor: makes a node holding d that points to nothing
    Node(int d)
    {
        data = d;
        next = null;
    }
}

// The singly linked list: only the head (first node) is stored
public class SinglyList
{
    Node head;    // reference to the first node; null when the list is empty
    Scanner sc = new Scanner(System.in);   // the only Scanner of the program, shared by all methods

    // Default constructor: starts with an empty list
    SinglyList()
    {
        head = null;
    }

    // Reads a value and inserts a new node at the front of the list
    void insertFront()
    {
        System.out.print("Enter the value to insert: ");
        int v = sc.nextInt();
        Node p = new Node(v);
        p.next = head;       // new node points to the old first node
        head = p;            // new node becomes the first node
        System.out.println("Inserted " + v + " at the front.");
    }

    // Reads a value and inserts a new node at the end of the list
    void insertEnd()
    {
        System.out.print("Enter the value to insert: ");
        int v = sc.nextInt();
        Node p = new Node(v);
        if (head == null)
        {
            head = p;        // empty list: the new node is the only node
        }
        else
        {
            Node t = head;
            while (t.next != null)   // move t to the last node
            {
                t = t.next;
            }
            t.next = p;      // last node now points to the new node
        }
        System.out.println("Inserted " + v + " at the end.");
    }

    // Deletes the first node and prints its value; prints a message if the list is empty
    void deleteFront()
    {
        if (head == null)
        {
            System.out.println("The list is empty. Nothing to delete.");
        }
        else
        {
            int v = head.data;
            head = head.next;    // second node (or null) becomes the first node
            System.out.println("Deleted " + v + " from the front.");
        }
    }

    // Reads a value and deletes the first node holding it
    void deleteValue()
    {
        System.out.print("Enter the value to delete: ");
        int v = sc.nextInt();
        if (head == null)
        {
            System.out.println("The list is empty. Nothing to delete.");
        }
        else if (head.data == v)
        {
            head = head.next;        // the first node holds the value
            System.out.println("Deleted " + v + ".");
        }
        else
        {
            Node t = head;
            while (t.next != null && t.next.data != v)   // stop just before the node to delete
            {
                t = t.next;
            }
            if (t.next == null)
            {
                System.out.println(v + " not found in the list.");
            }
            else
            {
                t.next = t.next.next;    // bypass the node holding v
                System.out.println("Deleted " + v + ".");
            }
        }
    }

    // Reads a value and prints its position (first node is position 1) if found
    void search()
    {
        System.out.print("Enter the value to search: ");
        int v = sc.nextInt();
        Node t = head;
        int pos = 1;         // position of the node t
        boolean found = false;
        while (t != null && !found)
        {
            if (t.data == v)
            {
                found = true;
            }
            else
            {
                t = t.next;
                pos++;
            }
        }
        if (found)
        {
            System.out.println(v + " found at position " + pos + ".");
        }
        else
        {
            System.out.println(v + " not found in the list.");
        }
    }

    // Displays the list from the head, e.g. 10 -> 20 -> null
    void display()
    {
        if (head == null)
        {
            System.out.println("The list is empty.");
        }
        else
        {
            Node t = head;
            while (t != null)
            {
                System.out.print(t.data + " -> ");
                t = t.next;
            }
            System.out.println("null");
        }
    }

    // Counts the nodes by walking from the head and prints the count
    void countNodes()
    {
        int c = 0;
        Node t = head;
        while (t != null)
        {
            c++;
            t = t.next;
        }
        System.out.println("Number of nodes: " + c);
    }

    // main: creates the list and runs the menu until Exit is chosen
    public static void main(String[] args)
    {
        SinglyList obj = new SinglyList();
        int choice;
        do
        {
            System.out.println();
            System.out.println("1. Insert at front");
            System.out.println("2. Insert at end");
            System.out.println("3. Delete from front");
            System.out.println("4. Delete a value");
            System.out.println("5. Search a value");
            System.out.println("6. Display");
            System.out.println("7. Count nodes");
            System.out.println("8. Exit");
            System.out.print("Enter your choice: ");
            choice = obj.sc.nextInt();
            switch (choice)
            {
                case 1: obj.insertFront(); break;
                case 2: obj.insertEnd(); break;
                case 3: obj.deleteFront(); break;
                case 4: obj.deleteValue(); break;
                case 5: obj.search(); break;
                case 6: obj.display(); break;
                case 7: obj.countNodes(); break;
                case 8: System.out.println("Program ended."); break;
                default: System.out.println("Invalid choice. Enter 1 to 8.");
            }
        } while (choice != 8);
    }
}

Variable description table

Sample input and output

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 1
Enter the value to insert: 20
Inserted 20 at the front.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 1
Enter the value to insert: 10
Inserted 10 at the front.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 2
Enter the value to insert: 30
Inserted 30 at the end.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 6
10 -> 20 -> 30 -> null

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 7
Number of nodes: 3

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 5
Enter the value to search: 20
20 found at position 2.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
Deleted 10 from the front.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 6
20 -> 30 -> null

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 8
Program ended.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 6
The list is empty.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
The list is empty. Nothing to delete.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 7
Number of nodes: 0

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 4
Enter the value to delete: 10
The list is empty. Nothing to delete.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 5
Enter the value to search: 10
10 not found in the list.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 9
Invalid choice. Enter 1 to 8.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 8
Program ended.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 2
Enter the value to insert: 10
Inserted 10 at the end.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 2
Enter the value to insert: 20
Inserted 20 at the end.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 2
Enter the value to insert: 30
Inserted 30 at the end.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 4
Enter the value to delete: 20
Deleted 20.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 4
Enter the value to delete: 99
99 not found in the list.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 4
Enter the value to delete: 10
Deleted 10.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 4
Enter the value to delete: 30
Deleted 30.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 6
The list is empty.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
The list is empty. Nothing to delete.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 7
Number of nodes: 0

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 8
Program ended.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 2
Enter the value to insert: 5
Inserted 5 at the end.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 5
Enter the value to search: 7
7 not found in the list.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
Deleted 5 from the front.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
The list is empty. Nothing to delete.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 3
The list is empty. Nothing to delete.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 6
The list is empty.

1. Insert at front
2. Insert at end
3. Delete from front
4. Delete a value
5. Search a value
6. Display
7. Count nodes
8. Exit
Enter your choice: 8
Program ended.

Dry run

Take the first sample. Each row shows the list after the operation.

The final display is 20 -> 30 -> null, which matches the first sample run.

Variations

1. Insert at a position "Write a program to insert a node at a given position of a singly linked list."
2. Reverse the list "Write a program to reverse a singly linked list by changing the links."
3. Delete the last node "Write a method to delete the last node of a singly linked list."
4. Sorted insertion "Insert a value into a linked list so that the list stays in ascending order."