这个链表是循环实现的吗？

Question

这是我第一次 post 在这里！我是一名CS学生，所以我还在学习。如果您有任何关于构建我的代码或一般实践的建议或指示（哈哈..！），我将不胜感激！

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

我不想给人留下自负或过于自信的印象，因为我显然在某种程度上不知道自己在做什么，但是在第 155 行到第 161 行中，我注释掉了打印的部分输出列表中下一个 link 的数据。据我所知，列表中的节点是 link 循环编辑的，因为即使在打印完最后一个节点的数据后，它们仍会继续打印第一个节点的数据。

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

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

打印：

next: 45

next.next: 71

next.next.next: 3

next.next.next.next: 45

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

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

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

tail = node;
node.setNext(head);

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

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

提前感谢您的帮助！

完整代码（三个class分别是CircularLinkedQueue、Node和CircularLinkedListTest）：

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

CircularLinkedListTest：

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

I received a zero on the assignment -- according to the grader my implementation of the linked list is not circular.

我觉得这个评价有点苛刻。 从外部看，你的class表现循环：它能够在 O(1) 时间内添加新值，并且"last" 值有一个 link 到 "first"，关闭循环。

I guess my question is: in what way is this not implemented circularly?

在真正的循环实施中，我不希望看到 "head" 和 "tail" 的概念。毕竟，一个圆没有起点也没有终点。它可能有一个当前元素，links 到下一个和上一个元素。也许这就是所需要的。 从内部看, 这个实现看起来非常类似于 run-of-the-mill linked 列表，快速访问尾巴。最好问一下评分员！

这个链表是循环实现的吗？

Is this linked list implemented circularly?

java

queue

linked-list

circular-list

data-structures