数据结构在Java中如何将循环链表的尾部链接到列表的头部？

Question

我试着在列表的前面和后面插入。然而，在循环链表类中，这些方法在一定程度上是可行的

我的问题是，我似乎不知道如何将列表的尾部与顶部联系起来。不过我已经让头指向尾巴了

因此，在执行以下代码行之后：

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

代码中的主要问题是，假设将存在一个next引用，即null，但这与循环链表的原理相矛盾。在循环链表中，您可以始终从一个节点转到下一个节点，并在循环中无休止地运行。所以原则是：next引用都不应该是null

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

其他一些评论：

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

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

• 对于您拥有的两种插入方法，有一些代码重复。新节点与现有节点的这种链接只能在一个地方完成。我建议用另一种方法

• 在你的课堂上真的没有必要有tail成员，因为tail总是将成为this.head.GetPreviousNode()（当然，除非你的列表是空的）。所以我会去掉tail成员，改为使用这个表达式。这将使您不必保持tail引用的最新状态

• insertAfter方法当前对列表中的目标值执行查找。如果您将这个逻辑放在一个单独的find方法中，这样它就可以在其他地方重新使用（如果需要的话）

下面是更正的Node类：

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