Please review my implementation of a Circular Singly Linked List.
public class NodeS {
public int num;
public NodeS next;
public NodeS(int n){
this.num = n;
}
}
public class SinglyCircularList {
private static NodeS head = null;
private static NodeS tail = null;
private static int size = 0;
public static int getSize() {
return size;
}
public static void insert(int n) {
NodeS node = new NodeS(n);
node.next = tail;
if (tail == null) {
tail = node;
} else {
head.next = node;
}
head = node;
size++;
}
public static int delete() {
if (!isEmpty()) {
NodeS deq = tail;
tail = deq.next;
size--;
if (size == 0) {
tail = null;
}
head.next = tail;
return deq.num;
} else {
System.out.println("List Empty !!");
}
return -1;
}
public static boolean isEmpty() {
return size == 0;
}
public void printList() {
NodeS temp = tail;
for (int i = 0; i <= size; i++) {
if (temp != null) {
System.out.print(temp.num);
temp = temp.next;
}
}
System.out.println();
}
/**
* @param args
*/
public static void main(String[] args) {
SinglyCircularList scl = new SinglyCircularList();
scl.insert(1);
scl.insert(2);
scl.insert(3);
scl.insert(4);
scl.insert(5);
scl.insert(6);
scl.insert(7);
scl.printList();
System.out.println("Del->" + scl.delete());
scl.insert(8);
scl.printList();
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
System.out.println("Del->" + scl.delete());
scl.printList();
scl.insert(9);
scl.insert(10);
scl.printList();
}
}
3 Answers 3
I have only a couple of points:
1
You implementation will be able to store only one list throughout your Java program:
SinglyCircularList list1 = new SinglyCircularList();
SinglyCircularList list2 = new SinglyCircularList();
list1.insert(1); // Here list1 = [1], and list2 = [1];
list2.insert(2); // Now list1 = [1, 2], and list2 = [1, 2]
So, basically, you should remove the keyword static from everywhere except the main(String[] args).
2
It would be nicer if your delete method would throw an exception on deleting from an empty list.
3
Instead of printList() you could override the public String toString().
4
private static NodeS head = null;
private static NodeS tail = null;
private static int size = 0;
Whenever declaring class or object fields, references are initialized by default with null, and numeric fields to zero. You can write simply:
private NodeS head;
private NodeS tail;
private int size;
Summa summarum
I had something like that in mind:
import java.util.NoSuchElementException;
public class SinglyCircularList<E> {
private static final class Node<E> {
private final E datum;
private Node<E> next;
Node(final E datum) {
this.datum = datum;
}
E getDatum() {
return datum;
}
Node<E> getNext() {
return next;
}
void setNext(final Node<E> next) {
this.next = next;
}
}
private Node<E> head;
private Node<E> tail;
private int size;
public int size() {
return size;
}
public void insert(final E datum) {
final Node<E> newnode = new Node<>(datum);
if (head == null) {
head = newnode;
tail = newnode;
size = 1;
return;
}
tail.setNext(newnode);
tail = newnode;
size++;
}
public E delete() {
if (isEmpty()) {
throw new NoSuchElementException("Deleting from an empty list.");
}
final E ret = head.getDatum();
if (size == 1) {
head = null;
tail = null;
} else {
head = head.getNext();
tail.setNext(head);
}
size--;
return ret;
}
public boolean isEmpty() {
return size == 0;
}
@Override
public String toString() {
final StringBuilder sb = new StringBuilder("[");
if (size > 0) {
sb.append(head.getDatum());
} else {
return "[]";
}
Node<E> currentNode = head.getNext();
for (int i = 1; i < size; ++i, currentNode = currentNode.getNext()) {
sb.append(", ").append(currentNode.getDatum());
}
return sb.append("]").toString();
}
public static void main(String[] args) {
SinglyCircularList<Integer> scl = new SinglyCircularList<>();
System.out.println("Creating the list:");
for (int i = 1; i <= 8; ++i) {
System.out.println(scl);
scl.insert(i);
}
System.out.println(scl);
System.out.println("Removing from the list:");
while (!scl.isEmpty()) {
scl.delete();
System.out.println(scl);
}
}
}
Hope that helps.
Tail unnecessary
Your tail pointer is always the same as head.next, so you really don't need to track it. All of your functions would simplify a bit. Your insertion function would become:
public static void insert(int n)
{
NodeS node = new NodeS(n);
if (head == null) {
node.next = node;
} else {
node.next = head.next;
head.next = node;
}
head = node;
size++;
}
Your deletion function would become:
public static int delete()
{
if (isEmpty()) {
System.out.println("List Empty !!");
return -1;
}
NodeS deq = head.next;
head.next = (--size == 0) ? null : deq.next;
return deq.num;
}
Lastly, in printList(), you would replace tail with head.next.
Terminology flawed
You have also swapped the head and tail. The first element is the head, the last the tail.
Bug on insert
Your code is bugged. A single item gets printed fine:
public static void main(String[] args) { SinglyCircularList scl = new SinglyCircularList(); scl.insert(1); scl.printList(); // 1 }
But adding more items yields in the first added item being duplicated at the back:
public static void main(String[] args) { SinglyCircularList scl = new SinglyCircularList(); scl.insert(1); scl.insert(2); scl.printList(); // 121 instead of 12 }
Specification not met
And most importantly, your list is not circular. A circular list has the property that it nevers yields null on calling any node.next. But as you can see in your print method, you reach null.
public void printList() { NodeS temp = tail; for (int i = 0; i <= size; i++) { if (temp != null) { System.out.print(temp.num); temp = temp.next; } } System.out.println(); }
Refactored to Circular Linked List
To make the list circular, we only need to track the head. The tail is the last next that is not the head, unless we have a single element.
private NodeS head = null;
private int size = 0;
public NodeS getTail() {
if (isEmpty()) {
return null;
}
NodeS node = head;
do {
node = node.next;
} while (node != head);
return node;
}
Inserting an element at the tail should be called append. Here's a circular implemenation:
public void append(int n) {
NodeS node = new NodeS(n);
if (isEmpty()) {
head = node;
head.next = head;
} else {
NodeS tail = getTail();
tail.next = node;
node.next = head;
}
size++;
}
Removing at the head should be called poll. Here's a circular implementation:
public int poll() {
if (isEmpty()) {
return -1;
}
int num = head.num;
head = head.next;
size--;
if (isEmpty()) {
head = null;
} else {
NodeS tail = getTail();
tail.next = head;
}
return num;
}
And printing the list should be from head to tail and also circular:
public void printList() {
NodeS node = head;
if (node == null) {
System.out.println("Empty List");
return;
}
do {
System.out.print(node.num);
node = node.next;
} while (node != head);
System.out.println();
}
Verification
Here's an updated test:
public static void main(String[] args) {
SinglyCircularList scl = new SinglyCircularList();
scl.printList();
scl.append(1);
scl.printList();
scl.append(2);
scl.printList();
System.out.println(scl.poll() + " removed");
scl.printList();
System.out.println(scl.poll() + " removed");
scl.printList();
}
yielding:
Empty List 1 12 1 removed 2 2 removed Empty List
Explore related questions
See similar questions with these tags.