如何在java中实现循环链​​表?

我读了一本关于“数据结构和算法”的书,其中有一些任务要求我实现循环链​​表。 这是一个学习练习,我的代码可能没有很高的标准。

我实现循环链​​表的主要思想是有一个指向最后一个元素的指针,每次添加新项时,最后一个项的字段“next”将刷新为指向新添加的项目。

插入方法工作正常,我可以添加项目没有任何问题,但由于某种原因我无法从列表中删除项目。

以下是“链接”或“节点”的代码:

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 

这是执行工作的类的代码,错误显然在这里:

 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 

主应用程序代码:

 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 

显示量看起来有点傻,我只是试图避免无限循环并使一些简单的东西正常工作。

在delete()函数中return temp之前添加last.next = first

 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()。

 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; } 

您的delete()方法不处理列表的循环。 最后一个元素指向第一个元素; 删除第一个元素时也需要更新。

换句话说,您需要将last.next设置为指向新的first而不是旧的first

你遇到的另一个问题是,如果你删除了最后一个元素(现在它是空的),那么你还需要将last设置为null

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