Linked List Implementation In Java

Linked list

In computer science, a linked list is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of a data and a reference (in other words, a link) to the next node in the sequence; more complex variants add additional links. This structure allows for efficient insertion or removal of elements from any position in the sequence.

Linked List Implementation In Java 

1. Insert at The end of the list

2. get size of list

3. print content of list

4.add element at the end

5. add element at specified position

6. remove element at index

Output

----------Size of list---------------

4

----------Content of list----------------

[ 1 ][ 2 ][ 3 ][ 4 ]

----------get element of list-----------------

2

----------remove element from list-----------

true

----------Content of list----------------

[ 1 ][ 3 ][ 4 ]

---add new element to specified position----

----------Content of list----------------

[ 1 ][ M ][ 3 ][ 4 ]

CODE 

/**
 * 1. Insert at The end of the list. 2. get size of list 3. print content of
 * list 4.add element at the end 5. add element at specified position 6. remove
 * element at index
 *
 * Note: The link object doesn't contain the another link object Next Link is
 * actually a reference to another link
 *
 * @author RaviKantSoni[12-August-2013]
 *
 */
public class testSingleLinkedList {

    public static void main(String[] args) {
        SingleLinkedList linkedList = new SingleLinkedList();
        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.add("4");

        System.out.println("----------Size of list---------------");
        System.out.println(linkedList.size());
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());
        System.out.println("----------get element of list-----------------");
        System.out.println(linkedList.get(2));
        System.out.println("----------remove element from list-----------");
        System.out.println(linkedList.remove(2));
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());
        System.out.println("---add new element to specified position----");
        linkedList.add("M", 2);
        System.out.println("----------Content of list----------------");
        System.out.println(linkedList.toString());

    }
}

class SingleLinkedList {
    // reference to Head Node
    private Node head;
    private int listCount;

    // LinkedList Constructor
    public SingleLinkedList() {
        // this is empty list so the reference to the head node is set to a new
        // node with no data
        head = new Node(null);
        listCount = 0;
    }

    // add new element to the end of the list
    public void add(String data) {
        Node temp = new Node(data);
        Node current = head;
        // starting at the head node, crawl to the end of the list
        while (current.getNext() != null) {
            current = current.getNext();
        }
        // the last node's next reference set to new node
        current.setNext(temp);
        listCount++;
    }

    // to print content of list
    public String toString() {
        Node current = head.getNext();
        String outPut = "";
        while (current != null) {
            outPut = outPut + "[ " + current.getData() + " ]";
            current = current.getNext();
        }
        return outPut;
    }

    // to get size of the list
    public int size() {
        return listCount;
    }

    // returns the element at the specified position in this list
    // here we are returning object from the list
    public Object get(int index) {
        // index should be 1 or more
        if (index <= 0) {
            return null;
        }
        Node element = head.getNext();
        for (int i = 1; i < index; i++) {
            if (element.getNext() == null)
                return null;

            element = element.getNext();
        }
        return element.getData();
    }

    // remove the element at specific position in the list\
    public boolean remove(int index) {
        // if index is out of range, exist
        if (index < 1 || index > size())
            return false;
        Node current = head;
        for (int i = 1; i < index; i++) {
            if (current.getNext() == null)
                return false;
            current = current.getNext();
        }
        current.setNext(current.getNext().getNext());
        listCount--;
        return true;
    }

    // insert specified element at specified position in the list
    public void add(String data, int index) {
        // insert to requested index or to last in this list, which ever come
        // first
        Node current = head;
        Node temp = new Node(data);
        for (int i = 1; i < index && current.getNext() != null; i++) {
            current = current.getNext();
        }
        temp.setNext(current.getNext());
        current.setNext(temp);
        listCount++;
    }

    static class Node {
        private Node next;
        private String data;

        Node(String data) {
            this.data = data;
        }

        public String toString() {
            return this.data;
        }

        public Node(String data, Node node) {
            this.data = data;
            this.next = node;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }

        public String getData() {
            return data;
        }

        public void setData(String data) {
            this.data = data;
        }

    }
}

Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Diameter of a Tree is the number of nodes on the longest path between two leaves in the tree

Consider a particular "node":- we have three cases
1. Longest Possible path includes node->left and not this node
2. Longest Possible path includes node->right and not his node
3. Longest Possible path includes this "node"

Thus, longest possible path should be maximum of these three: (node->left, node->right, 1+height(node->left) + height(node->right))

OutPut

H
D
B
A
H
D
B
diamater7

Java Code

import java.util.ArrayList;
import java.util.List;

public class longestPathInTree {
    // node class
    class node {
        node right;
        String val;
        node left;

        public String getVal() {
            return val;
        }

        public void setVal(String val) {
            this.val = val;
        }

        public node getRight() {
            return right;
        }

        public void setRight(node right) {
            this.right = right;
        }

        public node getLeft() {
            return left;
        }

        public void setLeft(node left) {
            this.left = left;
        }

        public node(String val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        longestPathInTree path = new longestPathInTree();
        path.find();
    }

