Developer Tips

Here I intend to provide recipes, patterns, and best practices across the areas I am often asked to help with on my consulting engagements.

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.

The HTML Form Elements

The following is a list of all form elements that may be used in an HTML page.
Text Field
Text fields are one line areas that allow the user to input text.

<input type="text" name="lastName" size="25" value="Enter your name here!" />

Password Field
Password fields are similar to text fields. The difference is that what is entered into a password field shows up as dots on the screen. This is, of course, to prevent others from reading the password on the screen.

<input type="password" name="pass" size="25" value="Enter your password here!" />

Hidden Field
The hidden field does not show on the page. Therefore the visitor can’t type anything into a hidden field, which leads to the purpose of the field to submit information that is not entered by the visitor.

<input type="hidden" name="Language" value="English" />

Check Box
Check boxes are used when you want to let the visitor select one or more options from a set of alternatives.

<input type="checkbox" name="option1" value="Milk" /> Milk
<input type="checkbox" name="option2" value="Butter" checked /> Butter
<input type="checkbox" name="option3" value="Cheese" /> Cheese

Radio Button
Radio buttons are used when you want to let the visitor select one – and just one – option from a set of alternatives.

<input type="radio" name="group1" value="Milk" /> Milk
<input type="radio" name="group1" value="Butter" checked /> Butter
<input type="radio" name="group1" value="Cheese" /> Cheese
<hr />
<input type="radio" name="group2" value="Water" /> Water
<input type="radio" name="group2" value="Beer" /> Beer
<input type="radio" name="group2" value="Wine" checked /> Wine

Drop-down Menu
Drop-down menus can serve the same purpose as radio buttons (one selection only) or check boxes (multiple selections allowed). The advantage of a drop-down menu, compared to radio buttons or check boxes, is that it takes up less space. But that is also a disadvantage, because people can’t see all options in the menu right away.

<select name="mydropdown"/>
<option value="Milk">Fresh Milk</option>
<option value="Cheese">Old Cheese</option>
<option value="Bread">Hot Bread</option>
</select>

Text Area
Text areas are text fields that can span several lines.

<textarea cols="40" rows="5" name="myname"></textarea>

HTML 5 Minimal Template

This is a minimal markup your web page should have in order to be validated with the W3C Markup Validation Service

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="utf-8">
    <title>title</title>
    <link rel="stylesheet" href="style.css">
    <script src="script.js"></script>
  </head>
  <body>
    <!-- page content -->
  </body>
</html>

Every HTML document should start with a declaration that tells the browser what version of HTML the document is written in. This code has been specifically designed to “fool” current browsers (that are yet to support HTML5) into treating the document as a full-blooded HTML4 document. Browser versions as far back as Internet Explorer 6 will render the page with their most standards-compliant rendering mode.

The tag should specify the primary language for the document’s content with the a attribute.

The first bit in the header should be a tag that specifies the character encoding of the page. Usually, the character encoding is declared by the web server that sends the page to the browser, but many servers are not configured to send this information. Specifying it here ensures the document is displayed correctly even when it’s loaded directly from disk, without consulting a server.

In CSS and JavaScript declaration, the type=”text/css” and type=”text/javascript” attributes that was required in HTML4 are now optional in HTML5, and all current browsers know what to do if you leave those attributes out.

Several related tips:

Always add a trailing slash to sub folder references. Otherwise, you generate two requests to the server: first, it will add the slash and second, create a new real request.

href="google.com/folder/"

To refresh a page every 30 seconds use this in the page head:

<meta http-equiv="refresh" content="30">

Specify width and height for img element. In this case the space for the image will be reserved by a browser, and the layout won’t change:

<img src="#" width="200" height="200" alt="image" />

The Quick Sort Algorithm

The quick sort algorithm is slower than merge sort algorithm, but requires less space, since it does not copy the array being searched into a temporary array, but performs all operations on the initial array.

The hart of the quick sort is the partitioning process. The algorithm picks a place in the array (usually the last element) and considers it to be a pivot. Then it throws every value that is less than that pivot to the left, and a value greater than the pivot to the right. After that the pivot is placed in the correct position of where it belongs in the array. Then the partitioning process begins in the right part of the array, and in the left part of the array until all elements of the array are sorted.

Code in Java:

public static void main(String[] args) {
  int[] inputArray = {9,8,3,13,87,12,99};
  quickSort(inputArray, 0, inputArray.length-1);
  System.out.println(Arrays.toString(inputArray));
}
	
