3

I need to implement a circular single-linked list data structure. What I'm having trouble understanding is when and where do I have to state that the final node of the list must point to the first node. I have the following empty constructor to build the list:

public class SList<E> implements IList<E> {

    protected SNode<E> firstNode = null;

    public SList() {
        firstNode = null;
    }

So basically each list starts with a null object that points to null again, signifying the end of the list:

public class SNode<E> {

E elem;
public SNode<E> nextNode = null;
...

What I am unaware of however is how to make it so that when the list contains at least one node, that node will point to the first node of the list.

For example, taking a look at this addLast() method that I implemented for my regular linked list:

    public void addLast(E newElem) {
        SNode<E> newNode= new SNode<E>(newElem);
        SNode<E> nodeTraveler = firstNode;
        while (nodeTraveler.nextNode != null) {
            nodeTraveler= nodeTraveler.nextNode;
        }
        nodeTraveler.nextNode = newNode;
     }

I would have to change it into something like:

    public void addLast(E newElem) {
    SNode<E> nodeTraveler = firstNode;
    SNode<E> newNode = new SNode<E>(newElem);
    while (nodeTraveler.nextNode != firstNode){
        nodeTraveler = nodeTraveler.nextNode;
    }
    nodeTraveler.nextNode = newNode;
    newNode.nextNode = firstNode;
}

nodeTraveler would stop traversing the list once it's next node matched that of the firstNode (meaning it's at the last position), and then it would change its nextNode to the one we want to add, newNode, and point newNode to the firstNode.

Theoretically, that should work, but since I'm never actually pointing the last element to the first one prior to this method (which is my main question, how to point the last element to the first one by default), I get a nullPointer exception when the code reaches the while iteration.

Any help would be appreciated, thanks.

VDG
  • 83
  • 1
  • 8
  • Check for the null pointer. That's how you know you're at the end of the tail. – Robert Harvey Feb 22 '15 at 16:37
  • Possibly related question on Java ring buffers at http://stackoverflow.com/questions/7266042/java-ring-buffer. Unless you are doing this for an exercise, using the Apache Commons CircularFifoBuffer may be worth considering. – paisanco Feb 22 '15 at 16:39
  • @RobertHarvey Yeah I can check for the null pointer, but that will only work for the first call of the method, because after that, the final element will point to the first one. I guess that the point of using a circular list is to not have a null pointer. – VDG Feb 22 '15 at 17:01
  • @paisanco yeah it's for an exercise, to get the whole feel of how lists work. Anyways, thanks for the link, will check it out! – VDG Feb 22 '15 at 17:02
  • You can point the last element to the first, if you like, but I would maintain a head and a tail pointer instead, with logic to wraparound. See http://en.wikipedia.org/wiki/Circular_buffer – Robert Harvey Feb 22 '15 at 17:27

1 Answers1

1

The only special case is when firstNode == null, which is the initial case.

After that, the first add will give a node whose next element is self:

public void addLast(E newElem) {
    SNode<E> newNode = new SNode<E>(newElem);
    if(firstNode == null) {
        firstNode = newNode;
    } else {
        SNode<E> traveler = firstNode;
        for( ; traveler.nextNode != firstNode ; traveler = traveler.nextNode) {}
        traveler.nextNode = newNode;
    }
    newNode.nextNode = firstNode;
}
Jean Logeart
  • 52,687
  • 11
  • 83
  • 118
  • I see, thanks for that! So it's safe to say there's not default way of letting Java know that my last element points to the first one, I just have to modify all my methods in order to do that? – VDG Feb 22 '15 at 16:52