Singly Linked List

Singly Linked List is a type of a data structure in which each node stores some kind of data and a pointer or a reference to the next node in the list. Last node in the list (called as a tail) will not point to any other node, hence is reference value is null. First node in the list is called as a head of the Linked List.

Here is a generic implementation of Singly Linked List in java programming language. You can easily implement Stack Or Queue data structures using the Singly Linked List code provided below.

package computer.science;

public class SinglyLinkedList {
 private Node head;
 private int size;

  SinglyLinkedList() {
  head = new Node(null);
  size = 0;
 }

  public T get(int index) {
  if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index out of bounds: " + index);
  }
  if (size == 0) {
   throw new IllegalAccessError("Trying to get element from empty list.");
  }
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }
  Node reqNode = temp.next;
  return reqNode.getData();
 }

  public void add(int index, T data) {
  System.out.println("index=" + index + ", value=" + data);
  if (index < 0 || index > size) {
   throw new IllegalArgumentException("Invalid position specified: " + index);
  }
  Node n = new Node(data);
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }
  n.next = temp.next;
  temp.next = n;
  size++;
 }

  // append to the list
 public void add(T data) {
  add(size, data);
 }

  public T remove(int index) {
  if (index < 0 || index >= size) {
   throw new IndexOutOfBoundsException("Index out of bounds: " + index);
  }
  if (size == 0) {
   throw new IllegalAccessError("Trying to remove element from empty list.");
  }
  Node temp = head;
  int count = 0;
  while (count < index) {
   temp = temp.next;
   count++;
  }

   Node toRemove = temp.next;
  if (toRemove.next != null) {
   temp.next = toRemove.next;
   toRemove.next = null;
  } else {
   temp.next = null;
  }
  size--;
  return toRemove.getData();
 }

  public String toString() {
  if (size == 0) {
   return null;
  } else {
   StringBuilder str = new StringBuilder();
   Node t = head.next;
   for (int i = 0; i < size; i++) {
    str.append(t.data + " ");
    t = t.next;
   }
   str.append("[size=" + size + "]");
   return str.toString();
  }
 }

  public int getSize() {
  return size;
 }

  private class Node {
  Node next;
  T data;

   Node(T data) {
   this.data = data;
   this.next = null;
  }

   public T getData() {
   return data;
  }
 }

  public static void main(String[] args) {
  SinglyLinkedList sLL = new SinglyLinkedList();

   System.out.println("Adding nodes ...");
  sLL.add(sLL.getSize(), 100);
  sLL.add(sLL.getSize(), 99);
  sLL.add(sLL.getSize(), 98);
  sLL.add(sLL.getSize(), 97);
  System.out.println(sLL.toString());
  sLL.add(2, 96);
  System.out.println(sLL.toString());
  sLL.add(1, 95);
  System.out.println(sLL.toString());
  sLL.add(4, 94);
  System.out.println(sLL.toString());
  sLL.add(sLL.getSize(), 93);
  System.out.println(sLL.toString());

   System.out.println();

   System.out.println("Removing nodes ...");
  int t;
  t = sLL.remove(0);
  System.out.println("removed " + t + " from position " + 0);
  System.out.println(sLL.toString());

   t = sLL.remove(6);
  System.out.println("removed " + t + " from position " + 6);
  System.out.println(sLL.toString());

   t = sLL.remove(4);
  System.out.println("removed " + t + " from position " + 4);
  System.out.println(sLL.toString());

   System.out.println();

   System.out.println("Get elements ...");
  System.out.println("Got " + sLL.get(1) + " at position " + 1);
  System.out.println("Got " + sLL.get(sLL.getSize() - 1) + " at position " + (sLL.getSize() - 1));
  System.out.println("Got " + sLL.get(3) + " at position " + 3);

   System.out.println();
  System.out.println(sLL.toString());
 
  System.out.println();
  System.out.println("Appending 55 to the list ...");
  sLL.add(55);
  System.out.println(sLL.toString());
 }

}

Doubly Linked List

