Monday, July 28, 2008

Cricular Linked List in Java

Had to implement a circular linked list recently. Here's my take, suggestions are welcome. The list can be parameterized for any type which has a meaningful equals method defined. The main method shows a sample usage of the Circular linked list with the String type. Only add, remove and size method are implemented.

There's more ...
package algo;

import java.util.NoSuchElementException;

public class CircularLinkedList<E> {
 private Entry<E> head;

 // Last element of the list. tail.next = head
 private Entry<E> tail;

 private int size = 0;

 /**
  * Class to hold the individual elements.
  @param <E>
  */
 private static class Entry<E> {
  E element;

  Entry<E> next;

  Entry(E element, Entry<E> next) {
   this.element = element;
   this.next = next;
  }

  Entry(E element) {
   this.element = element;
  }
 }

 public CircularLinkedList() {
  head = null;
 }

 /**
  * Remove obj from the circular linked list and return the removed object
  @param obj
  @return
  */
 public E remove(E obj) {
  if (head == null || tail == null)
   throw new NoSuchElementException();
  Entry<E> current = head, temp = head, found = null;
  if (obj.equals(head.element)) {
   if (head.next == head) {
    found = head;
    head = null;
    tail = null;
    size--;
    return found.element;
   else {
    found = head;
    temp = tail;
   }
  else {
   current = head.next;
   while (current != head) {
    if (current.element.equals(obj)) {
     found = current;
     break;
    }
    temp = current;
    current = current.next;
   }
  }
  if (found == null) {
   throw new NoSuchElementException(obj.toString());
  }
  E result = found.element;
  temp.next = found.next;
  found.next = null;
  found.element = null;
  size--;
  return result;
 }

 /**
  * Add obj to the circular linked list.
  @param obj
  */
 public void add(E obj) {
  Entry e = new Entry(obj);
  if (head == null) {
   size++;
   head = e;
   head.next = head;
   tail = head;
   return;
  }
  size++;
  e.next = head;
  head = e;
  tail.next = head;
 }

 /**
  * Size of the list.
  @return
  */
 public int size() {
  return size;
 }

 public static void main(String[] args) {
  CircularLinkedList<String> list = new CircularLinkedList<String>();
  list.add("One");
  list.add("Two");
  list.add("Three");
  list.add("Four");

  System.out.println(list.remove("Three"));
  System.out.println(list.remove("Two"));
  System.out.println(list.remove("One"));
  System.out.println(list.remove("Four"));
  System.out.println(list.remove("Four"));

 }
}

4 comments:

  1. I don't quite see what utility this gives you over a LinkedList. The only thing, or at least most obvious to me, reason to have a circular list would be to start at a paricular node and then iterate from that node until you get to node n-1. I'd do that by extending LinkedList and adding a method to give you an Iterator (or ListIterator) starting from a particular element.

    ReplyDelete
  2. A circular linked list may not add much over a linear linked list. However it is useful to describe circular structures which one might encounter when implementing certain games and schedulers etc. All the applications where a circular linked list is used can be implemented with a linear linked list, but using the former will make the job a lot simpler.

    ReplyDelete
  3. This just looks to me like a solution in search of a problem. Your example just has insert and remove methods. The insert is O(1) and remove O(n), no different than a LinkedList. What I'm asking is what functionality does this structure give you above and beyond LinkedList and why is a circular list a good implementation of it. If your need is to have a list structure where you can set the head to an arbitrary point and then iterate from there then this is a good way. I think it's a better design approach is to figure out what functionality and efficiency requirements I need, and then come up with the implementation.

    Of course, if you're just having fun with this, that's good too.

    ReplyDelete
  4. This is not a complete implementation. However insert and delete are the most used functionalities of any data structure, and so I just implemented them. Any further functionality must depend, as you said, on the requirements. A circular list is not required for most problems, but some problems, as I mentioned, certain game implementations (card games, Counting-out game etc.) can use
    a circular implementation.
    In comparison with the linear list, a circular list is a linear list where the tail contains a pointer to the head. And as such all the methods are similar except for when to end iteration over the list.

    ReplyDelete

Popular Posts