java - java实现循环链​​表

Question

我在实现循环链表时遇到了一些问题。我正在处理一个需要您自己实现任何 ADT 的问题。我似乎可以在列表中添加节点，但是在删除时我不熟悉。我包含了前两个删除方法，让您了解我的想法，我将如何删除列表中的最后一个节点？

public class LinkedList {
    private Node head;
    private Node tail;
    private int size = 0;
    LinkedList() {
        head = null;
        current = null;
        previous = null;
        tail = null;
        size = 0;
    }

    //checks if list is empty
    public boolean isEmpty() {
        return head == null;
    }
    //add new node to front of circularly linked list
    public void addToFront(E x) {
        if (head == null) {
            head = new Node(x);
        } else {
            Node n = new Node(x);
            x.next() = head;
            head = x;
        }
    }

    public void addtoMiddle(E x) {
        x.next = current.next();
        current.next = x;
        size = size + 1;
    }

    public void addToEnd(E x) {
        x.next = null;
        tail.next() = x;
        tail = x;
        size = size + 1;
    }

    public void removeFirst(E x) {
        if (head = null) {
            System.out.println("Error! List is empty!");
        } else {
            head = current.next();
            size = size + 1;
        }
    }

    public void removeMiddle(E x) {
        previous.next() = current.next();
        current.next() = null;
        size = size + 1;
    }

Answer 1

在循环链表中，最后一个节点的 next 指向头部，因此您循环遍历节点直到 node.next.equals( head )。请注意，next 绝不能为 null，如果您只有一个节点，则您有 head.next = head。

在循环双向链表中，您还有一个 previous 节点，即您可以向后迭代。在这种情况下，您的最后一个节点只是 head.previous。

一个小的ascii图片:

head -next---> node -next---> node -next---> last
 | ^  <---prev-      <---prev-      <---prev- | ^
 | |                                          | |
 | |_____________________________________next_| |
 |_prev_________________________________________|