public static void quickSort(int[] inputArray, int start, int end) {
  if (start < end) {
    int partition = partition(inputArray, start, end); // index position 
    // of the corrected placed element
    quickSort(inputArray, start, partition - 1); // sorts the left half of the range
    quickSort(inputArray, partition + 1, end); // sorts the right half of the range
    }
  }
private static int partition(int[] inputArray, int start, int end) {
  int pivot = inputArray[end]; // pivot at the end of the array
  int i = start - 1;  // the place before the start point (-1)
  for (int j = start; j <= (end - 1); j++) {
    if (inputArray[j] <= pivot) {
      i++;
      // swapping
      int temp = inputArray[i];			
      inputArray[i] = inputArray[j];
      inputArray[j] = temp;
    }
  }
  // put the pivot value in the correct slot next
  int temp = inputArray[i + 1];
  inputArray[end] = temp;
  inputArray[i + 1] = pivot;
  return i + 1;
}

The Merge Sort Algorithm

The merge sort algorithm is pretty fast algorithm for sorting list elements. Its running time is O(n log n). The merge sort may implement a recursive approach. Splitting sets the data to the stage where it is eligible for being merge.

public class MergeSort {
	public static void sort(int inputArray[]) {
		sort(inputArray, 0, inputArray.length-1);
	}
	
	public static void sort(int inputArray[], int start, int end) {
		if (end <= start) {
			return; // done traversing the array
		}
		int mid = (start + end) / 2;
		sort(inputArray, start, mid); // sort left half
		sort(inputArray, mid+1, end); // sort right half
		merge(inputArray, start, mid, end);
	}
	
	public static void merge(int inputArray[], int start, int mid, int end) {
		int[] tempArray = new int[end - start + 1];
		int leftSlot = start;
		int rightSlot = mid + 1;
		int k = 0;
		
		while(leftSlot <= mid && rightSlot <= end) {
			if (inputArray[leftSlot] < inputArray[rightSlot]) {
				tempArray[k] = inputArray[leftSlot];
				leftSlot++;
			} else {
				tempArray[k] = inputArray[rightSlot];
				rightSlot++;
			}
			k++;
		}
		
		if (leftSlot <= mid) {
			while(leftSlot <= mid) {
				tempArray[k] = inputArray[leftSlot];
				leftSlot++;
				k++;
			}
		} else if (rightSlot <= end) {
			while(rightSlot <= end) {
				tempArray[k] = inputArray[rightSlot];
				rightSlot++;
				k++;
			}
		}
		
		for (int i = 0; i < tempArray.length; i++) {
			inputArray[start+i] = tempArray[i];
		}
		
	}
}

Starting point:

int[] inputArray = {9,8,3,13,87,12,99};
MergeSort sorter = new MergeSort();
		
sorter.sort(inputArray);
for (int i = 0; i < inputArray.length; i++) {
    System.out.print(inputArray[i] + " ");
}

The Insertion Sort Algorithm

The insertion sort algorithm is of O(n2) complexity. It divides an array into two sections: a sorted section and unsorted section. In each step of the algorithm the number is moved from unsorted section to sorted one, until the entire array is sorted.
This is a pseudo code:

Procedure: insertionSort(a)
Inputs:
- a: the array to sort
Output:
- a: sorted array in ascending order
Process:
1) For i = 1 to a.length:
a) Set element to a[i] and set j to i-1
b) While j >= 0 and a[j] > element:
i) Set a[j+1] to a[j]
ii) Decrement j by 1
c) Set a[j+1] to element
2) Return the sorted array

The Java code:

public static int[] insertionSort(int[] a) {
  for (int i = 1; i < a.length; i++) {
    int element = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > element) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = element;
  }	
  return a;
}

The Selection Sort Algorithm

The selection sort algorithm has the worst case running time of O(n2) complexity. Given an array it scans from left to right to find the smallest number in the array. Once the algorithm is done scanning the entire array and the smallest number has been found, it is swapped into the first space. Then the scanning process starts over again, but this time from the second space. Once a new minimum has been found, that will be swapped into the second space. And so on.
This is a pseudo code:

Procedure: selectionSort(a)
Inputs:
- a: the array to sort
Output:
- a: the array in sorted ascending order
Process:
1) For i = 0 to a.length:
a) Set minimum to i
b) For j = i + 1 to a.length. If a[j] < a[minimum], then set minimum to j
c) Swap a[i] with a[minimum]
2) Return the sorted array

Code in Java

public static int[] selectionSort(int a[]) {
    for (int i = 0; i < a.length; i++) {
        int minimum = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[minimum]) minimum = j;
        }
        int temp = a[i];
        a[i] = a[minimum];
        a[minimum] = temp;
    }
    return a;
}