Object class

Object class is present in the java.lang package. It is the super class for all the classes directly or indirectly. If a class is not extended any class then for the class Object class is super class. If a class extends an other class then for this class Object class is indirect super class.

Object class has 12 methods which given below.

1. private static native void registerNatives(): It is a private method so we no need to consider it. It is implemented in the other language(C/C++).
2. public final native Class<?> getClass(): It is a native method and implementation in other language(C/C++). Which is used for the getting the class level information. It also provides the meta data of a class. It is a final class and it can’t be overridden.Example:
3. public native int hashCode(): It is a native method. For every object JVM generates a unique number which is different for different objects. This distinct number is generated by the hashcode. hashCode method returns the unsigned hex decimal integer. This number is formed by hashing the internal address of the object by using an algorithm. The main advantage of hashing is searching becomes easy. This method can be overridden, when it overridden we have to make sure that each object will have different hashcode.
4. public boolean equals(Object obj): It is used for compare a object with ‘this’ object. By default implementation in Object class of this method is compare the given object reference with ‘this’ object reference (Not contents of the object).  It is recommended that whenever this method is overridden then override hashcode method for make sure same content objects has same hash code.
5. protected native Object clone(): It is used for the make a copy of the object. If we want to make a copy of an object with using this method then class must implemented with Cloneable interface(Marker Interface) otherwise will get a CloneNotSupportedException.  By using clone method we can do 2 types of object copies. 1. Shallow cloning ( When we use it, it can copy only instance variables but not reference variables. i.e if we try to modify using this reference variables from copied object then actual object of that reference will be modified). 2. Deep cloning (When we use it, it can copy instance variables and also reference variable. i.e if we modify the data with reference variable from the copied object then it won’t modify the actual object.)
6. public String toString(): It is used for converting the object to String. By default implementation of this method in Object class is to convert the object reference to String. i.e class name + @+ hex integer. Not actual value of object. It is recommended to override to get the content of object to convert String.
7. public final void wait(): It is used in the multi-threaded programming. It keeps the current thread in sleep and release the lock until another thread enters the same monitor and calls notify.
   
8. public final void wait(long timeout): It keeps the current thread in sleep for specified time and release the lock on it. Here time is milliseconds.
   
9. public final void wait(long timout, int nanos): It keeps the current thread in sleep for specified milliseconds and nanoseconds and releases the lock on it.
10. public final native void notify(): It wakes up(notify) one thread which is called wait on same object. notify method just wakes up the thread but not release the lock until its execution finished.
    
11. public final native void notifyAll():It wakes up all threads which are called wait on same object. It also doesn’t release the lock until execution is finished.
    

Note: Above 5 methods (from 7 to 11) used in synchronized block only.

12.protected void finalize(): This method is called just before an object is garbage collected. It is called by the Garbage Collector on an object when garbage collector determines that there are no more references to the object. This method we need to override whenever we need to clean up the resources used in the object and also to avoid the memory leaks.

JVM

JVM(Java Virtual Machine): JVM is a part of JRE(Java Runtime Enviroment). Jvm is responsible for call the main method present in java code.

Image Source: Wikipedia.

When we compile .java file it will generate .class(Byte code) with same name. When we run it it will go to several steps, these steps together describes JVM.

Class Loader: Class loader loads the class information in the method area. Class loader responsibilities are below.

1. Loading
2. Linking
3. Initialization

Loading: Class loader reads the .class file and generates the binary data then save it in the method area. It loads the following information in the method area for every .class file.

-> Fully qualified class name and its immediate super class name.

-> Whether .class file related to Class or Interface or Enum.

-> Modifiers, variables and method information etc.

After loading .class file JVM creates the object for the Class which is from java.lang package. This Class object represents the class loaded .class file. Using this object we can get the class level information of the loaded class. We can get Class object from the getClass method of Object class.

Linking: It performs verification, preparation and resolution.

-> It verifies the correctness of the .class file. i.e it checks the file format is proper or not and also is it compiled with proper compiler or not. If verification fails then we will get java.lang.VerifyError runtime exception.

-> It allocates the memory for the instance variables and assign them with their default values.

Initialization: In this phase all the static variables assigned with its values and static blocks if any from the top to button and from the parent class to child class.

Basic class loader are below.

1. Bootstrap class loader: It is capable of loading trusted classes. It loads core java api classes which are present in the jre/lib directory. This directory popularly know as bootstrap path. Every JVM must implement bootstrap class loader. It is implemented in native languages like C/C++.
2. Extension class loader: It is a child class loader of bootstrap class. It is responsible for loading the classes which is present in the jre/lib/ext directory or java.ext.dirs property set path. It is implemented by the sun.misc.Launcher$ExtClassLoader class.
3. Application/System class loader: It is a child class loader of extension class loader which is responsible for load the class present in the application path. It is internally uses the class path(java.class.path). It is implemented by the sun.misc.Launcher$ExtClassLoader class.

