Linked List: Program to insert a node into a linked list

Write a program to insert a node in a linked list.

Linked list is a series of nodes in which each node contains a data field and
reference (pointer) to the next node in the list.

There are two cases in inserting node into linked list

1. Inserting a new node at the start of the linked list

   • For inserting nodes at the start we have to simply refer to the following steps
   • Modify the next pointer of the new node as head node
   • Set the newly inserted node as head node.



2. Inserting new node at end of linked list

   • For inserting nodes at the start we have to simply refer to the following steps
   • Set current node on head node
   • Traverse linked list till next pointer of current is not NULL
   • Modify the next pointer of the current node as a new node
   • Make the next pointer of the new node as NULL

Complexity

Time Complexity : O(n) , where n is the size of linked list
Space Complexity : O(1)

Java Code

   import java.util.*;

    class Node {
        // initialising data field and next pointer of node
        int data;
        Node next;
     
        Node(int d) {
            this.data = d;
            this.next = null;
        }
    }
     
    class LinkedList{
        Node head;
     
        public
        // creating a linked list using array
        void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
     
        }
     
        // insertion of node at start in linked list
        public void insertAtStart(int new_data) {
            Node temp = new Node(new_data);
            temp.next = head;
            head = temp;
        }
     
        // insertion of node at end in linked list
        public void insertAtEnd(int new_data) {
            Node temp = new Node(new_data);
            if (head == null) {
                head = temp;
                return;
            }
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = temp;
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 10, 30, 50, 40 };
            // initialising object of linkedlist class
            int numberOfNodes = 4;
            LinkedList ll = new LinkedList();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            System.out.println("Inserting node 20 at start ");
            ll.insertAtStart(20);
            ll.printLinkedlist();
            System.out.println("Inserting node 90 at end ");
            ll.insertAtEnd(90);
            ll.printLinkedlist();
        }
    }

Output

Given Linked List
10 -> 30 -> 50 -> 40
Inserting node 20 at start
20 -> 10 -> 30 -> 50 -> 40
Inserting node 90 at end
20 -> 10 -> 30 -> 50 -> 40 -> 90