Data structures

The Singly Linked List

In a singly linked list each node only has a single link to another (next) node. To store a single linked list, you only need to store a reference or pointer to the first node in that list. The last node has a pointer to NULL to indicate that it is the last node.

To define a singly linked list element create a separate class where each element will be an instance of this class. The class will have two property variables: data itself, and a pointer to the next node. Create another class where the list itself will be instantiated as an object. This class will define all methods that the list utilizes, such as insertFirst(), insertLast(), deleteFirst(), deleteLast(), and printList().

The following is a Java code that uses static inner classes:

package dsmy.linkedlist;

public class App {

	public static void main(String[] args) {
		SinglyLinkedList list = new SinglyLinkedList();
		list.insertFirst("First String");
		list.insertFirst("Second String");
		list.insertFirst("Third String");
		list.insertLast("Last String");
		list.deleteFirst();
		list.deleteLast();
		list.printList();

	}
	
	static class SinglyLinkedList {
		private Node first;
		
		public void insertFirst(Object data) {
			Node node = new Node(data);
			node.next = this.first;
			first = node;
		}
		
		public void insertLast(Object data) {
			// Traverse the list from beginning to the last node
			Node current = first;
			while (current.next != null) {
				current = current.next;
			}
			// Insert the node
			Node node = new Node(data);
			current.next = node;			
		}
		
		public void deleteFirst() {
			// The following node becomes the first one
			first = first.next;			
		}
		
		public void deleteLast() {
			// Traverse the list from beginning to one before 
                        // the last node
			Node current = first;
			while (current.next.next != null) {
				current = current.next;
			}
			// The node before the last one becomes the last
			current.next = null;
		}
		
		public void printList() {
			System.out.println("First --> Last");
			Node current = first;
			while (current != null) {
				current.displayNode();
				current = current.next;
			}
		}
	}
	
	static class Node {
		private Object data;
		private Node next;
		
		Node(Object data) {
			this.data = data;
		}
		
		public void displayNode() {
			System.out.print("{ " + data + " } \t");
		}		
	}
}

The Heap

The Heap is a data structure similar to binary sort tree structure. New nodes are placed to the heap from the top to bottom and from the left to right. Each parent may have no more than two children.

There are two kinds of heaps:

  • The Max heap, where the root node is the largest element of the entire tree.
  • The Min heap, where the root node is the smallest element of the tree.

When you add elements to the heap you add them to the bottom to the
next available slot to the right or down.

When you remove elements from the heap you remove them from the top. The root should be removed and the last element down the tree takes its place. The the new root is compared with its children and the largest element goes to the place of the root. The same process continues to the bottom of the tree.

To figure out parent and children in array that represents a Heap, use
the following formulas:
Left child index position = 2n + 1 (where the n is the index position of the parent)
Right child index position = 2n + 2 (n is its parent position)

To find a parent of the child use the formula:
Parent index position = ⌊(n-1) / 2⌋ (n is its child position)

The Binary Search Tree Data Structure

The binary search tree data structure is inspired by binary search algorithm. The tree inherits the same advantages as that algorithm.

The data is inserted in a sorted manner. It has inserting and deleting benefits of the linked list. This is the most popular data structure in Computer Science with many applications.

The binary search tree as any trees consists of nodes. Each node has no, one ore two children, but no more than two. This is why it is called binary. The top node is called the root. Everything that is on the right side of the root must be greater that the root, and every node one the left side should be smaller than the root. The child that has the same value must go to the left.

To get the most efficiency from the binary search tree, the tree should
be balanced, meaning that for all the nodes in the tree, the difference
between the hights of the left and right sub-trees must not be greater
than one.

Differences among the Singly, Circular, and Doubly Linked List Data Structures

The Circular Linked List data structure is pretty much identical to the
Singly Linked List except for the fact there is an extra reference
called “last”. That gives us an ability to quickly make changes to the
last node. Whereas the Single Linked List only has access to the first
node and in order to get to the end it has to traverse the entire list
of nodes to get to the end, which is not efficient.

