Java 中的循环 LinkedList 实现 [英] 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:
- 如果列表有 6 个数字，则列表将是 1、6、5、4、3、2.
- 如果列表有 8 个数字，则列表将为 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:
");
ll.print();
System.out.print("
The 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
推荐答案
当您向列表中添加新的 Node 时，您将新的 Node 添加到第二个位置(first.next 指向您新添加的节点)，但是这个新添加的节点将 first 作为它的下一个节点，而未引用列表的其余部分(因此垃圾 -收集和销毁).使用您的 add 方法，您的列表不可能包含 0、1 或 2 个 Node 以外的任何内容.将新的 Node 添加到列表中间有点奇怪；要么将它添加到前面(newnode.next = first; first = newnode; last.next = first;)，或者保留对列表后面的引用(正如其他人所建议的那样)，并且添加到那里.
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.
就个人而言，我会重构 LastNumberNode 类，使其具有以下操作链表的方法:
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)私有节点 findNode(Node nextNode)
如果您维护对列表中最后一个节点的引用，则您的 addNode(Node node) 方法可能如下所示:
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) 基于以下内容:
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;
}
如果我要实现这一点，我可能会使用这种方法将列表减少到单个 Node:
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());
}
这篇关于Java 中的循环 LinkedList 实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