In this post, we will implement a doubly linked list in Java. This post is a little different from the theme of this blog(algorithms), but data structures are closely related to algorithms. In fact every computer program is made up of some kind of data structure and algorithm. In other words, a computer program is a combination of data structures and algorithms.

Data structures are used to store the information and algorithms are used to carry out the operations (computations) on those data structures. The efficiency of an algorithm depends on how effectively the data structures are utilized. Data structure can be simple primitive data type (such as int, float, double etc) or very complex data types (such as String, Arrays, Hash Maps, User defined objects (classes)).

Coming back to linked lists ...

Linked List is a data structure consisting of a group of nodes. These nodes are organized in a sequence starting from a first node to the last node. A node is composed of some kind of data and a reference (a pointer or a link) to the next node in the sequence. All nodes in one linked list are similar i.e. they are structurally same. First node of a linked list is called head and last node is called a tail.

There are two types of linked list representations:

1. Singly Linked List
In this type of a representation, each node includes a reference to next node in the sequence. So this linked list can be traversed only in one direction.

2. Doubly Linked List
In this type of a representation, each node includes a reference to previous node and next node in the sequence. So this kind of list can be traversed in both directions i.e. from head to tail or from tail to head. The "previous" pointer in a head node is null and "next" pointer in a tail node is null.

Linked list can be used implement a variety of data structures such as array (ordered list), stack or a queue.

Following basic operations can be performed on a linked list:
1. Add a new node to the list (either at front or at the end)
2. Remove a node (either from front or from end or from some specified position)
3. Get the size of list
4. Traverse and display the data from the list

Above operations can be implemented in various ways and there are many ways to represent it in a computer program.

Following Java program is an example of a doubly linked list implementation. This program can be used to implement a dynamic array or a stack or a queue using doubly linked list.

Remember that a stack is a "first in last out (FILO)" kind of data structure, so you will have to select specific methods out of this program in order to use it as a Stack implementation. Queue is a "first in first out (FIFO) kind of a data structure. So select methods accordinly in order to use it as a Queue implementation.

Note: This program takes advantage of Java's generics feature, hence the client program can use same implementation to create Linked List of a different data type. e.g. It can be used to create a Linked List of Integers or a Linked List of Strings etc.

package computer.science;

