CODEWITHSUNDEEP
javadata-structureslinked-list
sam2015
sam2015

Reputation: 113

Circular LinkedList in Java

I am brushing up on my data structures by reading a book and one of the questions it asks is to build a circular Single Linked List by not using "first" & "last" pointers, but rather allow access to it by using one reference "current". I am not sure I understand the question, I always thought I needed at least either first or last. Here is my implementation but it has "first", not sure how to get around it. Can you please comment on how I can adjust my code to eliminate reliance on first?

class Link {
    public int iData;              
    public Link next;              

    public Link(int id) { // constructor
        iData = id;                         
    }                          

    public void displayLink() {
        System.out.print(iData + " ");
    }
}  // end class Link

Then here's the list itself:

public class CircularLinkedList {
    private Link first;
    private Link current;    

    public Link getCurrent(){
        return current;
    }

    public void setCurrent(int data){

    }

    public void advance(){
        current = current.next;
    }

    public void insert(int data) {
        Link newLink = new Link(data);
        if (first == null) { 
            first = current = newLink;
        } else {
            current.next = newLink;
        }
        current = newLink;
        newLink.next = first;
    }
    ...
}

Upvotes: 7

Views: 23390

Answers (3)

Erick Robertson
Erick Robertson

Reputation: 33082

If you have a circular linked list, then each node points to the next node in a continuous loop. So there is no last and no first. In this situation, you only need one pointer into the data structure (which the question is calling "current") because you can walk the whole list until you get back to where you started.

One node might look like this:

public class ListNode<T> {
    private T element;
    private ListNode<T> next;
}

So in this environment, when you add your first node to the list, it's "next" pointer will point to itself. When you add the second node, each "next" pointer will point to the other. When you add the third node, then they will each point to the next one, and presumably this is being ordered in some way. Each additional node added will be inserted into the appropriate place in the loop.

A good usage for a data structure like this would be a schedule that gets repeated every day or every hour. All of the events can be stored in a circular list and the "current" pointer always points to whichever is scheduled next.

Obviously, when searching a list like this, you need to keep a reference to the first node. This is the only way you can know if you've searched the whole list since it doesn't end with a null "next" pointer.

Edit: As discussed in the (extensive) comments below, a "tail" pointer would seem to be a very good idea here for insert operations. Here is the original method that I posted, which has been renamed insertAfter:

public void insertAfter(int data) {
    Link newLink = new Link(data);
    if (current == null) { 
        newLink.next = newLink;
        current = newLink;
    } else {
        newLink.next = current.next;
        current.next = newLink;
    }
}

A tail pointer would always point to the last node of the list. This would also be the node before the first node, since the list is circular. So be sure to maintain (tail.next == current) when manipulating the pointers. Here is the new insert method:

public void insert(int data) {
    Link newLink = new Link(data);
    if (current == null) { 
        current = newLink;
        tail = newLink;
        newLink.next = newLink; // tail.next = current!
    } else {
        tail.next = newLink; // tail.next = current!
        newLink.next = current;
        current = newLink; // tail is unchanged, newLink is current
    }
}

Inserting values should rightly put them out of order. To maintain order when adding, an add method should be used:

public void add(int data) {
    this.insert(data);
    this.advance();
}

Here's the code for advance:

public void advance() {
    if (current != null) {
        tail = current;
        current = tail.next; // tail.next = current!
    }
}

When used like this to create lists...

list1.add(1);
list1.add(2);
list1.add(3);
list2.insert(3);
list2.insert(2);
list2.insert(1);

...both lists are ordered 1-2-3 with the 1 as current.

Upvotes: 8

Tanmay Patil
Tanmay Patil

Reputation: 7057

Since the linked list is circular, there would be no first and last element.

You can traverse entire list starting from any node (current in this context).

So Node class would only have a next reference, and CircularLinkedList will have only current reference.

Hope this helps.
Good luck.

Upvotes: 0

Joop Eggen
Joop Eggen

Reputation: 109613

Use Node current, int currentIndex, int size. Have the last Node's next point to the first node of the list (= circular). With the current index you can walk (size - 1) elements to reach the previous node of current.

Upvotes: 0

Related Questions