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,
  1. Implementing a Simple LIFO Stack in Java using LinkedList
  2. Implementing a Simple FIFO Queue in Java Using Linked List
  3. In Place Matrix (2D Array) Clockwise and Counterclockwise Rotation – Java Implementation
  4. Matrix (2D Array) Clockwise and Counterclockwise Rotation with Extra Buffer – Java Implementation
  5. Array Max Integer Finder (With Big O Analysis)
  6. A Basic Implementation of Binary Tree in Java
  7. A Basic Implementation of Generic Tree in Java
  8. Basic example of implementing Singly Linked List in Java
  9. How to Add and Remove nodes in an unsorted Linked List
  10. Rotating a two dimensional integer array In-Place and using extra memory
  11. How to reverse a Singly Linked List iteratively and recursively
  12. Sorted Circular Linked List Implementation And Insert Operation
  13. Finding Mean Value Of An Integer Array In Java
  14. How to intersect two sets in Java using java.util.Set data structure.
  15. Bubble Sorting An Integer Array In Ascending and Descending Order
  16. How to split strings and separate the words with spaces
  17. How to easily sort characters in a String?
Tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *