Inserting a new node in a linked list data structure

Inserting new node in linked list can do 3 ways.

1. At the start of the Linked list
2. In the middle of the Linked list
3. At the end of the Linked list

Before starting you have to must know about Linked list and how to create it.

1.  At Start of Linked list

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    // method to add new node in start
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> "+node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(4);
        linkedList.push(3);
        linkedList.push(2);
        linkedList.printAllNodes();
    }
}

2.  In the Middle of Linked list

Insert a new node with data at the middle of the list and given a linked list containing n nodes..

So now condition is :

• If n is even, then insert the new node after the (n/2)th node,
• else insert the new node after the (n+1)/2th node.

Must read this tutorial to Find Length of a Linked List data for better understanding.

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;

        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void addMiddleNode(int n) {

        if (head == null) {
            head = new Node(n);
        } else {
            int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);

            //create new node
            Node newNode = new Node(n);
            Node pointerNode = head;
            int countNodes = 0;
            while (countNodes != middleNode -1) {
                pointerNode = pointerNode.next;
                countNodes ++;
            }
            System.out.println("\n Middle node of linked List " + middleNode);
            System.out.println("\n Middle node data " + pointerNode.data);

            // adding new node in middle
            newNode.next = pointerNode.next;
            pointerNode.next = newNode;
            printAllNodes();
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {

        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.printAllNodes();
        linkedList.addMiddleNode(3);
    }
}

3. Add node in linked list Last

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void append(int n) {
        // create new node
        Node newNode = new Node(n);
        // if head is null add new head
        if (head == null) {
            head = new Node(n);
            return;
        }
        //traverse till the last node
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        //Add the new node of last node
        last.next = newNode;
        return;
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> "+node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.append(1);
        linkedList.append(4);
        linkedList.append(3);
        linkedList.append(2);
        linkedList.printAllNodes();
    }
}