需要有关 Java 循环链表的帮助！

Question

是的，这是我的作业项目之一——基于单链表实现循环链​​表。它非常简单，代码很容易阅读。我的所有属性都是公开的，以避免 getters 和 setters 以及私人事务。就本项目而言，public 就足够了。

我在属性字段中初始化了 nItems 计数器（列表中的项目数）和链接头，但稍后我将通过在构造函数内部初始化它来更改它。

我的 step() 方法似乎根本不起作用。我的编译器只是冻结了一会儿，然后什么也没有显示。如果我调用它 4 次，step() 方法应该是这样工作的：

List: 40 80 30 20 10 70 50 
List: 80 30 20 10 70 50 40 
List: 30 20 10 70 50 40 80 
List: 20 10 70 50 40 80 30 

Find() 方法工作正常，只要我们要搜索的值在链接列表内。如果不是，它将永远持续下去。如果这是我的列表，如果您搜索不存在的值，find() 方法会发生什么情况（我一步步调试它）：

70 60 50 40 30 20 10 10 10 10 10 10 10 10...and 10 forever

原因：如果我们正在搜索的键值不存在，它将永远不会从 while 循环中退出，因此永远重复 current = current.next。

while(current.dData != key) {
current = current.next;

我的删除方法说它删除了值 60，正如我想要的那样，但这就是我得到的：

Deleted link with key 60
70 60 40 30 20 10       // lie! it deletes 50 instead of 60

另请查看我的 display() 和 insert() 方法。它们对我来说看起来不错，但我可能是错的，这可能是我在使用 find() 和 delete() 方法时遇到的所有问题的根源。

提前非常感谢！

class Link {
    public int dData;
    public Link next;

    public Link(int dd) {
        dData = dd;
    }

    public void displayLink() {
        System.out.print(dData + " ");
    }
}

class CircList {
    public Link head = null;
    int nItems = 0;

    public boolean isEmpty() {
        return (nItems == 0);
    }
    // INSERT
    public void insert(int key) { 

        Link current = new Link(key);
        if(isEmpty())
            head = current;

        current.next = head;
        head = current;
        nItems++;
    }
    // STEP
    public void step() {
        Link current = head;
        do {
            current = current.next;
        } while(current != head);
    }
    // FIND
    public Link find (int key) {
        Link current = head;
        while(current.dData != key) {
            current = current.next;
        }
        return current;
    }
     // DELETE
    public Link delete(int key) {
    Link current = head;
    while(current.dData != key) {
        current = current.next;
    }
    if(current == head)
        head = head.next;
    else {
        current.next = current.next.next;
        nItems--;
    }
    return current;
}
    // DISPLAY
    public void displayList() {
        Link current = head; // start at beginning
        int counter = nItems;
        while(true) {
            if(counter != 0) {
                current.displayLink();
                current = current.next; // move to next link
                counter--;
            }
            else 
                break;
        }
    }
}

class CircListApp {
    public static void main(String[] args) {
    Link f, d;
    CircList theList = new CircList();


    theList.insert(10);      // insert items
    theList.insert(20);
    theList.insert(30);
    theList.insert(40);
    theList.insert(50);
    theList.insert(60);
    theList.insert(70);

    //System.out.println(theList.nItems + " ");
    theList.displayList();              // display list

    System.out.println("");

    f = theList.find(30);               // find item
    if( f != null)
       System.out.println("Found link with key " + f.dData);
    else
       System.out.println("Can't find link with key 30");

//    theList.step();

//
//    System.out.println("Inserting link with key 80");
//    theList.insert(80);
//    theList.displayList();              // display list
//
    d = theList.delete(60);             // delete item

    if( d != null )
       System.out.println("Deleted link with key " + d.dData);
    else
       System.out.println("Can't delete link with key 60");
    theList.displayList();              // display list
//
//    f = theList.find(99);               // find item
//    if( f != null)
//       System.out.println("Found link with key " + f.dData);
//    else
//       System.out.println("Can't find link with key 99" );
//    theList.displayList();              // display list
//
//    d = theList.delete(13);             // delete item
//    if( d != null )
//       System.out.println("Deleted link with key " + d.dData);
//    else
//       System.out.println("Can't delete link with key 13");
//    theList.displayList();              // display list
//
//    System.out.println("Stepping through list");
//    for(int j=0; j<theList.getSize; j++)
//       {
//       theList.step();
//       theList.displayList();
//       }
//
//    System.out.println("Will delete and step one by one");
//    while(theList.isEmpty() == false)
//       {
//       theList.delete();
//       theList.step();
//       theList.displayList();
//       }
    }  // end main()

}

Answer 1

到你的“步骤”方法：
您创建一个名为 current 的本地引用，它最初指向 head。 之后

current = current.next

在它引用 head 的后继者 。在下一步中，它引用它的后继者，依此类推。但这是本地引用，因此您无需更改列表中的任何内容。

正如我从您想要的输出中推断出的那样，您所要做的就像

if( head != null && head.next != null )
    head = head.next

下一步一样简单：对于您的查找方法：
好吧，从你的循环条件来看，很明显，如果键不在列表中，它将永远运行，因为这是你唯一的中断条件。您应该考虑一种机制，使其在查看完列表中的每个项目后停止。提示：看看您在您的 step() 方法版本中做了什么。

对于您的删除方法：
第一部分（部分）没问题（它与您的查找方法具有相同的无限循环问题）。
您要做的就是迭代列表，直到当前的数据等于键。没关系。

但现在， current 是对要删除的元素的引用。但是你所做的是将 current.next 设置为 current.next.next，这意味着你要删除 current 的后继者，而不是 current 本身！在搜索键的循环中，您必须跟踪前驱，以便可以将前驱.next 更改为 current.next，这才是您真正想要做的。

然后，当然，您必须检查它是否是您要删除的头，如果是这种情况，则必须将其设置为它的前驱或后继。

最后，我发现您的 insert() 方法有问题！我不明白这如何产生一个循环链表，因为你让新插入的元素指向头部并使其成为新的头部，但没有任何东西指向它。所以你只创建一个单链表？您在 head“之前”插入一个新项目（ current.next = head ），但是您还应该让 head 的前一个项目现在指向新项目 current！