Search Element

Search a element in the linked list.

1. Just check did list contains the element or not, if contains return true else return false.
2. Search element and if found then return the position of it.
3. Search element if found then return node object of it.

Implementation of above requirements.

-> Search a element if found return true else return false

a. Create a method which receives a  search element as argument and returns boolean.

b. First check is list empty.

c. If list it not empty then create a copy of head and loop the it till data find.

private static boolean isContain(String data) {
    if(head == null ){
        return false;
    }
    Node temp = head;
    while (temp != null){
        if (temp.data.equals(data) )
        return true;

        temp = temp.next;
    }
    return false;
}

-> Search element if found then return position.

a. Create a method which takes search element as argument and returns integer as a position.

b. Check is list empty, if empty then return -1.

c. Check head is given element if yes then return 0. If not then create a copy of head node.

d. Create a counter and set it to 0. traverse the list and increment the counter. Add a condition to check the element. if found then return the counter.

private static int searchElement(String data) {
    if(head == null ){
        return -1;
    }
    if(head.data.equals(data))
        return 0;
    Node temp = head;
    int counter = 0;
    while (temp != null ){
        if(temp.data.equals(data))
            return counter;
        counter++;
        temp = temp.next;
    }
    return -1;
}

-> Search a element if found then return the Node object of it.

a. Create a method which receive the search element as argument and return type is Node.

b. Check list is empty. if empty then return null.

c. Check is head same as given element then return head.

d. if above 2 are not satisfied then create a copy of head. now traverse the list till find if found then return the node.

private static Node searchNode(String data) {
    if(head == null ) {
        return null;
    }
    Node temp = head;
    while (temp != null ){
        if(temp.data.equals(data))
        return temp;
        temp = temp.next;
    }
    return null;
}

 

Size of LinkedList

Linkedlist size we can implement by increasing the counter with traverse the loop.

We can get the size of linkedlist in 2 ways.

1. Iterative
2. Recursive

Iterative:

1. Create a method name size which returns integer as linkedlist size.
2. Create counter variable and set it to 0 (zero).
3. Loop the list until last node is null.
4. return the counter.

private static int size() {
    int counter = 0;
    Node temp = head;
    while (temp != null){
        counter++;
        temp = temp.next;
    }
    return counter;
}

Recursive:

1. Create a method name size which returns integer as linkedlist size
2. Create a method which receives head as argument and returns integer
3. call 2nd method from the first method and return the integer value.

private static int getSize() {

    return getCount(head);
}

private static int getCount(Node head) {
    if(head == null){
        return 0;
    }
    return 1+getCount(head.next);
}

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();
        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");

        delete("Hareesh");
        deleteAtPosition(2);

        System.out.println(size());
        System.out.println(getSize());

        printData();


    }

    private static int getSize() {

        return getCount(head);
    }

    private static int getCount(Node head) {
        if(head == null){
            return 0;
        }
        return 1+getCount(head.next);
    }

    private static int size() {
        int counter = 0;
        Node temp = head;
        while (temp != null){
            counter++;
            temp = temp.next;
        }
        return counter;
    }


    private static void deleteAtPosition(int position) {
        if(head == null){
            System.out.println("List is empty");
            return;
        }
        if(position == 0){
            head = head.next;
            return;
        }
        Node temp = head;
        for(int i = 0; temp != null && i < position-1; i++){
            temp = temp.next;
        }
        if(temp == null || temp.next == null){
            System.out.println("Given position is exceeded with list position");
            return;
        }
        temp.next = temp.next.next;
    }

    private static void delete(String data) {
        if(head != null && head.data == data){
            head = head.next;
            return;
        }
        Node temp, previous = null;
        temp = head;
        while( temp != null && temp.data != data){
            previous = temp;
            temp = temp.next;
        }
        if(temp == null){
            System.out.println("Given data is not found in the list");
            return;
        }
        previous.next = temp.next;
    }

    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;
        }
    }
}

DeleteNode

Delete node from the linkedlist based on the given data (First occurrence data node).

1. Create a method which receives data element as a argument.
2. Check  is head node itself contains this data. if it is then change the head to next node of given data.
3. if head doesn’t contain data then create a temp Node variable then assign head value to it and also create previous Node variable.
4. traverse the loop till data contained node found and same time keep track of previous node.
5. assign previous node next value to data node next value by skipping data node.

private static void delete(String data) {
    if(head != null && head.data == data){
        head = head.next;
        return;
    }
    Node temp, previous = null;
    temp = head;
    while( temp != null && temp.data != data){
        previous = temp;
        temp = temp.next;
    }
    if(temp == null){
        System.out.println("Given data is not found in the list");
        return;
    }
    previous.next = temp.next;
}

Deleting node from the linkedlist with a given position.

1. Check is list empty. if empty then print list is empty.
2. Check given position is zero then assign head node to next node.
3. If above 2 conditions not satisfied then we need to find a previous node of given position first for the first create a temp Node and assign it to head.
4. traverse the loop till position-1 for find previous node.
5. check previous node is null or previous node next is null, if any of one is null then position is exceeded than the list.
6. If above condition fails then Assign next of next to temp next which points to position+1.

private static void deleteAtPosition(int position) {
    if(head == null){
        System.out.println("List is empty");
        return;
    }
    if(position == 0){
        head = head.next;
        return;
    }
    Node temp = head;
    for(int i = 0; temp != null && i < position-1; i++){
        temp = temp.next;
    }
    if(temp == null || temp.next == null){
        System.out.println("Given position is exceeded with list position");
        return;
    }
    temp.next = temp.next.next;
}

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");

        delete("Hareesh");
        deleteAtPosition(4);

        printData();
    }

    private static void deleteAtPosition(int position) {
        if(head == null){
            System.out.println("List is empty");
            return;
        }
        if(position == 0){
            head = head.next;
            return;
        }
        Node temp = head;
        for(int i = 0; temp != null && i < position-1; i++){
            temp = temp.next;
        }
        if(temp == null || temp.next == null){
            System.out.println("Given position is exceeded with list position");
            return;
        }
        temp.next = temp.next.next;
    }

    private static void delete(String data) {
        if(head != null && head.data == data){
            head = head.next;
            return;
        }
        Node temp, previous = null;
        temp = head;
        while( temp != null && temp.data != data){
            previous = temp;
            temp = temp.next;
        }
        if(temp == null){
            System.out.println("Given data is not found in the list");
            return;
        }
        previous.next = temp.next;
    }

    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
Basha

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

LinkedList

LinkedList is a linear data structure and in which elements are not stored in continuous location.

Image source Wikipedia

In simple Linkedlist each elements will contain 2 memory locations one is for data element and other is for address of next element.

Advantages of Linkedlist over arrays :

1. Arrays are fixed in size and we have to specify the max memory when we declare an array whereas Linkedlist is dynamic.
2. In Arrays insertion and deletions are takes more time. Because if we add element in array in the first or middle all other elements need to move and same in deletion also whereas in linkedlist it takes less time because when insert element in the middle address of element will be added to previous element and next element address will be added to current element.

Deleting an element.

Adding an element

Disadvantages:

1. As each node required 2 memory location, it needs more memory.
2. In linkedlist random access is not possible. So retrieving/accessing an element needs traversal of list from first until the element found.

Time Complexity:

Accessing an element : O(1) if the element in the first location.

O(n) if the element in the last location.

Insertion and deletion: O(1).

Simple LinkedList program with Java:

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;

        printData();
    }

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