JVM follow Delegation-Hierarchy principle to load classes.

Image Source: http://javarevisited.blogspot.in/2012/12/how-classloader-works-in-java.html

JVM Memory:

Method Area: In method area classes information will be stored like class name, immediate super class name, variables(including static variables) and method informations. Only one method area per JVM and it is shared memory.

Heap Memory: Information of all the objects will be present here. Only one heap area per JVM and it is shared memory.

Stack Memory: For every thread JVM creates a stack memory, here local variables of the method will be stored and when thread is terminated the corresponding stack memory will be cleared by the JVM. It is not a shared memory.

PC Registers: Each thread as its own pc registers and it holds the address of current execution of a thread.

Native Method Stack: It stores the native methods information. Every thread has its own native method stack.

Execution Engine: It reads the .class file(byte code) line by line and use the data or information present in different memory areas then executes the instructions.

Execution engine consists of 3 parts.

1. Interpreter: It interprets the byte code line by line then executes. It needs more time when we call method multiple time for interpretation.
2. Just In Time(JIT) compiler: It compiles the byte code and converts it into native code, so whenever interpreter requires multiple class then JIT provides native code to the interpreter so re-interpretation is not required. Because of it efficiency of interpreter will be improved.
3. Garbage Collector: It is used for the clear the memory of object which are no longer used and their reference is referred to null.

Java Native Interface(JNI): It is a interface which interacts with the Native method libraries and it provides this libraries for execution.

Native Method Libraries: These are native libraries developed in C/C++ which are required for the execution engine.

String reverse with recursion

Steps:

1. Create a method which receives String as argument and return String.
2. Check is string is null or string length is less or equal to 1 then return the current string only.
3. If string length is more then 1 then again call string reverse method with substring(1) and append it with charAt(0). So first character of each call will be appended from right to left.

Example: “abc” is string then

substring of 1 is bc + ‘a’.

substring of 1 is c+’b’+’a’

Example:

package com.gudla.randomprograms;

/**
 * Created by santhosh on 28/3/17.
 */
public class StringReverse {

    public static void main(String[] args) {
        System.out.println(reverse("android"));

    }

    private static String reverse(String s){
        if(s == null || s.length() <= 1 ) {
            return s;
        } else {
            return reverse(s.substring(1))+s.charAt(0);
        }
    }
}

Output:

diordna

Swap 2 Numbers

We can swap 2 numbers in different ways.

1. Using a temp variable.
2. Without using temp variable
3. Using Logical operators
4. In Single line

Example:

package com.gudla.swapnumbers;

/**
 * Created by santhosh on 26/3/17.
 */
public class SwapNumbers {

    public static void main(String[] args) {
        withTemp(10, 20);
        System.out.println("\n"+"\n");
        withoutTempSimple(10, 20);
        System.out.println("\n"+"\n");
        withLogical(10, 20);
        System.out.println("\n"+"\n");
        inSingle(10, 20);
    }

    private static void inSingle(int a, int b) {
        System.out.println("Before a value is : "+a);
        System.out.println("Before b value is : "+b);
        System.out.println("\n");
        b=(a+b)-(a=b);

        System.out.println("After a value is : "+a);
        System.out.println("After b value is : "+b);

    }

    private static void withLogical(int a, int b) {
        System.out.println("Before a value is : "+a);
        System.out.println("Before b value is : "+b);
        System.out.println("\n");
        a = a^b;
        b = a^b;
        a = a^b;
        System.out.println("After a value is : "+a);
        System.out.println("After b value is : "+b);
    }

    private static void withoutTempSimple(int a, int b) {
        System.out.println("Before a value is : "+a);
        System.out.println("Before b value is : "+b);
        System.out.println("\n");
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println("After a value is : "+a);
        System.out.println("After b value is : "+b);
    }

    private static void withTemp(int a, int b) {
        System.out.println("Before a value is : "+a);
        System.out.println("Before b value is : "+b);
        System.out.println("\n");
        int c = a;
        a = b;
        b = c;

        System.out.println("After a value is : "+a);
        System.out.println("After b value is : "+b);
    }
}

Output:

Before a value is : 10
Before b value is : 20

After a value is : 20
After b value is : 10

Before a value is : 10
Before b value is : 20

After a value is : 20
After b value is : 10

Before a value is : 10
Before b value is : 20

After a value is : 20
After b value is : 10

Before a value is : 10
Before b value is : 20

After a value is : 20
After b value is : 10

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

 

Exception

Exception:

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