    public void find() {
        node root = new node("A");
        node b = new node("B");
        node c = new node("C");
        node d = new node("D");
        node e = new node("E");
        node f = new node("F");
        node g = new node("G");
        node h = new node("H");
        node i = new node("I");
        node j = new node("J");
        node k = new node("K");
        node l = new node("L");
        node m = new node("M");
        node n = new node("N");
        root.setLeft(b);
        root.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);
        c.setRight(g);
        d.setLeft(h);
        d.setRight(i);
        e.setLeft(j);
        e.setRight(k);
        f.setRight(l);
        f.setLeft(m);
        g.setLeft(n);

        int diameter = 0;
        List<node> leftPath = findLongestPath(root.getLeft());
        diameter = diameter + leftPath.size();
        for (int z = leftPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println(root.getVal());
        List<node> rightPath = findLongestPath(root.getRight());
        diameter += rightPath.size();
        for (int z = rightPath.size() - 1; z >= 0; z--) {
            System.out.println(leftPath.get(z).getVal());
        }
        System.out.println("diamater: " + ++diameter);

    }

    /**
     * if node does not have child node, then it will be child node else move
     * inside
     *
     * @param n
     * @return
     */
    private List<node> findLongestPath(node n) {
        List<node> stacks = new ArrayList<node>();
        node left = n.getLeft();
        node right = n.getRight();
        stacks.add(n);
        if (left == null && right == null) {
            return stacks;
        } else {
            List<node> sl = new ArrayList<longestPathInTree.node>();
            List<node> sr = new ArrayList<longestPathInTree.node>();
            if (left != null) {
                // Find longest path to left of node.
                sl = findLongestPath(left);
            }
            if (right != null) {
                // Find longest path to right of node.
                sr = findLongestPath(right);
            }
            if (sl.size() >= sr.size()) {
                for (node e : sl) {
                    stacks.add(e);
                }
            } else {
                for (node e : sr) {
                    stacks.add(e);
                }
            }
            return stacks;
        }
    }
}

Tower Of Hanoi

 



Towers of Hanoi 

The objective is to move the entire stack to any other rod, obeying these rules: 

• Only one disk can be moved at a time
• Each move consists of taking the upper disk from one rod, adding it onto another rod, on top of any disks that you may have already placed on that rod.
• But no disk can be placed on top of a smaller disk 

The recursive algorithm

• move n-1 disk from the starting pole to the pole which is neither start nor target (intermediate)
• move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
• The n-1 disks are moved recursively 

Pseudo code:

• if ( nDisks == 1 )    return( "Do this move: fromPeg --> toPeg" ); 
• else 
• helpPeg = peg index that is not equal to fromPeg and toPeg; 
• sol1 = hanoi( nDisks-1, fromPeg, helpPeg );
• myStep = "Do this move: fromPeg --> toPeg"; 
• sol2 = hanoi( nDisks-1, helpPeg, toPeg );

How to use the solutions sol1 and sol2 to solve hanoi(nDisks, fromPeg, toPeg): 
 1. first making the moves in sol1
 2. then do myStep
 3. finally, do the moves in sol2

OUTPUT

Move 2 from 2 to 1
Move1from 3 to 1
Move 1 from 3 to 1
Move 3 from 2 to 3
Move1from 1 to 2
Move 1 from 1 to 2
Move 2 from 1 to 3
Move1from 2 to 3
Move 1 from 2 to 3

Java Code

/**
 * three poles and n disks which fit on the poles
 * All disks have different size
 * they are stacked on pole 1 in the orders of their size
 * The largest disk is on the bottom, the smallest is on the top.
 * The task is to move all disk from pole 1 to pole 3 under the following restrictions
 * Only one disk can be moved
 * A larger disk can not be placed on a smaller disk
 *
 * recursive algorithm works like the following: move n-1 disk from the starting pole
 * move disk n to the target pole and then move n-1 disk from the intermediate pole to the target pole
 *
 * n-1 disks are moved recursively
 *
 * @author ravi
 *
 */
public class TowerOfHanoi {
    /**
     * Pole are labeled 1, 2,3
     * Each disk is also labeled
     *
     * @param args
     */
    public static void main(String[] args) {
        move(4, 1, 3);
    }
    /**
     * For first (n-1) elemnet, end pole will be intermediate pole
     * And n element will be moved to last pole
     *
     * @param n
     * @param stratPole
     * @param endPole
     */
    static void move(int n, int stratPole, int endPole){
        if(n==0){
            return;
        }
        if(n==1){
            System.out.println("Move" + n + "from "+ stratPole +" to " + endPole);
        }       
        int intermediatePole = 6-endPole - stratPole;//3+2+1=6
        move(n-1, stratPole, intermediatePole);
        System.out.println("Move " + n + " from "+ stratPole +" to " + endPole);
        move(n-1, intermediatePole, endPole);
    }

}

Binary Tree Example In Java

OUTPUT

----Binary Tree Example--------
Binar Tree with Root Value: 25
--------------------------
inserted value to left of node11
inserted value to right of node14
inserted value to right of node55
inserted value to right of node93
inserted value to right of node93
inserted value to right of node44
inserted value to left of node44
-----------------------------
Traversing order
Traversed Order 11
Traversed Order 14
Traversed Order 25
Traversed Order 44
Traversed Order 55
Traversed Order 93
 

---------------------------------------------------------------

Code as
---------


/**
 * Binary Search Tree Left node will be less than parent node Right node will be
 * greater than parent node Each node has distinct key Information represented
 * by node is the object element Nodes are compared according to their keys than
 * any part of their associate records
 *
 * @author ravi
 *
 */
public class BinaryTreeExample {
    /**
     * Inside this class we have a static node class and have two static node
     * variable Node left, Node right and int value to store the respective node
     * value.
     */
    static class Node {
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * Inside the main method we instantiate Binary Tree that call run( ) method
     */
    public static void main(String[] args) {
        System.out.println("----Binary Tree Example--------");
        BinaryTreeExample bTree = new BinaryTreeExample();
        bTree.run();
    }