public class DoublyLinkedList<T> {
private Node head;
private Node tail;
private int size;

public DoublyLinkedList() {
size = 0;
head = new Node(null);
tail = new Node(null);
head.next = tail;
tail.prev = head;
}

public int getSize() {
return size;
}

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

public void addFront(T data) {
Node n = new Node(data);
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
size++;
}

public void addLast(T data) {
Node n = new Node(data);
n.prev = tail.prev;
n.next = tail;
tail.prev.next = n;
tail.prev = n;
size++;
}

public T removeFirst() {
Node t = head.next;
t.next.prev = head;
head.next = t.next;
size--;
t.prev = null;
t.next = null;
return t.getData();
}

public T removeLast() {
Node t = tail.prev;
t.prev.next = tail;
tail.prev = t.prev;
size--;
t.prev = null;
t.next = null;
return t.getData();
}

// add at specified index
public void add(int pos, T data) {
// System.out.println("adding at index " + index);
if (pos <= 0) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

if (pos > size) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

Node n = new Node(data);
Node t = head;
int count = 1;
while (count < pos) {
t = t.next;
count++;
}

n.next = t.next;
n.prev = t;
t.next.prev = n;
t.next = n;
size++;
}

// remove from specified index
public T remove(int pos) {
if (pos <= 0) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

if (pos > size) {
throw new IllegalArgumentException("Invalid index specified: " + pos);
}

Node t = head;
int count = 1;
while (count < pos) {
t = t.next;
count++;
}

Node toRemove = t.next;

t.next = toRemove.next;
toRemove.next.prev = t;
size--;

toRemove.prev = null;
toRemove.next = null;
return toRemove.getData();
}

public void printList() {
// System.out.println("Size of the List : " + getSize());
Node start = head.next;
while (start.next != null) {
System.out.print(start.getData() + " ");
start = start.next;
}
System.out.println(" [size=" + size + "]");
}

private class Node {
private Node next;
private Node prev;
private T data;

public Node(T data) {
this.next = null;
this.prev = null;
this.setData(data);
}

public T getData() {
return data;
}

public void setData(T data) {
this.data = data;
}

public String toString() {
return data.toString();
}
}

public static void main(String[] args) {
// Integers
int[] intList = { 23, 25, 27, 28, 29, 31, 33, 35 };
DoublyLinkedList<Integer> dLL = new DoublyLinkedList<Integer>();

System.out.println("Adding to the front ...");
for (int i = 0; i < intList.length; i++) {
dLL.addFront(intList[i]);
dLL.printList();
}

System.out.println();
System.out.println("Adding to the end ...");
int[] intList2 = { 213, 215, 217, 218, 219 };
for (int i = 0; i < intList2.length; i++) {
dLL.addLast(intList2[i]);
dLL.printList();
}

System.out.println();
System.out.println("Removing from front ...");
int t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();
t = dLL.removeFirst();
dLL.printList();

System.out.println();
System.out.println("Removing from end ...");
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();
t = dLL.removeLast();
dLL.printList();

System.out.println();
System.out.println("Adding at specified position ...");
dLL.add(3, 1);
dLL.printList();
dLL.add(1, 100);
dLL.printList();
dLL.add(dLL.getSize(), 110);
dLL.printList();

System.out.println();
System.out.println("Removing from specified position ...");
dLL.remove(4);
dLL.printList();
dLL.remove(1);
dLL.printList();
dLL.remove(dLL.getSize());
dLL.printList();

System.out.println();

// Following code is to illustrate genericness of the implementation

// Strings
String[] strList = { "abc", "xyz", "pqr", "efg", "hijk" };
DoublyLinkedList<String> sLL = new DoublyLinkedList<String>();
for (int i = 0; i < strList.length; i++) {
sLL.addFront(strList[i]);
}
sLL.printList();

System.out.println();

// Doubles
Double[] dblList = { 23.23, 25.12, 27.15, 28.5, 29.0, 31.0, 33.98 };
DoublyLinkedList<Double> dblLL = new DoublyLinkedList<Double>();
for (int i = 0; i < dblList.length; i++) {
dblLL.addFront(dblList[i]);
}
dblLL.printList();
}

}

Quick Sort By Hand

Here is a rough by hand quick sort algorithm example :

Quick Sort

Quick Sort is very popular and widely used sort algorithm. Quick Sort is generally unstable. But there are ways to make quick sort stable, it depends on the actual implementation.

A sorting algorithm is stable if it maintains the relative order of the items in the final output i.e. Two objects with equal keys should appear in the same order in the sorted output as they appear in the input array to be sorted.

Quick Sort is divide and conquer type of an algorithm and key part of the quick sort is the partitioning implementation. Partitioning basically divides the input list into multiples parts and sorts each one of them recursively. Quick Sort is in place sort i.e. no extra storage space (variables) are required for quick sort algorithm.

Quick Sort algorithm works as follows:

For a given list
1. Pick a "pivot" element
2. "Partition" the array into three parts:
   i. All elements in this part are less than the pivot
  ii. The pivot itself (one element)
 iii. All elements in this part are greater than or equal to pivot
3. Apply the quick sort algorithm to the first and the third part recursively.

Partitioning is the most crucial part of quick sort and it should be done in place. There are different techniques for choosing a pivot element and partitioning.

Best and average case performance for quick sort is O(nlogn). Its worst case performance is O(n^2).
Again quick sort is very widely used algorithm. If we do random shuffling of the list at the beginning of quick sort, then it almost guarantees O(nlogn) performance.

Simplest implementation of Quick Sort in java is as follows:

package computer.science;

import java.util.Random;

