Exercise_3.java

//T.C - O(1) for insertion at head and O(n) for insertion at the end. For traversal, O(n) as we iterate
// through all the nodes for printing, S.C - O(n)
// Your code here along with comments explaining your approach
/*
 * I initialize the constructor with the incoming parameter and insert new node by checking if head is null and making the
 * new node as head if null. If not, I safely append it by traversing till the end of the list. Similarly, I print
 * the data values of each node by traversing them.
 * */
import java.io.*;
  
// Java program to implement 
// a Singly Linked List 
class LinkedList {
  
    Node head; // head of list 
  
    // Linked list Node. 
    // This inner class is made static 
    // so that main() can access it 
    static class Node { 
  
        int data; 
        Node next; 
  
        // Constructor 
        Node(int d) 
        { 
            //Write your code here
            this.data = d;
            this.next = null;
        } 
    } 
  
    // Method to insert a new node 
    public static LinkedList insert(LinkedList list, int data) 
    { 
        // Create a new node with given data
        Node newNode = new Node(data);
   
        // If the Linked List is empty, 
        // then make the new node as head
        if(list.head == null)
            list.head = newNode;

        
            // Else traverse till the last node 
            // and insert the new_node there
        else {
            Node temp = list.head;
            while(temp.next != null)
                temp = temp.next;
            temp.next = newNode;
        }

            // Insert the new_node at last node 
        // Return the list by head
        return list;
    } 
  
    // Method to print the LinkedList. 
    public static void printList(LinkedList list) 
    {  
        // Traverse through the LinkedList 
   
            // Print the data at current node 
       
            // Go to next node
        Node temp = list.head;
        while(temp != null) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    } 
   
    // Driver code 
    public static void main(String[] args) 
    { 
        /* Start with the empty list. */
        LinkedList list = new LinkedList(); 
  
        // 
        // ******INSERTION****** 
        // 
  
        // Insert the values 
        list = insert(list, 1); 
        list = insert(list, 2); 
        list = insert(list, 3); 
        list = insert(list, 4); 
        list = insert(list, 5); 
  
        // Print the LinkedList 
        printList(list); 
    } 
}