    /**
     * The run method ( ) create an instance of node class start with node value
     * of 25
     */
    public void run() {
        Node rootnode = new Node(25);
        System.out.println("Binar Tree with Root Value: " + rootnode.value);
        System.out.println("--------------------------");
        /**
         * Add leaf values to Tree
         *
         * Information represented by node is the object element
         */
        insert(rootnode, 11);
        insert(rootnode, 14);
        insert(rootnode, 55);
        insert(rootnode, 93);
        insert(rootnode, 44);
        System.out.println("-----------------------------");
        System.out.println("Traversing order");
        printInOrder(rootnode);
    }

    /**
     * The insert method accept a node and int as argument value
     *
     * 2-->3--->4 (left->parent->right)
     *
     * @param node
     * @param value
     */
    public void insert(Node node, int value) {
        // left value will always be less than parent
        if (value < node.value) {
            // if left node exist, move inside.
            if (node.left != null) {
                insert(node.left, value);
            } else {
                System.out.println("inserted value to left of node" + value);
                /**
                 * left node object will get value
                 *
                 * create Node object with value and assign it left node
                 */
                node.left = new Node(value);
            }
        } else if (value > node.value) {
            System.out.println("inserted value to right of node" + value);
            // right node ill have greater value
            // if right node exist
            if (node.right != null) {
                insert(node.right, value);
            } else {
                node.right = new Node(value);
            }
        }

    }

    /**
     * The rootnode.value return you the value of the node
     *
     * @param node
     */
    public void printInOrder(Node node) {
        if (node != null) {
            printInOrder(node.left);
            System.out.println("Traversed Order " + node.value);
            printInOrder(node.right);
        }
    }

}

 

Tips for Interview Preparation

1. Read Basic Theory
2. Drive into the CookBook
1. CarrerCup
2. Cracking The Code Interview
3. Glassdoor.com
3. Ask Recruiter for much information about Interview
4. Practise On Notebook

HTML5 – A Short Description

HTML5 – A Short Description

Introduction

1. HTML5 is the next major revision to HTML

New HTML5 Tags

1. <section> – breaks a document into its logical sections
2. <header> – represents a header section, note that this represents a document header, and is different from <head> tag which is a HTML header
3. <footer> – represents a document footer
4. <aside> – represents an “aside” section that is unrelated to the rest of the document
5. Form inputs in HTML5 also introduced new input elements such as <datetime>, <tel>, <url>, etc. Contrast this with <input type=”text”>
6. HTML5 also introduced the famous <video> and <audio> tags for playing of videos and audio files respectively

Semantic Markup and Page Layout

• article
• aside
• figcaption
• figure
• footer
• header
• hgroup
• mark
• nav
• section
• time

1. Headers and footers are self-explanatory and nav creates a navigation or menu bar. You can use sectionsand articles to group your content.
2. aside element can be used for secondary content, for example, as a sidebar of related links.
3. hgroup element, which grouped together my h1 and h2 headers
4. mark element allowed me to highlight or mark some important text.
5. figure and figcaptionelements specify a figure in my content (like an image, diagram, photo, code snippet, etc.)
6. < canvas> tag. It’s just what it sounds like——a blank surface for drawing. You need to use JavaScript to manipulate and draw on the canvas.
7. In HTML5, you can embed audio and video using the new <audio> and <video> tags.

Get HttpServletRequest Via Maven Repository

Get HttpServletRequest Via Maven Repository

Problem

Using Maven build tool, which jar should include to use HttpServletRequest or HttpServletResponse?

Solution

To use HttpServletRequest or HttpServletResponse in development environment, include “serlvet-api.jar” in your Maven pom.xml file.

  <dependency>
 <groupId>javax.servlet</groupId>
 <artifactId>servlet-api</artifactId>
 <version>2.5</version>
 <scope>provided</scope>
  </dependency>

Put scope as “provided“, because most j2ee containers have this jar. You need this for complication only, not deployment.

<dependency>
   <groupId>javax</groupId>
   <artifactId>javaee-api</artifactId>
   <version>6.0</version>
</dependency>