public class QuickSort {

public static void sort(int a[]) {

quicksort(a, 0, a.length - 1);

}

private static void quicksort(int[] a, int lo, int hi) {

int i = lo;

int j = hi;

int pivot = a[(lo + hi) / 2];

// partition

while (i <= j) {

while (a[i] < pivot)

i++;

while (a[j] > pivot)

j--;

if (i <= j) {

if (i != j) // optimization

swap(a, i, j);

i++;

j--;

}

}

// quick sort left side

if (lo < j)

quicksort(a, lo, j);

// quick sort right side

if (i < hi)

quicksort(a, i, hi);

}

private static void swap(int[] a, int x, int y) {

int t = a[x];

a[x] = a[y];

a[y] = t;

}

public static void main(String[] args) {

final int LENGTH = 100;

int[] a = new int[LENGTH];

Random random = new Random();

for (int i = 0; i < LENGTH; i++) {

a[i] = random.nextInt(100);

}

System.out.println("Before sort : ");

display(a);

long startTime = System.nanoTime();

sort(a);

long endTime = System.nanoTime();

System.out.println("After sort : ");

display(a);

double sortTime = (endTime - startTime) / 1000000.0;

System.out.println("Estimated Time for Sort: " 

                                 + sortTime + " milliseconds.");

}

private static void display(int[] a) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

System.out.print(" ");

}

System.out.println();

}

}

Merge Sort

Merge Sort algorithm works as follows:

While the list has more than one elements:
  Divide the list in two halves
  Sort first half
  Sort second half
  Merge sorted lists

This strategy is called divide-and-conquer method. We take advantage of the recursion technique in merge sort. So there are two operations happening recursively, dividing the list into two halves and merging them back. The base case for the recursion is when the list size is one.

Following diagram illustrates merge sort algorithm:

The number of times the list of size n is divided is equal to log(n). Where log(n) resembles to height of a virtual tree created during recursive calls to merge sort.

The time complexity of merge function is linear i.e. it takes exactly n operations to merge two lists of size n/2. Hence the overall time complexity of merge sort is O(n log n).

Here is a java implementation of a merge sort algorithm:

public class MergeSort {

public static void sort(int[] a) {

int left = 0; // start index of the list

int right = a.length - 1; // end index of the list

int[] aux = new int[a.length];

mergeSort(a, aux, left, right);

}

private static void mergeSort(int[] a, int[] aux, 

                                      int left, int right) {

if (left < right) {

int center = (left + right) / 2;

mergeSort(a, aux, left, center);

mergeSort(a, aux, center + 1, right);

merge(a, aux, left, center + 1, right);

}

}

private static void merge(int[] a, int[] aux, int left, 

                                          int right, int rightEnd) {

int leftEnd = right - 1;

int numOfElements = rightEnd - left + 1;

int k = left; // start index to save merged result

while (left <= leftEnd && right <= rightEnd) {

if (a[left] <= a[right]) {

aux[k++] = a[left++];

} else {

aux[k++] = a[right++];

}

}

// copy leftover elements from first list

while (left <= leftEnd) {

aux[k++] = a[left++];

}

// copy leftover elements from second list

while (right <= rightEnd) {

aux[k++] = a[right++];

}

// copy auxiliary back to a

for (int i = 0; i < numOfElements; i++, rightEnd--) {

a[rightEnd] = aux[rightEnd];

}

}

}

Test program to test merge sort algorithm:

import java.util.Random;

public class SortTest {

public final static int LENGTH = 10;

public static void main(String[] args) {

int[] a = new int[LENGTH];

Random random = new Random();

for (int i = 0; i < LENGTH; i++) {

a[i] = random.nextInt(100);

}

System.out.println("Before sort : ");

display(a);

long startTime = System.nanoTime();

MergeSort.sort(a);

long endTime = System.nanoTime();

System.out.println("After sort : ");

display(a);

double sortTime = (endTime - startTime) / 1000000.0;

System.out.println("Estimate Time for Sort: "

                              + sortTime + " milliseconds.");

}

private static void display(int[] a) {

for (int i = 0; i < a.length; i++) {

System.out.print(a[i]);

System.out.print(" ");

}

System.out.println();

}

}

