ISC Practicals and Theory - Singly Linked List (OOP)

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 version is written in the object-oriented style: the methods take the value as a parameter and return results (a boolean, a position, a count or the deleted value), and main reads the input and prints the messages.

Definition

A single linked list is made of nodes. Each node has 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 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

Return values used here:

• deleteValue(v) returns true if a node was deleted and false if the list is empty or v is not found.
• search(v) returns the position (the first node is position 1), or 0 if v is not in the list.
• deleteFront() returns the deleted value, or -1 if the list is empty. As -1 can also be stored in a node, main calls isEmpty() first.

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 act on it. Any other number prints Invalid choice. Enter 1 to 8.
2. Choice 1: read v, call insertFront(v).
   • Create p = new Node(v), set p.next = head, then head = p.
3. Choice 2: read v, call insertEnd(v).
   • Create p. If head == null, set head = p.
   • Otherwise start with t = head, move t = t.next while t.next != null, then set t.next = p.
4. Choice 3: if isEmpty() print a message; otherwise deleteFront() saves head.data, sets head = head.next and returns the value.
5. Choice 4: read v. If the list is empty print a message. Otherwise call deleteValue(v):
   • If head.data == v, set head = head.next and return true.
   • Otherwise move t from head while t.next != null and t.next.data != v. If t.next == null return false; else set t.next = t.next.next and return true. Only the first node holding v is deleted.
   • main prints the deleted message for true and the not-found message for false.
6. Choice 5: read v and call search(v): start with t = head and pos = 1, return pos when t.data == v, otherwise move on and increase pos; return 0 when t becomes null.
7. Choice 6: display() prints each t.data followed by ->, then null, or a message if the list is empty.
8. Choice 7: countNodes() walks from head to null, adds 1 to c per node and returns c.
9. Choice 8 prints Program ended. and the loop stops.

Program

Node builds one node. In SinglyList, isEmpty, search and countNodes return information, the insert and delete methods change the links, and main holds the one Scanner and prints all messages except the list display. 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

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

    // Returns true if the list has no node
    boolean isEmpty()
    {
        return head == null;
    }

    // Inserts a new node holding v at the front of the list
    void insertFront(int v)
    {
        Node p = new Node(v);
        p.next = head;       // new node points to the old first node
        head = p;            // new node becomes the first node
    }

    // Inserts a new node holding v at the end of the list
    void insertEnd(int v)
    {
        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
        }
    }

    // Deletes the first node and returns its value.
    // Returns -1 if the list is empty (the caller checks isEmpty() first, as -1 can also be a stored value)
    int deleteFront()
    {
        if (head == null)
        {
            return -1;
        }
        int v = head.data;
        head = head.next;    // second node (or null) becomes the first node
        return v;
    }

    // Deletes the first node holding v.
    // Returns true if a node was deleted, false if the list is empty or v is not found
    boolean deleteValue(int v)
    {
        if (head == null)
        {
            return false;
        }
        if (head.data == v)
        {
            head = head.next;        // the first node holds the value
            return true;
        }
        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)
        {
            return false;
        }
        t.next = t.next.next;        // bypass the node holding v
        return true;
    }

    // Returns the position of v (first node is position 1), or 0 if v is not in the list
    int search(int v)
    {
        Node t = head;
        int pos = 1;         // position of the node t
        while (t != null)
        {
            if (t.data == v)
            {
                return pos;
            }
            t = t.next;
            pos++;
        }
        return 0;
    }

    // Returns the number of nodes by walking from the head
    int countNodes()
    {
        int c = 0;
        Node t = head;
        while (t != null)
        {
            c++;
            t = t.next;
        }
        return c;
    }

    // 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");
        }
    }

    // main: creates the list and runs the menu until Exit is chosen
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // the only Scanner of the program
        SinglyList obj = new SinglyList();
        int choice, v, pos;
        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 = sc.nextInt();
            switch (choice)
            {
                case 1:
                    System.out.print("Enter the value to insert: ");
                    v = sc.nextInt();
                    obj.insertFront(v);
                    System.out.println("Inserted " + v + " at the front.");
                    break;
                case 2:
                    System.out.print("Enter the value to insert: ");
                    v = sc.nextInt();
                    obj.insertEnd(v);
                    System.out.println("Inserted " + v + " at the end.");
                    break;
                case 3:
                    if (obj.isEmpty())
                    {
                        System.out.println("The list is empty. Nothing to delete.");
                    }
                    else
                    {
                        System.out.println("Deleted " + obj.deleteFront() + " from the front.");
                    }
                    break;
                case 4:
                    System.out.print("Enter the value to delete: ");
                    v = sc.nextInt();
                    if (obj.isEmpty())
                    {
                        System.out.println("The list is empty. Nothing to delete.");
                    }
                    else if (obj.deleteValue(v))
                    {
                        System.out.println("Deleted " + v + ".");
                    }
                    else
                    {
                        System.out.println(v + " not found in the list.");
                    }
                    break;
                case 5:
                    System.out.print("Enter the value to search: ");
                    v = sc.nextInt();
                    pos = obj.search(v);
                    if (pos == 0)
                    {
                        System.out.println(v + " not found in the list.");
                    }
                    else
                    {
                        System.out.println(v + " found at position " + pos + ".");
                    }
                    break;
                case 6:
                    obj.display();
                    break;
                case 7:
                    System.out.println("Number of nodes: " + 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."