In this post, I would like to write down some notes on dynamic data structures that grow and shrink at execution time. Linked lists, queues, stacks and binary trees will follow in this post.

Node
A class that contains an instance variable that refers to another object of the same class type is called a self-referential class.

package LinkedList;

public class Node> {
	private Node< T > nextNode;
	private T data;

	public Node(Node< T > nextNode, T data){
		this.nextNode = nextNode;
		this.data = data;
	}
	public Node(T data){
		this.nextNode = null;
		this.data = data;
	}
	public Node(){
		this(null,null);
	}

	public Node< T > getNextNode(){ return nextNode; }
	public T getData(){return data;}

	public void setNextNode(Node< T > nNode){ this.nextNode = nNode; }
	public void setData(T data){ this.data = data; }

	public boolean equals(Node< T > n){
		return data.equals(n.getData());
	}

	public int compareTo(Node< T > n){
		return data.compareTo(n.getData());
	}

}

If you have multiple data objects that are linked together, they will make a linked list, queues, stacks and trees.

Linked List
Linked lists are nodes that are connected together by their reference node. The last link will return null. A node can contain data of any type. Linked list are dynamic, which means that the length of the list can increase or decrease as necessary.

package LinkedList;

public class Person implements Comparable< Person > {
	private String name;
	private int age;

	public Person(String name, int age){
		this.name = name;
		this.age = age;
	}
	public Person(){
		this("Not Set",0);
	}

	public void setName(String newName){ this.name = newName;}
	public void setAge(int newAge){ this.age = newAge; }

	public int getAge() {
		return age;
	}
	public String getName() {
		return name;
	}

	public String toString(){
		return String.format("Name: %10s. Age: %10s.\n", name, age);
	}

	public boolean equals(Object o){
		return name.equals(((Person)o).getName());
	}

	public int compareTo(Person p){
		return name.compareTo(p.getName());
	}
}

package LinkedList;

public class List< T extends Comparable< T > > {
	private Node< T > firstNode;
	private Node< T > lastNode;
	private int size;

	public List(Node< T > firstNode, Node< T > lastNode, int size){
		this.firstNode = firstNode;
		this.lastNode = lastNode;
		this.size = size;
	}
	public List(){ this(null,null,0); }

	public void setNodeInFront(Node< T > newNode){
		if(firstNode == null && lastNode == null){
			firstNode = lastNode = newNode;
		}else{
			newNode.setNextNode(firstNode);
			firstNode = newNode;
		}
		size++;
	}

	public void setNodeInBack(Node< T > newNode){
		if(firstNode == null && lastNode == null){
			lastNode = firstNode = newNode;
		}else{
			Node< T > node = firstNode;
			while(node.getNextNode() != null){
				node = node.getNextNode();
			}
			if(node.getNextNode() == null){
				node.setNextNode(newNode);
				lastNode = newNode;
			}
		}
		size++;
	}

	public void printAll(){
		System.out.println(toString());
	}

	//print all nodes
	public String toString(){
		String data = "";
		Node< T > node = firstNode;
		while(node != null){
			data += node.getData().toString();
			node = node.getNextNode();
		}
		return data;
	}

	public Node< T > removeAtBack(){
		Node< T > removedNode = new Node();

		if(lastNode != null && firstNode != null){
			removedNode = firstNode;
			while(removedNode.getNextNode().getNextNode() != null){
				removedNode = removedNode.getNextNode();
			}
			if(removedNode.getNextNode().getNextNode() == null){
				lastNode = removedNode;
				removedNode.setNextNode(null);
				removedNode = removedNode.getNextNode();
			}
		}
		size--;
		return removedNode;
	}
	public Node removeAtFront(){
		Node< T > removedNode = new Node< T >();
		if(firstNode != null && lastNode != null){
			removedNode = firstNode;
			firstNode = firstNode.getNextNode();
		}
		size--;
		return removedNode;
	}

	// MAKE A REMOVENODE( NODE ) !!!

	public Node< T > getFirstNode() {return firstNode;}
	public Node< T > getLastNode() {return lastNode;}
	public int getSize() {return size;}

	public void setSize(int size) {	this.size = size; }

}

