Sorted Circular Linked List Implementation And Insert Operation

Circular Linked List Data Structure (Unsorted). Source: Wikipedia

Circular Linked List is a kind of Linked List where the elements are accessed sequentially and the last node of the sequence points back to the first node, thus creating a circle. Circular linked lists can be created with simple Java Objects. The only tricky portion is to understand how to link the next element.

The following piece of code demonstrates:

  1. How to create a circular linked list data structure
  2. How to insert elements to the list so that the insertion creates a sorted data structure.
  3. How to handle special scenarios such as:
    • Inserting to an empty list
    • Inserting duplicate elements
    • Inserting element smaller than head (thus forming new head)
    • Inserting element greater than tail (thus forming new tail)
    • Inserting element in between two elements.

package com.icodejava.blog.datastructure;
/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 22, 2014
 * Last Modified On - Feb 22, 2014
 */
public class CircularListInsert {
	public static void main(String args[]) {

		CircularList myList = new CircularList(5);
		myList.printAll();
		
		myList = myList.insert(2);
		myList.printAll();
		
		//test for value smaller than the head.
		myList = myList.insert(1);
		myList.printAll();
		
		myList = myList.insert(3);
		myList.printAll();
		
		//Test for duplicate value
		myList = myList.insert(5);
		myList.printAll();
		
		//test for value greater than he tail.
		myList = myList.insert(6);
		myList.printAll();
	}
}

class CircularList {
	CircularList next;
	int value;

	public CircularList(int value) {
		this.next = this;
		this.value = value;
	}

	/**
	 * @param value
	 *            - new value to be inserted in the list.
	 * @return head node in the circular list
	 * 
	 * This method inserts data in ascending order.
	 */
	public CircularList insert(int value) {

		// if the current list is null.
		if (this == null) {
			return new CircularList(value);
		} else if (this.next == this) {
			// if the current list is head and tail i.e. single element
			this.next = new CircularList(value);
			this.next.next = this;

			// return the smallest node as the head
			if (this.value < value) {
				return this;
			} else {
				return this.next;
			}
		} else if (value < this.value) {

			// if the value is smaller than the head
			// find the tail and append.

			CircularList temp = new CircularList(value);
			temp.next = this;

			CircularList current = this.next;
			while (current.next != this) {
				current = current.next;
			}

			current.next = new CircularList(value);
			current.next.next = this;

			return current.next;

		} else if (value >= this.value) {
			CircularList current = this;

			/**
			 * Keep looking for nodes until all the nodes are smaller than the
			 * value to be inserted.
			 */
			while (current.next != this && current.next.value <= value) {
				current = current.next;
			}

			/**
			 * Once we find the node to be inserted, make a copy of the
			 * current's next value. Insert a node as current's next. and Make
			 * current's next's next value as the previous next which has been
			 * copied as temp
			 */
			CircularList temp = current.next;
			current.next = new CircularList(value);
			current.next.next = temp;
			return this;

		}

		return this;
	}

	public void printAll() {

		if (this == null) {
			return;
		}

		CircularList current = this;
		
		do {

			System.out.print(current.value + ",");
			current = current.next;
		} while (current != this);

		System.out.println();
	}
}


The output of running this program is below. Please note that the elements appear sorted.

5,
2,5,
1,2,5,
1,2,3,5,
1,2,3,5,5,
1,2,3,5,5,6,

Finding Mean Value Of An Integer Array In Java

In Basic Algebra, mean is nothing but just an average of all the points and is calculated as a sum of all the numbers divided by the total count. Don’t be surprised if you are asked to write a java program that can calculate mean value of an array of integers.

The interviewer might be trying to test your coding style, clean coding ability and ability to think about the boundary conditions and user errors. As you can see in the program below, I have written the method to be fail proof from null value or an empty integer.

package com.icodejava.blog.datastructure;

import java.util.Arrays;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * Created On -  Feb 21, 2014
 * Last Modified On - Feb 21, 2014
 * 
 * This class can be used to find the mean value in an array
 */
public class AlgebraMeanFinder {
	
	public static void main(String args []) {
		int [] numbers = {5,5,7,2,3,9,8,9,2,6,7,8,1};
		/**
		 * Finding mean number of a valid integer array
		 */
		findMeanValue(numbers);
		
		/**
		 * Testing for null array
		 */
		findMeanValue(null);
		
		/**
		 * Passing an empty array
		 */
		findMeanValue(new int[] {});
	}

	/**
	 * @param numbers - array of numbers whose mean has to be found
	 * Mean is a simple average value of all numbers.
	 * This method is capable of handling boundary conditions.
	 */
	public static double findMeanValue(int[] numbers) {

		double sum = 0;
		if (numbers == null || numbers.length < 1) {
			System.out.println("\nInvalid Input. Returning 0. Input was:" + Arrays.toString(numbers));
			return sum;
		}

		for (int index = 0; index < numbers.length; index++) {
			sum += numbers[index];
		}

		double mean = (sum / numbers.length);
		System.out.println("\nInput Array is: " + Arrays.toString(numbers));
		System.out.println("Sum:" + sum + " Count:" + numbers.length + " Mean Value is: " + mean);

		return mean;

	}

}

Here is the output of this program.


Input Array is: [5, 5, 7, 2, 3, 9, 8, 9, 2, 6, 7, 8, 1]
Sum:72.0 Count:13 Mean Value is: 5.538461538461538

Invalid Input. Returning 0. Input was:null

Invalid Input. Returning 0. Input was:[]

How to intersect two sets in Java using java.util.Set data structure.

Set Intersection

Set is a collection that holds non-duplicate data. Set itself is an interface and has several implementing classes. Here are some know implementation of Set.

  • AbstractSet
  • ConcurrentSkipListSet
  • CopyOnWriteArraySet
  • EnumSet
  • HashSet
  • JobStateReasons
  • LinkedHashSet
  • TreeSet

In the example below, I have used HashSet to create two different sets. One set contains the name of all the developers of a fictitious team. Another set contains names of all the tech leads for that team. We are intersted to know what all tech leads are also developers. This can be done by doing an intersection of two sets. Intersection of sets can be done by calling retainAll() method as show below.

package com.icodejava.blog.datastructure;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Kushal Paudyal
 * www.icodejava.com
 * 
 * Created on: 02/19/2014
 * Last Modified On: 02/19/2014
 *
 */
public class SetIntersection {
	
	public static void main(String args [] ) {
		/**
		 * Prepare a set of Developers
		 */
		Set<String> developers = new HashSet<String>();
		developers.add("Kushal");
		developers.add("Madan");
		developers.add("Pradip");
		developers.add("Nick");
		
		System.out.println("Developers: " + developers.toString());
		
		/**
		 * Prepare a set of Tech Leads
		 * Note that some of the items added are duplicates.
		 * Set does not allow duplicates which is apparent console print.
		 */
		Set<String> techLeads = new HashSet<String>();
		techLeads.add("Kushal");
		techLeads.add("Kushal"); //set does not allow duplicates
		techLeads.add("Nick");
		techLeads.add("Matthew");
		
		System.out.println("Tech Leads: " + techLeads.toString());
		
		/**
		 * To do set intersection, you can call retainAll() method
		 * and pass another set as parameter.
		 */
		developers.retainAll(techLeads);
		
		System.out.println("Tech Leads who are also developers:" + developers);
		
	}

}

Here is the output of this program:

Developers: [Kushal, Pradip, Madan, Nick]
Tech Leads: [Kushal, Matthew, Nick]
Tech Leads who are also developers:[Kushal, Nick]