这个链表是循环执行的吗？

Question

这是我在这里的第一篇帖子！我是一名CS学生，所以我还在学习。如果你有任何建议或建议（哈哈…！）在构建我的代码或一般实践方面，我非常感谢任何反馈！

我被指派用java重新实现Queue类(https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html)使用循环链表。我的意见附在这个问题上。我在作业中得到了零分——根据评分员的说法，我对链表的实现不是循环的。

我不想表现得自负或过于自信，因为我显然在某种程度上不知道我在做什么，但在第 155 行到 161 行中，我注释掉了一个打印出列表中下一个链接的数据的部分。据我所知，列表中的节点是循环链接的，因为即使在打印了最后一个节点的数据之后，它们也会继续打印第一个节点的数据。

例如（我知道这段代码看起来很乱，我只是为了调试而这样设置的——这实际上是我注释了我的实际代码的部分）：

System.out.println("next: " + cursor.getNext().getData());
System.out.println("next.next: " + cursor.getNext().getNext().getData());
System.out.println("next.next.next: " + cursor.getNext().getNext().getNext().getData());
System.out.println("next.next.next.next: " + cursor.getNext().getNext().getNext().getNext().getData());

印刷品：

下一个:45

下一页下一页:71

下一个。下一个。下一个：3

next.next.next.next： 45

当有三个节点包含在列表中输入的数据时。

此外，从第30行开始的add方法将列表尾部之后的下一个节点分配给head（而不是空值），因此列表应该循环，对吗？这是一个片段：

Node<T> node = new Node<T>(element);
if(isEmpty() == true){
    head = node;
}else{tail.setNext(node);}

tail = node;
node.setNext(head);

我想我的问题是:这不是以什么方式循环实施的？

同样，我完全有可能不知道我在说什么，但据我所知，这实际上是一个循环链表。

提前感谢您的帮助！

完整代码（三个类分别为CircularLinkedQueue、Node和Circular LinkedListTest）：

CircularLinkedQueue:

import java.util.NoSuchElementException;

