单链表实现

Question

好的，我正在尝试通过我的教科书（Goodrich & Tamassia，算法设计，2001）实现一个（单）链表，到目前为止一切顺利。

现在，我运行遇到的问题是我无法正确测试它例如，如果我通过 insertFirst 方法插入一个节点，我如何仍然能够检索它能够将它用于类似 swapElements 的方法吗？

我考虑过通过元素来工作，但是当我有具有相同元素的节点时，我会运行遇到问题。那么，这通常应该如何工作？如果我的问题相对简单或含糊，我很抱歉，在这种情况下，请告诉我如何改进它，因为我对数据结构还很陌生。

这是我的代码；

public class Node<E> implements Position<E> {

    private Node<E> next;
    private E element;

    public Node(Node<E> next, E element) {
        this.next = next;
        this.element = element;
    }

    public Node(E element) {
        this.element = element;
    }

    public void setNext(Node<E> next) {
        this.next = next;
    }

    public Node<E> getNext() {
        return next;
    }

    public void setElement(E element) {
        this.element = element;
    }

    public E element() {
        return element;
    }

    public String toString() {
        return ("Element: " + element);
    }

}

和

public class SinglyLinkedListImp<E> implements List<E> {

    private Node<E> head;
    private int size;

    public SinglyLinkedListImp() {
        this.head = null;
        this.size = 0;
    }

    public Node<E> first() {
        return head;
    }

    public Node<E> last() {
        Node<E> current = head;
        while (current.getNext() != null) {
            current = current.getNext();
        }
        return current;
    }

    public boolean isFirst(Node<E> n) {
        return (head == n);
    }

    public boolean isLast(Node<E> n) {
        return (n.getNext() == null);
    }

    public Node<E> before(Node<E> n) {
        Node<E> current = head;
        while (current.getNext() != n) {
            current = current.getNext();
        }
        return current;
    }

    public Node<E> after(Node<E> n) {
        return n.getNext();
    }

    public Node<E> replaceElements(Node<E> n, E element) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current != n) {
            previous = current;
            current = current.getNext();
        }
        Node<E> newLink = new Node<E>(current.getNext(), element);
        previous.setNext(newLink);
        return current;
    }

    public void swapElements(Node<E> n, Node<E> k) {
        E tmp = n.element();
        n.setElement(k.element());
        k.setElement(tmp);
    }

    public void insertFirst(E element) {
        head = new Node<E>(head, element);
        size++;
    }

    public void insertLast(E element) {
        if (head == null) {
            head = new Node<E>(head, element);
        } else {
            Node<E> current = head;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(new Node<E>(null, element));
        }
        size++;
    }

    public void insertBefore(Node<E> n, E element) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current.getNext() != n) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(n);
    }

    public void insertAfter(Node<E> n, E element) {
        Node<E> current = head;
        while (current != n) {
            current = current.getNext();
        }
        current.setNext(n);
    }

    public void remove(Node<E> n) {
        Node<E> current = head;
        Node<E> previous = null;
        while (current != n) {
            previous = current;
            current = current.getNext();
        }
        previous.setNext(current.getNext());
        size--;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return (size == 0);
    }

    public void display() {
        if (head == null) {
            System.out.println("Empty list.");
        } else {
            Node<E> current = head;
            while (current != null) {
                System.out.println(current.toString());
                current = current.getNext();
            }
        }
    }

}

请注意，SinglyLinkedListImp class 尚未完全完成（如果列表为空，某些方法会出错）。我认为不需要提供这两个接口的代码，但如果需要请告诉我。

Answer 1

在您的实现中，您设置了一些可用于迭代集合的方法（如 getNext 等）。我能想到的一个场景是在一次操作中检索列表的任何元素，然后根据元素（如 swapElements）对集合应用编辑。

不过，我建议您做的（并且可能会把事情弄清楚）是添加一个按索引检索元素的方法：方法 get(int index) 会将元素 return 放置在作为参数给出的索引上。其实Java中的LinkedList集合标准API就有这样的方法。这背后的逻辑很简单：获取下一个节点，直到迭代次数达到索引号。

更新：为了应用元素交换，显然Node所涉及的MUST是列表的一部分，否则这里没有任何意义。正如所建议的那样，swapElements 可能基本上用于 in-class 目的，因此除非您有充分的理由，否则请将其声明为私有。

单链表实现

Singly Linked List Implementation

java

singly-linked-list