How to implement circular linked list in java?

Question

I read a book about "Data structures and algorithms" in which there is assignment which asks me to implement a circular linked list. This is a learning exercise and my code may not be of a very high standard.

The main idea behind my implementation of a circular linked list is to have a pointer which points to the last element and each time I add new item, the field 'next' of the last item will be refreshed to point to the newly added item.

The insertion method works fine, I can add item without any problems, but for some reason I can't delete items from the list.

Here is the code for 'Link' or 'Node':

public class Link {
  public long data;
  public Link next;

  public Link(long val) {
    data = val;
    next = null;
  }

  public void displayLink() {
    System.out.print(data + " ");
  }

}  // end class

This is the code for class which carries out the work, and the bug is obviously somewhere here:

public class CircularList {
Link first;
Link last;

public CircularList() {
     first = null;
     last = null;
}

public Link find(long key) {
    Link current = first;
    while(current.data != key) {
        current = current.next;
    }
    return current;
} // end find

public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    return temp;
}  // end delete

public boolean isEmpty() { return (first == null); }

public void insert(long val) {
    Link newLink = new Link(val);

    if(isEmpty())
        last = newLink;

    newLink.next = first;
    first = newLink;
    last.next = first;
} // end insert

public void displayAmount(int n) {
    Link current = first;
    while(n>0) {
        current.displayLink();
        current = current.next;
        n--;
    }
    System.out.println("");
} // end displayAmount

}  // end class

And the main app code:

public class App {
public static void main(String[] args) {
    CircularList cl = new CircularList();

    cl.insert(10);
    cl.insert(20);
    cl.insert(30);
    cl.insert(40);

    cl.displayAmount(6);

    cl.delete();

    cl.displayAmount(6);
}
}  // end class

The display amount looks kind of silly, I just tried to avoid infinite loop and made something simple that just works.

Answer 1

Add last.next = first before return temp in your delete() function:

public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    if(last != null)
        last.next = first
    return temp;
} 

Updated:

I cannot find a scenario which satisfy first.next == null, and we should take into consideration calling delete() on an empty list.

public Link delete() {
    Link temp = first;
    if(first == null){
        ;  // or you can throw some exception as a warning
    }
    else if(first==last){  // only one element
        first = null; // reset to initial state
        last = null;
    }
    else{
        first = first.next;
        last.next = first;
    }
    return temp;
} 

Answer 2

Your delete() method doesn't handle the circularity of the list. The last element points to the first element; that also needs updating when the first element is deleted.

In other words, you need to set last.next to point to the new first rather than the old first.

The other issue you have is that if you delete the final element (so that it's now empty), then you also need to set last to null.

public Link delete() {
    if (first.next == null) {
        first = null;
        last = null;
    }
    Link temp = first;
    first = first.next;
    last.next = first;
    return temp;
}