package LinkedList;

public class Client {
	public static void main(String[] args){
		List< Person > list = new List< Person >();
		list.setNodeInFront(new Node< Person >(new Person("Ramy",20)));
		list.setNodeInFront(new Node< Person >(new Person("Millad",23)));
		list.setNodeInBack(new Node< Person >(new Person("David",12)));
		list.setNodeInFront(new Node< Person >(new Person("Mark",16)));
		list.setNodeInBack(new Node< Person >(new Person("John",12)));

		list.printAll();
		list.removeAtFront();
		list.removeAtBack();
		list.printAll();

	}
}

Code prints out:

Name:       Mark. Age:         16.
Name:     Millad. Age:         23.
Name:       Ramy. Age:         20.
Name:      David. Age:         12.
Name:       John. Age:         12.

Name:     Millad. Age:         23.
Name:       Ramy. Age:         20.
Name:      David. Age:         12.

Stacks
Stacks is a bit different from LinkedLists, new items/nodes can be added and removed from only the top of the stack hence the name stack. Stack has two methods, pop and push. The pop method will remove item/node, and push will add a new item/node to the stack. The easiest way to create a stack is to extend our List class and add the methods pop and push which do the same thing as insertInFront and removeAtFront methods.

// The class is generic but you can use not a generic class.
// Note that the List class extends Comparable !
public class MyStack< T extends Comparable< T > > extends List< T > {
	public MyStack(){ super(); }
	public void push(T o){
		setNodeInFront( new Node< T >( o ) );
	}
	public Node< T > pop(){
		return removeAtFront();
	}
}

If you want to do a stack composition, you then do the same thing but without extending the List, just declare the List and use its methods.

package LinkedList;

public class MyStack< T extends Comparable< T > > {
	private List< T > list;
	public MyStack(){
		list = new List< T >();
	}
	public void push(T o ){
		list.setNodeInFront( new Node< T >( o ) );
	}
	public Node< T > pop(){
		return list.removeAtFront();
	}
}

Queues
Queue is like a checkout line in a supermarket. It’s all about the person/object at the beginning of the line first. New persons/items will only enter from the back and wait. We are going to use to methods from our list, one that adds a new item to the back, and one that removes items from the front.

package LinkedList;

public class MyQueue< T extends Comparable< T > > extends List< T > {
	public MyQueue(){
		super();
	}

       // remove from front
	public Node< T > dequeue(){
		return removeAtFront();
	}

        // add to back
	public void enqueue(Node< T > node){
		setNodeInBack(node);
	}
}

Trees
Trees are different from Linked lists, stacks and queues which are arranged in or extending along a straight or nearly straight line, while Trees are not. Tree nodes contain two or more links.

In this quick note, I’m going to write a tree that will put the lower integer values at the left side and the higher integer values at the right side, just like the picture above.

This is a new Node Class which differs from the one used earlier.

package Trees;

public class Node {

	Node leftNode, rightNode;
	int data;

	public Node( int nodeData ){
		this.data = nodeData;
		leftNode = rightNode = null;
	}
	public void insert( int newData ){
		if( newData < data ){
			if( leftNode == null){
				leftNode = new Node ( newData );
			}else{
				leftNode.insert (newData );
			}
		}else if(newData > data ){
			if( rightNode == null ){
				rightNode = new Node( newData );
			}else{
				rightNode.insert( newData );
			}
		}
	}

}

package Trees;

public class Tree {

	private Node rootNode;

	public Tree(){ rootNode = null; }

	public void insertNode ( int theValue ){
		if( rootNode == null ){
			rootNode = new Node( theValue );
		}else{
			rootNode.insert( theValue );
		}
	}

	public void print(){
		printNodes(rootNode);
	}

	public void printNodes(Node node){
		if( node == null ){
			System.out.println("Seeking...");
			return;
		}
		System.out.println(node.data);
		printNodes(node.leftNode);
		printNodes(node.rightNode);

	}
}

package Trees;

public class Client {
	public static void main(String[] args) {

		Tree tree = new Tree();

		tree.insertNode(2);
		tree.insertNode(3);
		tree.insertNode(55);

		tree.print();

	}

}