InsertNode

In LinkedList we can insert node in 3 ways.

  1. Insert first
  2. Insert after a specified node
  3. Insert at the end.

1. Inserting at the first

a. Create a method which receives data element as argument

b. Check is head element is null, if its then create object for the Node with passing data and assign it to head node.

c. If head is not null, then create object for the Node class with passing data.

d. Assign head to new node next value

e. Assign new node to head.

private static void insert(String data) {
    // check is head null or not
    if(head == null){
        // As head is null, so list is empty then create head node with given data
        head = new Node(data);
        return;
    }
    // head is not null so creating a object for the new node
    Node new_node = new Node(data);

    // assign head to new node address feild
    new_node.next = head;

    // move new node to head
    head = new_node;
}

2. Insert after a specified node:

a. Create a method which takes 2 arguments, one is previous nodeĀ  and other is data element.

b. Check previous node is null, if its null then print previous node can’t be null.

c. If previous node not null then create object for the Node class with passing data.

d. Assign previous node address field(current list next node address) new node address field.

e. Assign new node to previous node address field.

private static void insert(Node previous_node, String data) {
    if(previous_node == null){
        System.out.println("Previous node can't be null");
        return;
    }
    Node new_node = new Node(data);

    new_node.next = previous_node.next;

    previous_node.next = new_node;
}

3. Insert at the end

a. Create a method with argument data element.

b. Check is head is null, if it is then create object for Node class with data assign it to head.

c. if head is not null then create object for the Node class with data.

d. Assign new_node address field to null, because it will be last node so it should be null.

e. Create a reference for the Node and assign the head value to it.

f. Now traverse the loop till end and for the end node address field assign the new node.

private static void addAtEnd(String data) {
    if(head == null ){
        head = new Node(data);
        return;
    }
    Node new_node = new Node(data);
    new_node.next = null;

    Node last = head;
    while (last.next != null){
        last = last.next;
    }
    last.next = new_node;
}

Note: Here add node at the end takes O(n) time complexity because we are traversing the full list and adding the new node at the end.

Full program:

package com.gudla.linkedlist;

/**
 * Created by santhosh on 19/3/17.
 */
public class LinkedList {
    static Node head;

    static class Node{
        String data;
        Node next;
        Node(String string){
            data = string;
            next = null;
        }
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.head = new Node("Santhosh");
        Node first = new Node("Muni");
        Node second = new Node("Basha");

//        Assign address of first node to head and second node to first
        head.next = first;
        first.next = second;

        insert("Vamsi");
        insert(first, "Hareesh");
        addAtEnd("Santa");

        printData();
    }

    private static void addAtEnd(String data) {
        if(head == null ){
            head = new Node(data);
            return;
        }
        Node new_node = new Node(data);
        new_node.next = null;

        Node last = head;
        while (last.next != null){
            last = last.next;
        }
        last.next = new_node;
    }

    private static void insert(Node previous_node, String data) {
        if(previous_node == null){
            System.out.println("Previous node can't be null");
            return;
        }
        Node new_node = new Node(data);

        new_node.next = previous_node.next;

        previous_node.next = new_node;
    }

    private static void insert(String data) {
        // check is head null or not
        if(head == null){
            // As head is null, so list is empty then create head node with given data
            head = new Node(data);
            return;
        }
        // head is not null so creating a object for the new node
        Node new_node = new Node(data);

        // assign head to new node address feild
        new_node.next = head;

        // move new node to head
        head = new_node;
    }

    static void printData(){
        while (head != null){
            System.out.println(head.data);
            head = head.next;
        }
    }
}

Output:

Vamsi
Santhosh
Muni
Hareesh
Basha
Santa

Advertisements