Posts

Showing posts from June, 2010

HashMap Internal

I always wanted to implement the logic behind the famous data structure of Java , HashMap and here it comes. Though it’s not the complete implementation considering all optimization scenarios, but it will highlight the basic algorithm behind the HashMap . So let’s start, this implementation will use my LinkedList implementation (Reason: for this implementation I thought to write everything from the scratch apart from primitive data types. Sounds weird? May be ;-) ). You may refer my earlier post on LinkedList , as I’m going to use it. HashMap is a key-value pair data structure, where you retrieve value by passing key. To optimize the search of key, a concept of Bucket (an Array of Java Objects) has been introduced. This is used, so that if search hits this Bucket , corresponding value element is instantly retrieved, otherwise it iterates sequentially through the Linked List associated with each Bucket element. So you can say if all HashMap elements get fit into the Bucket, retrieving

Binary Search Tree in Java

--> This post is a part of my continuous effort to just implement few of the important data structures in Java. Please find my previous post on LinkedList and QuickSort . This post is regarding BST (Binary Search Tree). Let’s first declare the structure of a BST Node /**   * BST Node Structure   * @author prasanta   */ public class BST_Node {       /**         * Left subtree pointer         */       BST_Node left ;       /**         * Right subtree pointer         */       BST_Node right ;       /**         * key which is used for comparison         */       int value ; } Add Node into BST BST_Node root ;       public void insert( int value){       root = add( root , value); }       private BST_Node add( BST_Node node, int value){       if (node == null ){             node = new BST_Node ();             node. value = value;             return n

QuickSort in Java

This post is a part of my continuous effort to just implement few of the important data structures in Java. Please find my previous post on LinkedList . Probably I just want to pay back, those bunking college days.... :-) Anyway, whatever be the case I'm really enjoying doing this.....   Let’s start with the output- Array to sort: [80, 30, 10, 5, 7, 40, 0] Mid: 3 Pivot: 5 Left Array: [5, 0] Right Array: [80, 30, 10, 7, 40] Mid: 1 Pivot: 0 Left Array: [0] Right Array: [5] Inter list: (can u see that ? it's getting better) 0 5 Mid: 2 Pivot: 10 Left Array: [10, 7] Right Array: [80, 30, 40] Mid: 1 Pivot: 7 Left Array: [7] Right Array: [10] Inter list: (can u see that ? it's getting better) 7 10 Mid: 1 Pivot: 30 Left Array: [30] Right Array: [80, 40] Mid: 1 Pivot: 40 Left Array: [40] Right Array: [80] Inter list: (can u see that ? it's getting better) 40 80 Inter list: (can u see that ? it's getting better) 30 40 80 Inter list: (c