Circular LinkedList in Java

Question

I look at my data structures while reading a book, and one of the questions she asks is to create a round Single Linked List without using the "first" and "last" pointers, but rather allow access to it using a single link "current". I'm not sure I understand this question, it always seemed to me that I needed at least one or the last. Here is my implementation, but it has a “first”, not sure how to get around this. Can you comment on how I can customize my code to get rid of the need 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 is 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; } ... } 

Answer 1

If you have a circular linked list, then each node points to the next node in a continuous loop. So there is neither the last nor the first. In this situation, you only need one pointer to the data structure (which calls the "current" call), because you can go through the whole list until you return 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 "next" pointer will point to itself. When you add a second node, each "next" pointer points to another. When you add the third node, each of them will point to the next, and apparently this is sorted out somehow. Each additional node added will be inserted at the appropriate place in the loop.

A good use for such a data structure is a graph that will be repeated every day or every hour. All events can be stored in a circular list, and the "current" pointer always indicates what is planned next time.

Obviously, when searching in such a list, you need to save the link to the first node. This is the only way to find out if you have looked at the entire list, since it does not end with a null "next" pointer.

Edit: As discussed in the (extensive) comment below, the tail pointer would seem to be very useful for insert operations. Here is the original method that I posted that was 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 pointer to the tail would always point to the last node of the list. This will also be node until the first node, since the list is circular. Therefore, when managing pointers, be sure to support (tail.next == current) . Here is the new insertion 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 correctly disable them. To maintain order while adding, use the add method:

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

Here is the code for advance :

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

When used 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 1 as current.

Answer 2

Use Node current, int currentIndex, int size . Let the last Node next point to the first Node of the list (= circular). With the current index, you can move (size - 1) to achieve the previous Node current .

Answer 3

Since the linked list is circular, there will be no first and last item.

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

So, the Node class will have the following link, and the CircularLinkedList will only have the current link.

Hope this helps. Good luck.