如何在Java中将一个循环链表的尾部链接到列表的头部？[关闭]

Question

我目前正在为Java中的循环链表工作。我们应该能够在列表的前面插入和后面插入。但是，我已经让这些方法在循环链表类中正常工作。

list.InsertAtFront(0);

list.InsertAfter(0, 4); // Inserting the 4 after 0 which was inserted above...

我得到的结果是

[data:ID=0{previous:4},{next:4}]->[data:ID=4{previous:0},{next:null}]

对于第二次插入，这里的next指向null{next:null}应该指向列表的头部{next:0}。

节点类

package circular_linked_list;

public class Node {
    private int id;
    private Node next_node;
    private Node previous_node;

    public Node(){
        this.id = 0;
        this.next_node = null;
        this.previous_node = null;
    }

    public Node(int id, Node next_node, Node previous_node){
        this.id = id;
        this.next_node = next_node;
        this.previous_node = previous_node;
    }

    public Node(int id){
        this.id = id;
        this.next_node = null;
        this.previous_node = null;
    }

    public Node(Node node){
        this.id = node.GetId();
        this.next_node = node.GetNextNode();
        this.previous_node = node.GetPreviousNode();
    }

    public void SetId(int id) {
        this.id = id;
    }

    public void SetNextNode(Node next_node) {
        this.next_node = next_node;
    }

    public void SetPreviousNode(Node previous_node) {
        this.previous_node = previous_node;
    }

    public int GetId() {
        return this.id;
    }

    public Node GetNextNode() {
        return this.next_node;
    }

    public Node GetPreviousNode() {
        return this.previous_node;
    }

    public void NodeDetails(){
        if(this.previous_node != null && this.next_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: "+ this.next_node.GetId() + "}] -> ");
        }
        else if(this.previous_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: null}] -> ");
        }
        else if(this.next_node != null){
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: null}, {Next: "+ this.next_node.GetId() + "}] -> ");
        }
        else{
            System.out.print("[Data: __ID = " + this.id + "__ |{Previous: null}, {Next: null}] -> ");
        }
    }
}

循环链表类

package circular_linked_list;


public class CircularLinkedList{
    private Node head;
    private Node tail;

    public CircularLinkedList(){
        this.head = null;
        this.tail = null;
    }

    public CircularLinkedList(Node head, Node tail){
        this.head = head;
        this.tail = tail;
    }

    public void SetHead(Node head){
        this.head = head;
    }

    public void SetTail(Node tail){
        this.tail = tail;
    }

    public Node GetHead(){
        return this.head;
    }

    public Node GetTail(){
        return this.tail;
    }

    public void InsertAtFront(int data){
        Node new_node = new Node(data);

        if( new_node != null){
            // If the list is not empty then...
            if(this.head != null){
                this.head.SetPreviousNode(new_node); // Set the list head's previous node to point to the new node.
                new_node.SetNextNode(this.head); // Set the new node's next node to point to the current list head.
                new_node.SetPreviousNode(this.tail); // Set the previous node of the head of the list to point to the tail of the list
            }

            this.head = new_node; // Set the list head to point to the new node
            this.FindTail(); // Set the tail of the list.
        }
        else{
            System.out.print("Sorry, the list is full!");
        }
    }

    public void InsertAfter(int target, int data){
        Node new_node = new Node(data);

        if(new_node != null){
            Node target_node = this.head;
            boolean found = false;

            // This while loop will loop to find if a node is equal to the value passed as target.
            while(target_node != null){
                if(target_node.GetId() == target){
                    // If the target is found then break the loop to keep this current node as the target node.
                    found = true;
                    break;
                }

                // Assigning the target node next node to the target node.
                target_node = target_node.GetNextNode();
            }
     
            // If the target was found then...
            if(found){
                new_node.SetPreviousNode(target_node); // Set the previous node of the new node to point to the target node.

                // Set the next node of the new node with the target node's next node to continue to link.
                new_node.SetNextNode(target_node.GetNextNode());

                // If the target node's next node is not null, then set the target node's next node->previous node to point to the new node.
                if(target_node.GetNextNode() != null){
                    target_node.GetNextNode().SetPreviousNode(new_node);
                }

                target_node.SetNextNode(new_node); // Set the target node's next node to point to the new node.

                // Setting the tail of the list...
                this.FindTail();
            }
            else{
                System.out.println("Sorry, but the integer " + target + " was not found in the list!\n");
            }
        }
        else{
            System.out.println("Sorry, the list is full!\n");
        }
   }