Insertion Sort

Insertion Sort works as follows:

1. Divide the given list into two parts: sorted and unsorted
2. Iterate over unsorted list and insert each element into the sorted list at a proper position
3. So the elements in the sorted list are always in order

Following diagram illustrates this method:

Pseudocode for Insertion Sort:

Insertion-Sort(LIST)

  for j = 2 to LIST.length
      key = LIST[j]
      // insert key into sorted sequence LIST[1 .. j-1]
      i = j - 1
      while i >= 0 and key < LIST[i]
          LIST[i + 1] = LIST[i]
          i = i - 1    
      LIST[i + 1] = key

And here is a Java implementation of Insertion sort algorithm:

public class InsertionSort {
public static void sort(int[] list) {
for (int j = 1; j < list.length; j++) {
int key = list[j];
int i = j - 1;
while (i >= 0 && key < list[i]) {
list[i + 1] = list[i];
i--;
}
list[i + 1] = key;
}
}
}

Worst case running time for insertion sort is quadratic i.e. O(n^2).
Best case (when the array is already sorted) running time is linear i.e. O(n).

Space complexity for insertion sort is O(1) i.e. it requires constant amount of extra storage, in this case only one temporary variable which is "key".

Insertion sort is often a choice when the list is nearly sorted or when the list size small. Insertion is stable because it maintains the order of items which are equal.

Selection Sort - Algorithm Analysis

Let us look at the time and space complexity of the Selection Sort algorithm.

As seen in the above diagram, for n element list, there are total n -1 iterations required. Total number of comparisons required in the first iteration is n - 1, in second iteration n - 2, in third iteration n -2 and so on. This is comparison scenario is equivalent to summation series.

Hence, the time complexity of selection sort using asymptotic Big(O) notation is O(n^2). 

If we consider the swap operations, selection sort takes n swaps (1 swap operation in each iteration). According to the asymptotic notation, the value n^2 will dominate for large values of n. Hence this constant value of swap operations can also be dropped for algorithm analysis. So worst case running time for selection sort is O(n^2).

Space complexity for selection sort is O(1). Extra space is required only during swap operation.

Selection Sort

In selection sort algorithm, list is divided into 2 lists: sorted & unsorted list.
In each iteration, smallest element is selected from unsorted list and appended to the sorted list.

While starting the scan of list, assume that the first element is the smallest, then compare it with the rest of the elements in the list, save the index of smallest element along the way. Once all the elements are scanned, swap the starting index element with the minimum index element (if the indices are different).

Here is a Java implementation of a selection sort algorithm:

In the next post, we will look at the time & space complexity of the selection sort algorithm.

Bubble Sort: Illustrated

Bubble sort is called "Bubble Sort" because the largest item in the list bubbles up to the end of a list after each iteration.

Following images illustrate this concept.

In this example the length of an array is 6.
In first iteration of a for loop (where j = 1), index i starts at 0 and ends at 5 (lenght - j).

In second iteration of a for loop (where j = 2), index i starts at 0 and ends at 4 (lenght - j).

In third iteration of a for loop (where j = 2), index i starts at 0 and ends at 3 (lenght - j).

In fourth iteration of a for loop (where j = 3), index i starts at 0 and ends at 2 (lenght - j).

In this iteration, there was no swapping of items as the list is already sorted. Hence the while loop terminates.

As you can see, after each iteration of a for loop, the length of an iteration reduces by 1 (because of an optimization condition i < length - j). Another optimization used is the boolean variable "swapped", if there no swaps during an iteration, that means the list is already sorted. So we can terminate outer loop immediately.

Optimized Bubble Sort in Java

Bubble sort is a simplest sorting algorithm which is used as a traditional method to introduce sorting concept to the students of computer science. Though it is not very efficient algorithm, it illustrates the sorting methodology very well.

Here is a bubble sort algorithm with "two optimizations" (think!!) :

Could you find out the optimizations used in above java code?
Best case running time for this algorithm in O(n) and worst case running time is O(n^2).