In this article lets discuss about how to write a simple data structure in java.
Data structure is a logical representation of data. There are different datastructures in java like Array, ArrayList, Set, Map etc. Each one has their own logical representation of the data elements. For example, ArrayList stores data in an ordered(in which it is inserted) but unsorted way.
TreeMap stores data in sorted order. Each datastructure will have methods for inserting, deleting and iterating the data elements. Now, you may ask the question why we need a new data structure?. In most cases, you may use the data structures available in java api for your programming needs. In some special cases, you may be required to write a custom data structure, considering performance issues like data retrieval time, data traversal time etc.
Whatever may be the scenario its good to know how to write a data structure in java. Its pretty simple!
Lets, take the example of BinaryTree and implement the same as a data structure. Binary tree is a inverted tree like data structure with nodes and vertex. Nodes represent the data elements and vertex is the connection line between nodes. Every binary tree has a root element and child elements.
Mostly we use binary tree for searching and sorting. The elements in the left side of the root element are the values less than the root element. The elements greater than the root element are present in the right side, like (left < root < right). This rule is followed till the end of the tree which contains leaf nodes. Leaf nodes are present in the end of the binary tree with no left or right nodes.
The following BinaryTree program, can be used to insert elements, retrieve them in sorted order and also delete the elements. This is a generic data structure (i.e) you can insert element of any type, which should be comparable to itself, BinaryTree
Basically all immutable types like Integer, String, Double etc., will work fine with this data structure. Whenever you delete an element the data structure will rearrange to form a new tree with the remaining elements. The program below is self explanatory with comments.
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*/
package in.techdive.java.ds;
import java.util.ArrayList;
/**
* This class represents a simple Binary tree data structure, with basic insertion , search,
* traversal and deletion operations. The elements inserted should be comparable to itself.
*/
public class BinaryTree<T extends Comparable<T>>
{
public BinaryTree()
{
}
private T t = null;
private BinaryTree<T> left = null;
private BinaryTree<T> right = null;
private BinaryTree<T> root = null;
private boolean traverse = false;
private ArrayList<T> aList = new ArrayList<T>();
public boolean isTraverse()
{
return traverse;
}
public void setTraverse(boolean traverse)
{
this.traverse = traverse;
}
public BinaryTree<T> getLeft()
{
return left;
}
public void setLeft(BinaryTree<T> left)
{
this.left = left;
}
public BinaryTree<T> getRight()
{
return right;
}
public void setRight(BinaryTree<T> right)
{
this.right = right;
}
public BinaryTree<T> getRoot()
{
return root;
}
public void setRoot(BinaryTree<T> root)
{
this.root = root;
}
public T getT()
{
return t;
}
public void setT(T t)
{
this.t = t;
}
public ArrayList<T> getaList()
{
return aList;
}
public void setaList(ArrayList<T> aList)
{
this.aList = aList;
}
/**
* This method is used to insert data into the Binary Tree. The passed argument should also be
* Binary Tree with a comparable type. The first element inserted will be the logical root
* element(whose root will be always null). The successive elements inserted will be stored in
* left or right node based on comparison.
*/
public void insert(BinaryTree<T> bTree)
{
if (root == null)
{
if (t == null)
{
setT(bTree.getT());
return;
}
}
if (getT().compareTo(bTree.getT()) > 0)
{
if (left == null)
{
left = bTree;
left.setRoot(this);
}
else
{
left.insert(bTree);
}
}
else if (getT().compareTo(bTree.getT()) == 0)
{
return;
}
else
{
if (right == null)
{
right = bTree;
right.setRoot(this);
}
else
{
right.insert(bTree);
}
}
}
/**
* This method is used to delete a particular element in the Binary Tree. The passed argument
* should be a comparable type. A recursive binary search will be performed to search for the
* given element to be deleted. Once the element is found the elements below the element to be
* deleted in the tree and mapped to the root element accordingly so that the rule of (left<root<right)
* is maintained.
*/
public void delete(T t)
{
boolean deleted = false;
if (deleted == true)
{
return;
}
if (getT().compareTo(t) > 0)
{
if (left == null)
{
System.out.println("Element -> " + t + " not found.");
}
else
{
left.delete(t);
}
}
else if (getT().compareTo(t) == 0)
{
BinaryTree<T> btr = getRoot();
if (btr == null)
{
if (left == null && right == null)
{
setT(null);
deleted = true;
return;
}
if (left != null && right == null)
{
BinaryTree<T> currLeft = left;
currLeft.root = null;
setT(null);
btr = currLeft;
deleted = true;
return;
}
if (left == null && right != null)
{
BinaryTree<T> currLeft = left;
BinaryTree<T> currRight = right;
currLeft.root = null;
currRight.root = null;
setT(null);
btr = currLeft;
btr.insert(currRight);
deleted = true;
return;
}
if (left != null && right != null)
{
BinaryTree<T> currRight = right;
currRight.root = null;
setT(null);
btr = currRight;
deleted = true;
return;
}
}
if (left == null && right == null)
{
if (btr.getLeft() != null && btr.getLeft().getT().compareTo(t) == 0)
{
btr.setLeft(null);
}
else if (btr.getRight() != null && btr.getRight().getT().compareTo(t) == 0)
{
btr.setRight(null);
}
}
if (left == null && right != null)
{
BinaryTree<T> currRight = right;
if (btr.getLeft() != null && btr.getLeft().getT().compareTo(t) == 0)
{
btr.setLeft(null);
btr.left = currRight;
currRight.root = btr;
}
else if (btr.getRight() != null && btr.getRight().getT().compareTo(t) == 0)
{
btr.setRight(null);
btr.right = currRight;
currRight.root = btr;
}
}
if (left != null && right == null)
{
BinaryTree<T> currLeft = left;
if (btr.getLeft() != null && btr.getLeft().getT().compareTo(t) == 0)
{
btr.setLeft(null);
btr.left = currLeft;
currLeft.root = btr;
}
else if (btr.getRight() != null && btr.getRight().getT().compareTo(t) == 0)
{
btr.setRight(null);
btr.right = currLeft;
currLeft.root = btr;
}
}
if (left != null && right != null)
{
BinaryTree<T> currLeft = left;
BinaryTree<T> currRight = right;
if (btr.getLeft() != null && btr.getLeft().getT().compareTo(t) == 0)
{
btr.setLeft(null);
btr.left = currLeft;
currLeft.root = btr;
currRight.root = null;
btr.insert(currRight);
}
else if (btr.getRight() != null && btr.getRight().getT().compareTo(t) == 0)
{
btr.setRight(null);
btr.right = currLeft;
currLeft.root = btr;
currRight.root = null;
btr.insert(currRight);
}
}
deleted = true;
return;
}
else
{
if (right == null)
{
System.out.println("Element -> " + t + " not found.");
}
else
{
right.delete(t);
}
}
}
/**
* This method is used to search for a particular element in the Binary Tree. The passed
* argument should be a comparable type. A recursive binary search will be performed to search
* for the given element with a complexity 0(logn).
*/
public void search(T t)
{
if (getT().compareTo(t) > 0)
{
if (left == null)
{
System.out.println("Element -> " + t + " not found.");
}
else
{
left.search(t);
}
}
else if (getT().compareTo(t) == 0)
{
System.out.println("Element ->" + t + " found.");
return;
}
else
{
if (right == null)
{
System.out.println("Element -> " + t + " not found.");
}
else
{
right.search(t);
}
}
}
/**
* This method is used to traverse or iterate through the binary tree in such a way that (left <
* root < right) is maintained so that the returned ArrayList will be in sorted order. It uses a
* flag to check whether an element is already traversed or not.
*/
public ArrayList<T> traverse(BinaryTree<T> tree)
{
if (tree == null)
{
return null;
}
if (tree.getLeft() != null && tree.getLeft().isTraverse() == false)
{
traverse(tree.getLeft());
}
if (tree.getLeft() == null)
{
if (tree.isTraverse() == false)
{
if (tree.getT() != null)
aList.add(tree.getT());
tree.setTraverse(true);
}
}
if ((tree.getLeft() != null && tree.getLeft().isTraverse() == true))
{
if (tree.isTraverse() == false)
{
if (tree.getT() != null)
aList.add(tree.getT());
tree.setTraverse(true);
}
}
if (tree.getRight() != null && tree.getRight().isTraverse() == false)
{
traverse(tree.getRight());
}
if (tree.getRight() == null)
{
if (tree.isTraverse() == false)
{
if (tree.getT() != null)
aList.add(tree.getT());
tree.setTraverse(true);
}
traverse(tree.getRoot());
}
if ((tree.getRight() != null && tree.getRight().isTraverse() == true))
{
if (tree.isTraverse() == false)
{
if (tree.getT() != null)
aList.add(tree.getT());
tree.setTraverse(true);
}
traverse(tree.getRoot());
}
return aList;
}
/**
* This method is used to set the traversal flag to false for all the elements in the binary
* tree, so that the binary tree can be traversed from beginning. It should be used before the
* traversal method is called.
*/
public void removeTraverseRef(BinaryTree<T> tree)
{
if (tree.getLeft() != null && tree.getLeft().isTraverse() == true)
{
removeTraverseRef(tree.getLeft());
}
if (tree.getLeft() == null)
{
tree.setTraverse(false);
}
if (tree.getRight() == null)
{
tree.setTraverse(false);
if (tree.getRoot() != null)
removeTraverseRef(tree.getRoot());
}
if ((tree.getRight() != null && tree.getRight().isTraverse() == true))
{
tree.setTraverse(false);
removeTraverseRef(tree.getRight());
}
}
public static void main(String[] args)
{
System.out.println("Binary Tree Example ");
int srchInt = 12;
int delInt = 14;
Integer[] intArr = new Integer[] { 21, 1, 7, 6, 3, 8, 14, 29, 19, 12, 10, 11 };
BinaryTree<Integer> bTreeInt = new BinaryTree<Integer>();
System.out.println("Inserting Integer Elements : ");
for (int i = 0; i < intArr.length; i++)
{
BinaryTree<Integer> b1 = new BinaryTree<Integer>();
b1.setT(intArr[i]);
bTreeInt.insert(b1);
}
System.out.println("After Insertion Sorter order of the elements : ");
System.out.println(bTreeInt.traverse(bTreeInt));
System.out.println("Searching the element : " + srchInt);
bTreeInt.search(srchInt);
System.out.println("Deleting the Element " + delInt);
bTreeInt.delete(delInt);
bTreeInt.removeTraverseRef(bTreeInt);
bTreeInt.setaList(new ArrayList<Integer>());
System.out.println("Tree Traversal after the deletion : ");
System.out.println(bTreeInt.traverse(bTreeInt));
System.out.println("_____________________________________________");
System.out.println();
String srchElem = "Galileo";
String delElem = "Newton";
System.out.println("Inserting String Elements : ");
String[] strArr = new String[] { "Newton", "Archimedes", "Sigmund", "Einstein",
"Aristotle", "Galileo", "Raman" };
BinaryTree<String> bTreeStr = new BinaryTree<String>();
for (int i = 0; i < strArr.length; i++)
{
BinaryTree<String> b2 = new BinaryTree<String>();
b2.setT(strArr[i]);
bTreeStr.insert(b2);
}
System.out.println("After Insertion Sorter order of the elements : ");
System.out.println(bTreeStr.traverse(bTreeStr));
System.out.println("Searching the element : " + srchElem);
bTreeStr.search(srchElem);
System.out.println("Deleting the Element " + delElem);
bTreeStr.delete(delElem);
bTreeStr.removeTraverseRef(bTreeStr);
bTreeStr.setaList(new ArrayList<String>());
System.out.println("Tree Traversal after the deletion : ");
System.out.println(bTreeStr.traverse(bTreeStr));
}
}
Have a look at the sample output to get a better idea.
Output:
Inserting Integer Elements :
After Insertion Sorter order of the elements :
[1, 3, 6, 7, 8, 10, 11, 12, 14, 19, 21, 29]
Searching the element : 12
Element ->12 found.
Deleting the Element 14
Tree Traversal after the deletion :
[1, 3, 6, 7, 8, 10, 11, 12, 19, 21, 29]
_____________________________________________
Inserting String Elements :
After Insertion Sorter order of the elements :
[Archimedes, Aristotle, Einstein, Galileo, Newton, Raman, Sigmund]
Searching the element : Galileo
Element ->Galileo found.
Deleting the Element Newton
Tree Traversal after the deletion :
[Archimedes, Aristotle, Einstein, Galileo, Raman, Sigmund]
In this way, you can write a custom data structure of your own, when you have a specific need. You can also implement Iterator interface for the above Binary Tree so that the elements can be retrieved one by one is sorted order.