Using the Circular Linked List it is possible to implement both the Stack
and the Queue mechanisms, but use the nodes as objects of the Linked List type instead elements of a simple array.

In the Circular and Singly Linked Lists the inner nodes only know about
the next one. Each node does not know anything about the node preceding it. In the Doubly Linked List every node knows about the node that follows it as well as the node that is preceding it, which makes the Doubly Linked List the most efficient and flexible of all Lists.

Queue Data Structure

The Queue data structure allows for FIFO (first in – first out) functionality. Think of this as a simple line to a counter in a store.

public class Queue {

  // Initialize the set number of slots
  private int maxSize;

  // Array (slots) to maintain the data in
  private long[] queArray;

  // Index position for the element in the front
  private int front;

  // Index position for the element at the back
  private int rear;

  // Counter to maintain the number of items in the queue
  private int nItems;

  public Queue(int size) {
    this.maxSize = size;
    this.queArray = new long[size];
    front = 0;
    rear = -1; // no item in the array yet
    nItems = 0;
  }

  // Put to the end of queue
  public void insert(long j) {

    /** Create a circular queue, so each element that is
     * out of the array boundary will go to the beginning 
     * and override the
     * element there.
     */
    if (rear == maxSize - 1) {
      rear = -1;
    }

    rear++;
    queArray[rear] = j;
    nItems++;
  }

  // Remove from the front of queue
  public long remove() {
    long temp = queArray[front];
    front++;
    // reset front to the 0
    if (front == maxSize) {
      front = 0;
    }
    nItems--;
    return temp;
  }

  public long peakFront() {
    return queArray[front];
  }

  public boolean isEmpty() {
    return (nItems == 0);
  }

  public boolean isFull() {
    return (nItems == maxSize);
  }

  public void view() {
    System.out.print("[ ");
    for (int i = 0; i < queArray.length; i++) {
      System.out.print(queArray[i] + " ");
    }
    System.out.print("]");
  }
}

Make it work:

public static void main(String[] args) {
  Queue myQueue = new Queue(5);
  myQueue.insert(10);
  myQueue.insert(20);
  myQueue.insert(30);
  myQueue.insert(40);
  myQueue.insert(50);
}

Stack and Reverse a String Algorithm

The Stack data structure allows for LIFO (last in – first out) functionality. We can use is it within complex structures where we need the order of items to be reversed.
One of a simple examples would be a string reverse method:

public static void main(String[] args) {		
  String str = "system";
  String result = App.reverseString(str);
  System.out.println(result);
}
	
// Algorithm to reverse the string that is passed in as a parameter
public static String reverseString(String str) {  
  Stack stack = new Stack(str.length());
  for (int i = 0; i < str.length(); i++) {			
    stack.push(str.charAt(i));
  }
  String result = "";
  while (!stack.isEmpty()) {
    result  += stack.pop();		
  }
  return result;
}

The Stack class may look like this:

public class Stack {

	// Store the size of the stack
	private int maxSize;

	// Store list of items
	private char[] stackArray;

	// Index position of the last item on the top of the stack
	private int top;

	public Stack(int size) {
		this.maxSize = size;
		this.stackArray = new char[maxSize];
		this.top = -1;
	}

	public void push(char j) {
		if (isFull()) {
			System.out.println(" this stack is already full");
		} else {
			top++;
			stackArray[top] = j;
		}
	}

	public char pop() {
		if (isEmpty()) {
			System.out.println(" this stack is already empty");
			return 0;
		} else {
			int old_top = top;
			top--;
			return stackArray[old_top];	
		}		
	}

	public long peak() {
		return stackArray[top];
	}

	public boolean isEmpty() {
		return (top == -1);
	}

	public boolean isFull() {
		return (maxSize - 1 == top);
	}
}

Of course, there would be a much simpler solution for such a basic operation as a string reverse, but the code above just illustrates the LIFO benefit.

public static String reverseString(String str) {        
    String result = "";   
    for (int i = str.length() - 1; i >= 0; i--) {
      result += str.charAt(i);        
    }        
return result;    
}