如何在Java中实现循环链​​表？ [英] How to implement circular linked list in java?

问题描述

我读了一本关于数据结构和算法的书，其中有一项作业要求我实现一个循环链表。这是一项学习活动，我的代码可能不是很高的标准。

I read a book about "Data structures and algorithms" in which there is assignment which asks me to implement a circular linked list. This is a learning exercise and my code may not be of a very high standard.

实现循环链​​接列表的主要思想是要有一个指向到最后一个元素，并且每次添加新项目时，都会刷新最后一个项目的字段下一个以指向新添加的项目。

The main idea behind my implementation of a circular linked list is to have a pointer which points to the last element and each time I add new item, the field 'next' of the last item will be refreshed to point to the newly added item.

插入方法工作正常，我可以毫无问题地添加项目，但是由于某种原因我无法从列表中删除项目。

The insertion method works fine, I can add item without any problems, but for some reason I can't delete items from the list.

这是链接或节点：

public class Link {
  public long data;
  public Link next;

  public Link(long val) {
    data = val;
    next = null;
  }

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

}  // end class

进行工作的类的代码，并且该错误显然在这里：

This is the code for class which carries out the work, and the bug is obviously somewhere here:

public class CircularList {
Link first;
Link last;

public CircularList() {
     first = null;
     last = null;
}

public Link find(long key) {
    Link current = first;
    while(current.data != key) {
        current = current.next;
    }
    return current;
} // end find

public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    return temp;
}  // end delete

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

public void insert(long val) {
    Link newLink = new Link(val);

    if(isEmpty())
        last = newLink;

    newLink.next = first;
    first = newLink;
    last.next = first;
} // end insert

public void displayAmount(int n) {
    Link current = first;
    while(n>0) {
        current.displayLink();
        current = current.next;
        n--;
    }
    System.out.println("");
} // end displayAmount

}  // end class

以及主要应用程序代码：

And the main app code:

public class App {
public static void main(String[] args) {
    CircularList cl = new CircularList();

    cl.insert(10);
    cl.insert(20);
    cl.insert(30);
    cl.insert(40);

    cl.displayAmount(6);

    cl.delete();

    cl.displayAmount(6);
}
}  // end class

显示量看起来很傻，我只是想避免无限循环，并简化了一些可行的方法。

The display amount looks kind of silly, I just tried to avoid infinite loop and made something simple that just works.

推荐答案

最后添加个。 next = first 在delete（）函数中返回温度之前：

Add last.next = first before return temp in your delete() function:

public Link delete() {
    if(first.next == null) 
        last = null;
    Link temp = first;
    first = first.next;
    if(last != null)
        last.next = first
    return temp;
} 

已更新：

我找不到满足 first.next == null 的方案，我们应该考虑在空列表上调用delete（）。

I cannot find a scenario which satisfy first.next == null, and we should take into consideration calling delete() on an empty list.

public Link delete() {
    Link temp = first;
    if(first == null){
        ;  // or you can throw some exception as a warning
    }
    else if(first==last){  // only one element
        first = null; // reset to initial state
        last = null;
    }
    else{
        first = first.next;
        last.next = first;
    }
    return temp;
} 

这篇关于如何在Java中实现循环链​​表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！