Question

urgent !! ASAP PLEASE

DATA STRUCTURES

To class SinglyLinkedList, add method afterThird(E e) which receives an element e and insert that in a new node after the third node in the list (assume the first node in the list is number 1). You should ensure that the linked list has at least three nodes, otherwise throw an exception. You should consider all possible cases.

Answer 1

If you want the method to addatThird Plzz refer to method "insertAfterThird" in the below code:

public class LinkedList {
    private Node head; // head of list

    // Linked list Node.
    //  inner class is made to be static so that main() can access it
    static class Node {

        int data;
        Node next;

        // Constructor to add data in the list
        Node(int d) {
            data = d;
            next = null;
        }
    }

    public static LinkedList insert(LinkedList list, int data) {
        // Create a new node with given data
        Node new_node = new Node(data);
        new_node.next = null;

        // If the Linked List is empty, then make the new node as head
        if (list.head == null) {
            list.head = new_node;
        } else {
            // Else traverse till the last node and insert the new_node there
            Node last = list.head;
            while (last.next != null) {
                last = last.next;
            }

            // Insert the new_node at last node
            last.next = new_node;
        }

        // Return the list by head
        return list;
    }


    // Method to print the LinkedList.
    public static void printList(LinkedList list) {
        Node currNode = list.head;

        System.out.print("LinkedList: ");

        // Traverse through the LinkedList
        while (currNode != null) {
            // Print the data at current node
            System.out.print(currNode.data + " ");

            // Go to next node
            currNode = currNode.next;
        }
        System.out.print("\n\n");
    }


    /**********************************************************
     * PROBLEM SOLUTION
     *Here is the solution to add at Third
     */


    //Method to find the length of linked list
    public static int getLength(LinkedList list) {

        //if list is null return 0
        if (list == null) return 0;

        //count variable to get count
        int count = 0;

        Node node = list.head;

        //traverse linked list until reach to end
        while (node != null) {
            count++;
            node = node.next;
        }

        //return length count
        return count;
    }


    public static void insertAfterThird(LinkedList list, int data) throws Exception {
        int lengthOfLinkedList = getLength(list);

        //if length is less than 3 throw exception 
        if (lengthOfLinkedList < 3) {
            throw new Exception("Linked List length is less than 3");
        }

        //generate new Node
        Node newNode = new Node(data);
        
        Node node = list.head;

        int count = 0;

        //traverse linked list and maintain count 
        while (node != null) {
            
            count++;
            
            // if count is equal to 3 insert the new node to it
            if (count == 3) {
                newNode.next = node.next;
                node.next = newNode;
            }
            node = node.next;
        }


    }

    /*******************************************************/

    public static void main(String[] args) {


        /* Start with the empty list. */
        LinkedList list = new LinkedList();
        /*Insertion to make Linked List of length 3*/
        list = insert(list, 1);
        list = insert(list, 2);
        list = insert(list, 3);


        System.out.print("Initial linked List:");
        printList(list);


        try {
            System.out.println("\nInsert '4' after third:");
            insertAfterThird(list, 4);
            System.out.println("Output:");
            printList(list);

            System.out.println("Insert '5' after third:");
            insertAfterThird(list, 5);
            System.out.println("Output:");
            printList(list);

            System.out.println("Insert '6' after third:");
            insertAfterThird(list, 6);
            System.out.println("Output:");
            printList(list);
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }

    }
}

Output 1: insert when linked list has more than 3 element

output 2: when linked list has less than 3 element.

list = insert(list, 3); comment this line in main method to get this output