   public void DisplayList(){
       Node current_node = this.head;

        while(current_node != null){
            current_node.NodeDetails();

            current_node = current_node.GetNextNode();
        }
   }

   private void FindTail(){
       Node current_node = this.head;

        // Traversing from the start of the list to the end to get the tail.
        while(current_node.GetNextNode() != null){
            current_node = current_node.GetNextNode();
        }

        this.head.SetPreviousNode(current_node); // Updating the head of the list previous node.

        this.SetTail(current_node); // Set the tail of the list with the last node.
    }
}

主班

package circular_linked_list;


public class Main {
    public static void main(String[] args) {
        CircularLinkedList list = new CircularLinkedList();

        // Inserting at the front of the list
        list.InsertAtFront(0);
        
        // Inserting 4 right after the 0
        list.InsertAfter(0, 4);

        // To display the nodes/elements in the list
        list.DisplayList();
    }
}

Answer 1

代码中的主要问题是假设下一个引用是null，但这与循环链表的原则相矛盾。在一个循环链表中，您总是可以从一个节点到下一个节点，在循环中无休止地运行。因此，原则是:下一个引用都不应该是null！

这意味着您必须在设置null或检查null值的几个地方修改代码。

其他一些评论：

>

让节点构造函数通过其下一个和上一个成员使新节点引用自身。这样可以避免从一开始就在那里存储null。这就像自己制作一个单节点循环链表一样。

循环不应该检查null，而是检测您已经循环并返回到head节点。

以下是更正的节点类：

public class Node {
    private int id;
    private Node next_node;
    private Node previous_node;

    public Node(){
        this.id = 0;
        // Make a node refer to itself by default -- this is practical in a circular list
        this.next_node = this;
        this.previous_node = this;
    }

    public Node(int id, Node next_node, Node previous_node){
        this.id = id;
        this.next_node = next_node;
        this.previous_node = previous_node;
    }

    public Node(int id){
        this.id = id;
        // Make a node refer to itself by default -- this is practical in a circular list
        this.next_node = this;
        this.previous_node = this;
    }

    public Node(Node node){
        this.id = node.GetId();
        this.next_node = node.GetNextNode();
        this.previous_node = node.GetPreviousNode();
    }

    public void SetId(int id) {
        this.id = id;
    }

    public void SetNextNode(Node next_node) {
        this.next_node = next_node;
    }

    public void SetPreviousNode(Node previous_node) {
        this.previous_node = previous_node;
    }

    public int GetId() {
        return this.id;
    }

    public Node GetNextNode() {
        return this.next_node;
    }

    public Node GetPreviousNode() {
        return this.previous_node;
    }

    public void NodeDetails(){
        System.out.print("[Data: __ID = " + this.id + "__ |{Previous: " + this.previous_node.GetId() + "}, {Next: "+ this.next_node.GetId() + "}] -> ");
    }
}

和更正的circularLinkedList类：

public class CircularLinkedList{
    private Node head; // No need for a tail

    public CircularLinkedList(){
        this.head = null;
    }

    public CircularLinkedList(Node head){
        this.head = head;
    }

    public void SetHead(Node head){
        this.head = head;
    }

    public Node GetHead(){
        return this.head;
    }

    public void InsertAtFront(int data){
        if (this.head == null) {
            this.head = new Node(data);
        } else {
            insertAfter(this.head.GetPreviousNode(), data);
            this.head = this.head.GetPreviousNode();
        }
    }

    public Node find(int target) {
        Node target_node = this.head;
        while (target_node != null) {
            if(target_node.GetId() == target) {
                return target_node;
            }
            target_node = target_node.GetNextNode();
            if (target_node == this.head) break; // running in circles
        }
        return null;
    }

    // Add this method to avoid code repetition
    public void insertAfter(Node target_node, int data) {
        Node new_node = new Node(data, target_node.GetNextNode(), target_node);
        target_node.SetNextNode(new_node);
        new_node.GetNextNode().SetPreviousNode(target_node);
    }

    public void InsertAfter(int target, int data){
        Node target_node = find(target);
        if (target_node != null) {
            insertAfter(target_node, data);
        } else{
            System.out.println("Sorry, but the integer " + target + " was not found in the list!\n");
        }
   }

   public void DisplayList(){
        Node current_node = this.head;

        while (current_node != null) {
            current_node.NodeDetails();
            current_node = current_node.GetNextNode();
            if (current_node == this.head) break; // running in circles
        }
   }
}