Alex Rivera | Logout

Circular LinkedList implementation in Java

Asked 2012-09-09T11:58:04.990
12

This is an assignment. I have to create a circular linked list and remove every third number in the list. When my program reaches the end of the list it should go back to the head and continue the process until only one number remains.

I've searched online and some other reference books but couldn't solve my problem. Most of the references that I've found say things such as:

Beside the fact that circular lists have no end, they are quite the same as regular lists

or (taken from my textbook):

A singly-linked list is circularly linked if the successor of the last node is the first

But these don't tell how to do it. I've also tried using some code I found on this site, but that did not clear anything up.

I can get as far as creating a list (I don't know if it's a circular linked list) and displaying it, but the order of the elements is strange:

  • if the list has 6 numbers, the list will be 1,6,5,4,3,2.
  • if the list has 8 numbers, the list will be 1,8,7,6,5,4,3,2.

Without getting a correct list, I can do the deletion properly. What is wrong with the following code:

public class LastNumberDemo {
    public static void main(String[] args) {
        LastNumberNode ll=new LastNumberNode();
        System.out.println("how long is the list: ");
        Scanner keyboard = new Scanner(System.in);
        int input = keyboard.nextInt();

        if(input<=0) {
            System.out.println("no number to creat list");
        }
        if(input==1) {
            System.out.println("The Last number is 1.");
        }
        else {
            String[] n=new String[input];
            for(int index=0; index<n.length; index++)
                n[index]=Integer.toString(index+1);
            for(String e:n)
                ll.add(e);
            System.out.print("The list contains: \n");
            ll.print();
java linked-list circular-list
Edit
Report

1 Answer

7

When you add a new Node to your list, you add the new Node into the second position (first.next points to your newly added node), but this newly added node has first as its next node, leaving the rest of the list unreferenced (And thus garbage-collected and destroyed). With your add method as it is, it's impossible for your list to contain anything other than 0, 1 or 2 Nodes. It's a bit odd to add new Node into the middle of the list; either add it to the front (newnode.next = first; first = newnode; last.next = first;), or keep a reference to the back of the list (as others have suggested), and add it there.

Personally, I'd restructure the LastNumberNode class so that it has the following methods for manipulating the linkedlist:

  • private void addNode(Node node)
  • private void removeNode(Node node)
  • private Node findNode(Node nextNode)

If you maintain a reference to the last node in the list then your addNode(Node node) method can be something like the following:

if(isEmpty()) {
    first = node;
    last = node;
}
else {
    Node tail = last;
    tail.next = node;
    node.next = first;
    last = node;
}

removeNode(Node node) is based around the following:

Node prevNode = findNode(node);

if(node == first) {
    first = node.next;
    last.next = first;
}
else if(node == last) {
    prevNode.next = first;
    last = prevNode;
}
else {
    prevNode.next = node.next;
}

If I were to implement of this I'd probably do the reduction of the list down to a single Node using this sort of approach:

public String reduceList() {
    Node curNode = first;
    while(first != last) {
        removeNode(curNode.getNext().getNext());
        curNode = cu
answered 2012-09-11T15:35:14.510

Your Answer