Circular LinkedList implementation in Java

问题:

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();
            System.out.print("\nThe last number is: ");
            ll.remove();
            ll.print();
        }
    }
}

---

//The circular linked list class
class LastNumberNode{
    private class Node{
        String value;  
        Node next;     

        Node(String val, Node n){
            value = val;
            next = n;
        }

        Node(String val){
            value=val;
            next=null;
        }
    } //This brace was missing - Edd

    private Node first;

    public LastNumberNode(){
      first = null;
    }

    public boolean isEmpty(){        
       return first == null;
    }

    public int size(){
        int count = 0;
        Node p = first.next;   
        while (p != first){
            count ++;
            p = p.next;
        }
        return count;
    }

    public void add(String e) {
        Node p=new Node(e);
        if(first==null){
            first=p;
            first.next=first;
        }
        else{
            first.next=new Node(e,first.next);
        }
    }

    public void remove(){
        while(size()>0){
            Node target=first.next.next;   
            Node temp=first;               
            target=target.next;          
            last.next=temp;
            first=target;
        }
    }

    public void print(){
        Node ref=first;
        for(int index=-1; index<size();index++)
            System.out.print(ref.value+" ");
        ref=ref.next;
    }
} //Extra brace removed - Edd

回答1:

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 = curNode.getNext().getNext();
    }

    return first.getValue();
}

As a final point, I wouldn't bother filling an array with sequential numbers and then walking it to add the elements to your list. I'd just go straight for something like the following:

for(int i = 1; i <= input; i++) {
    linkedlist.add(new Integer(i).toString());
}

回答2:

Your add method inserts the elements directly after first if first is already set:

first.next = new Node(e, first.next);

This leads to the observed behaviour.

You need to keep track of the last element of the list and add the new element as last.next if you want to append the new element at the end of the list. One way to do this is to simply save a reference to the last element in a member variable of the list class, another would be to traverse the list until you find the node linking to first which would be the last node.