
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:
- How to create a circular linked list data structure
- How to insert elements to the list so that the insertion creates a sorted data structure.
- 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,