public class CircularLinkedQueue<T> {
int count = 0;
private Node<T> head = null;
private Node<T> tail = head;

public CircularLinkedQueue(){
    Node<T> node = new Node<T>();
    tail = node;
}

/* Inserts the specified element into this queue if it is
 * possible to do so immediately without violating capacity
 * restrictions, returning true upon success and throwing
 * an IllegalStateException if no space is currently available.
 */
public boolean add(T element){
    try{
        Node<T> node = new Node<T>(element);
        if(isEmpty() == true){
            head = node;
        }else{tail.setNext(node);}
        
        tail = node;
        node.setNext(head);
        count++;
        return true;
    }catch(Exception all){
        Node<T> node = new Node<T>(element);
        if(element == null){throw new NullPointerException("Specified 
element is null.");}
        else if(element.getClass().getName() != 
node.getData().getClass().getName()){
            throw new ClassCastException
            ("Class of specified element prevents it from being added.");
        }
        return false;
    }
}
/* Retrieves, but does not remove, the head of this queue.
 * This method differs from peek only in that it throws
 * an exception if this queue is empty.
 */
public T element(){
    Node<T> cursor;
    if(isEmpty() != true){
        cursor = head;
    }else{throw new NoSuchElementException("No such element exists.");}
    return cursor.getData();
    
}
/*
Inserts the specified element into this queue if it is possible
to do so immediately without violating capacity restrictions.
When using a capacity-restricted queue, this method is generally
preferable to add(E), which can fail to insert an element only
by throwing an exception.
/*
public boolean offer(T element){
    try{
        Node<T> node = new Node<T>(element);
        if(isEmpty() == true){
            head = node;
        }else{tail.setNext(node);}
        
        tail = node;
        node.setNext(head);
        count++;
        return true;
    }catch(Exception all){return false;}
}

/* Retrieves, but does not remove, the head of this queue,
 * or returns null if this queue is empty.
 */
public T peek(){
    Node<T> cursor;
    //set cursor to head if not empty, create new null node otherwise
    if(isEmpty() != true){
        cursor = head;
    }else{cursor = new Node<T>(); cursor.setData(null);}
    //return null if no data is stored
    return cursor.getData();
}
/* Retrieves and removes the head of this queue,
 * or returns null if this queue is empty.
 */
public T poll(){
    Node<T> cursor = head;
    if(isEmpty() != true){
        if(count <= 1){
            head.setNext(null);
            head = head.getNext();
            tail = head;
            count--;
            return null;
        }else{
            //cursor = head;
            head = head.getNext();
            tail.setNext(head);
        }
    }else{cursor = new Node<T>(); cursor.setData(null);}
    count--;
    return cursor.getData();
}
/* Retrieves and removes the head of this queue.
 * This method differs from poll only in that it
 * throws an exception if this queue is empty.
 */
public T remove(){
    Node<T> cursor;
    if(isEmpty() != true){
        if(count <= 1){
            head.setNext(null);
            head = head.getNext();
            tail = head;
            count--;
            return null;
        }else{
            cursor = head;
            head = head.getNext();
            tail.setNext(head);
        }
    }
    else{throw new NoSuchElementException("No such element exists.");}
    count--;
    return cursor.getData();
}
//returns whether the list is empty or not
public boolean isEmpty(){return head == null;}

/* This method puts all the values of the circular linked list
 * into a String type for output purposes.
 */
@Override
public String toString(){
    int cycles = count;
    String s = "";
    Node<T> cursor = head;
    while(cycles > 0){
        s = s + cursor.getData() + "\n";
        cursor = cursor.getNext();
        cycles--;
    }
    /*
     * these lines print as expected & exist only for debugging purposes
    System.out.println("next: " + cursor.getNext().getData());
    System.out.println("next.next: " + 
cursor.getNext().getNext().getData());
    System.out.println("next.next.next: " + 
cursor.getNext().getNext().getNext().getData());
    System.out.println("next.next.next.next: " + 
cursor.getNext().getNext().getNext().getNext().getData());
    */
    return s;
}
//returns the length of the list
public int getCount(){return count;}
}

节点:

public class Node<T> {
T data;
Node<T> next;

public Node(){data = null;}

public Node(T data){this.data = data;}

public void setData(T data){this.data = data;}

public void setNext(Node<T> nextNode){next = nextNode;}

public T getData(){return data;}

public Node<T> getNext(){return next;}
}

循环链表测试：

public class CircularLinkedListTest<T>{

public static void main(String[] args) {
    /* demonstrates creation of new circular linked lists/linked queues,
     * uses two different data types
     */
    CircularLinkedQueue<Integer> c1 = new CircularLinkedQueue<Integer>();
    CircularLinkedQueue<String> c2 = new CircularLinkedQueue<String>();
    //demonstrate add and offer methods detailed in Queue interface
    c1.add(3);
    c1.offer(45);
    c1.offer(71);
    c2.add("hello");
    c2.offer("good evening");
    c2.offer("how do you do");
    //demonstrates a toString method and prints after data has been added
    System.out.println("c1.toString(): \n" + c1.toString());
    System.out.println("c2.toString(): \n" + c2.toString());
    /* demonstrates the remove and poll methods, prints out the values in 
the list,
     * poll method returns null when implemented, isEmpty method shows the
     * nodes are truly being removed from the list after poll or remove
methods are
     * called
     */
    c1.remove();
    c2.remove();
    c2.remove();
    System.out.println("c1.toString(): \n" + c1.toString());
    System.out.println("c2.poll(): " + c2.poll());
    System.out.println("c2.getCount(): " + c2.getCount());
    System.out.println("c2.isEmpty(): " + c2.isEmpty());
    System.out.println("");
    //re-add data to c2
    c2.offer("howdy");
    c2.offer("hi there");
    //reprint c2, getCount and isEmpty to prove updated data values
    System.out.println("c2.toString(): \n" + c2.toString());
    System.out.println("c2.getCount(): " + c2.getCount());
    System.out.println("c2.isEmpty(): " + c2.isEmpty());
    System.out.println("");
    /* demonstrate peek and element functions by printing out most
     * recent items in the linked queue
     */
    System.out.println("c1.peek(): " + c1.peek());
    System.out.println("c2.element(): " + c2.peek());
    System.out.println("");
    //remove items from c1 to show peek returns null when list is empty
    c1.remove();
    c1.remove();
    System.out.println("c1.peek(): " + c1.peek());
    System.out.println("c1.getCount(): " + c1.getCount());
    System.out.println("c1.isEmpty(): " + c1.isEmpty());
    
    //all methods in queue interface have been demonstrated
}

}

再次提前感谢您的任何帮助！

Answer 1

我在作业中得了零分——根据评分者，我的链表实现不是循环的。

我觉得这种评价有点苛刻。从外部看，您的类表现为循环:它能够在O(1)时间内添加新值，并且“最后一个”值与“第一个”值有一个链接，从而结束循环。

我想我的问题是:这不是以什么方式循环实施的？

在一个真正的循环实现中，我不期望看到“头”和“尾”的概念。毕竟，一个圆没有开始也没有结束。它可能有一个当前元素，链接到下一个和上一个元素。也许这就是所需要的。从内部看，这个实现看起来非常类似于普通的链表，可以快速访问尾部。最好问问评分者！