A Basic Implementation of Generic Tree in Java

A generic tree data structure can be implemented in Java with the concept of an object to define a node and the object itself having a reference to n children nodes (or null to point the tree termination i.e. Leaf Nodes).

The following is a very trivial implementation of this data structure to show the concept of generic tree. The use of an array is completely voluntary, you can use any other datastructure of your choice to hold the children based on your need (Such as ArrayList or even LinkedLists).

This code any any other codes published in this blog are also available at Github (search for icodejava)

package com.icodejava.blog.published.datastructure;

/**
 * 
 * @author Kushal Paudyal www.icodejava.com Created On - Dec 5, 2016 Last
 *         Modified On - Dec 5, 2016
 * 
 *         This class shows a basic implementation of Generic Tree concept in
 *         Java.
 */
public abstract class AbstractGenericTreeNode {

	private AbstractGenericTreeNode [] children;

	public AbstractGenericTreeNode [] getChildren() {
		return children;
	}

	public void setChildren(AbstractGenericTreeNode [] children) {
		this.children = children;
	}
	
	public int getNumberOfChildren () {
		
		return children != null ? children.length : 0;
	}
	
}

The following is a concrete implementation of the Abstract node above and is defined to hold integer values. You however can implement this class to hold the object of your choice.

package com.icodejava.blog.published.datastructure;

/**
 * 
 * @author Kushal Paudyal www.icodejava.com Created On - Dec 5, 2016 Last
 *         Modified On - Dec 5, 2016
 * 
 *         This class shows a basic implementation of Generic Tree concept in
 *         Java.
 */

public class IntegerTreeNode extends AbstractGenericTreeNode {
	private int value;

	public IntegerTreeNode(int value, AbstractGenericTreeNode[] children) {
		super();
		this.value = value;
		this.setChildren(children);
	}

	public int getValue() {
		return value;
	}

}

Generic trees are different from Binary Trees. Binary Trees have 2 child nodes at maximum whereas the generic trees can have n-number of children.

Basic example of implementing Singly Linked List in Java

The following is a very basic example of a Singly Linked List implementationin Java. In a nutshell, it’s an object that holds a value for itself and also has a reference to another object in the list, which could be null of the object itself is the tail (i.e. last element in the linked list)

package com.icodejava.blog.published.datastructure;
/**
 * @author Kushal Paudyal
 * Created on - 11/28/2016
 * Last modified on - 11/28/2016
 * This class shows a basic example of defining a SinglyLinkedList in Java
 * Also provides a overridden constructor both of which are optional.
 */
public class SinglyLinkedList {
	
	private Object value;
	private SinglyLinkedList nextObject;
	
	public SinglyLinkedList(Object value) {
		this.value = value;
		this.nextObject = null;
	}
	
	public SinglyLinkedList(Object value, SinglyLinkedList nextObject) {
		this.value = value;
		this.nextObject = nextObject;
	}
	
	
	public Object getValue() {
		return value;
	}
	public void setValue(Object value) {
		this.value = value;
	}
	public SinglyLinkedList getNextObject() {
		return nextObject;
	}
	public void setNextObject(SinglyLinkedList nextObject) {
		this.nextObject = nextObject;
	}

}


Linked List is a data structure that possess following properties:

  • The are a group of nodes linked together by some reference. Singly linked list has reference to next node, while doubly linked list has reference to previous and next nodes.
  • Elements can be inserted indefinitely.
  • They don’t take contiguous memory locations. For this reason, they are suitable to be used even if the disk or memory is fragmented.
  • They allow sequential access to elements while arrays allow random access
  • Extra space is needed for reference. It is impractical to use for boolean or char for space wastage.

Singly linked list might not be a right data structure for all situations, so a care must be taken in choosing the data structure for your problem. As the link in the singly linked list only points to the location of the next object (and not in reverser order), singly linked list can only be traversed in forward direction. Also, you need to know the location of the first node or object to be able to traverser rest of the nodes or objects.

How to Add and Remove nodes in an unsorted Linked List

Class Diagram: LinkedListNode and LinkedListOperation

If you add any new nodes to the tail of the current linked list, the list will become unsorted, because it does not care what values you are passing, it will simply keep appending the new node at the end of the list. Thus any add operation is O(n) because you will have to sequentially navigate to the end of the list before adding the new node.

Time complexity of remove operation, however varies. If you are removing the head node, the operation takes O(1) time and if you are removing the tail, it takes O(n) time. It really depends on where the node to be deleted is located.

The following source code show you:

  • How to represent unsorted linked list
  • How to add a node
  • How to remove a node

package com.icodejava.blog;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Mar 9, 2014
 * Last Modified On - Mar 9, 2014
 */
public class LinkedListOperation {
	public static void main(String args[]) {

		LinkedListNode linkedList = new LinkedListNode(4).addNode(5).addNode(2).addNode(-5);

		System.out.println("Final List: " + linkedList +"\n");

		// Deleting nodes in an order different from how they were added.
		linkedList = linkedList.removeNode(5).removeNode(-5).removeNode(2).removeNode(4);

		System.out.println("After Removal, the list is: " + linkedList);

	}
}

@SuppressWarnings({"rawtypes", "unchecked"})
class LinkedListNode {
	private LinkedListNode next;
	private Comparable value = null;

	public LinkedListNode(Comparable value) {
		// create first node
		next = null;
		this.value = value;

		System.out.println("Adding Node: " + value);
	}

	/**
	 * This method removes a node from a linked list.
	 */
	public LinkedListNode removeNode(Comparable nodeValue) {

		System.out.println("Removing Node: " + nodeValue);

		if (this.value.compareTo(nodeValue) == 0) { // head
			return this.next;
		} else { // non head

			LinkedListNode current = this;
			LinkedListNode previous = null;

			while (current.next != null) {
				if (current.value.compareTo(nodeValue) == 0) {
					previous.next = current.next;
					return this;
				}

				previous = current;
				current = current.next;
			}

			if (current.value.compareTo(nodeValue) == 0) { // tail
				previous.next = null;
			}

		}

		return this;

	}

	@Override
	public String toString() {

		String data = "";
		LinkedListNode current = this;
		do {
			data += current.value + ",";
			current = current.next;
		} while (current != null);

		return data;
	}

	/**
	 * Adds the node at the tail, making it an unsorted linked list. This method
	 * returns a head node.
	 */
	public LinkedListNode addNode(Comparable value) {

		// if first node
		if (this.next == null) {
			LinkedListNode node = new LinkedListNode(value);
			this.next = node;
			this.next.next = null;
		} else {
			LinkedListNode current = this.next;
			while (current.next != null) {
				current = current.next;
			}

			LinkedListNode node = new LinkedListNode(value);
			current.next = node;
			current.next.next = null;
		}

		return this; // return head
	}

}

Here is the output of running the above program:

Adding Node: 4
Adding Node: 5
Adding Node: 2
Adding Node: -5
Final List: 4,5,2,-5,

Removing Node: 5
Removing Node: -5
Removing Node: 2
Removing Node: 4
After Removal, the list is: null