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"));
}
}
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.
ReplyDeleteA 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.
ReplyDeleteThis 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.
ReplyDeleteOf course, if you're just having fun with this, that's good too.
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
ReplyDeletea 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.