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.

Your linked list node is missing a reference to the previous node, making removal impossible. You want to have the last element refer to the first as well as the first to the last, meaning both need a next and previous. With these, you can take any element, get the previous and the next on the current element and connect previous with next, effectively cutting out the element to delete. — G_V
– G_V, Commented Jan 4, 2015 at 16:45
@G_V the delete() method as it stands always (tries to) delete the first element, which is OK because its predecessor is last. You'd need it to be doubly linked if you wanted to delete arbitrary elements, but if you only ever delete first, you don't need that. — chiastic-security
– chiastic-security, Commented Jan 4, 2015 at 16:46

Paul Lo · Accepted Answer · 2015-01-04 18:14:19Z

5

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;
}

edited Jan 4, 2015 at 18:14

answered Jan 4, 2015 at 16:46

Paul Lo

6,1466 gold badges33 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

chiastic-security Over a year ago

You don't need your null check: if first isn't null then last can't be null either (because if you've just got one element then first == last).

Paul Lo Over a year ago

@chiastic-security As long as first.next == null might be true, I think we need that null check as we set last to null. However, I noticed that might never happen, therefore I updated my answer and added defensive code for another case which we delete() on an empty list.

chiastic-security · Accepted Answer · 2015-01-04 16:48:33Z

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;
}

edited Jan 4, 2015 at 16:48

answered Jan 4, 2015 at 16:42

chiastic-security

20.5k4 gold badges43 silver badges70 bronze badges

1 Comment

SuperManEver Over a year ago

you variant is also working. And at least for me it much clear convey the idea.

Collectives™ on Stack Overflow

How to implement circular linked list in java?

2 Answers 2

2 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related