如何 link 循环 link 编辑列表尾到 Java 中列表的头部？

Question

我正在尝试在列表的前面和后面插入。但是，我已经让这些方法在循环链表 class.

中发挥了一定的作用

我的问题是，我似乎无法弄清楚如何 link 尾部与列表的头部。不过我已经把头指向尾巴了。

所以在执行下面的代码行之后：

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

非常感谢大家的帮助！

我会在下面展示我目前所拥有的...

节点CLASS

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}] -> ");
        }
    }
}

循环链表CLASS

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

主要CLASS

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引用的none应该是null!

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

一些其他备注：

让 Node 构造函数使新节点通过其 next 和 previous 成员引用自身。这样您就可以避免从一开始就将 null 存储在那里。就好像自己做了一个单节点循环链表。
循环不应该检查 null，而是检测你已经循环并返回到 head 节点。
您拥有的两种插入方法有一些代码重复。新节点与现有节点的这种链接应该只在一个地方完成。我建议为此制作一个单独的方法。
您的 class 中确实不需要 tail 成员，因为 tail 总是将是 this.head.GetPreviousNode()（当然除非你的列表是空的）。因此，我将删除 tail 成员并改为使用该表达式。这将使您不必使 tail 参考保持最新。
insertAfter 方法当前对列表中的目标值执行查找。如果您将此逻辑放在单独的 find 方法中会更好，这样它就可以在其他地方重新使用（如果需要）。

这里是更正后的 Node class:

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 class:

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

如何 link 循环 link 编辑列表尾到 Java 中列表的头部？

How to link the a circular linked list tail to the head of the list in Java?

java

linked-list

data-structures