java何时初始化链表中的虚拟节点

Question

我正在用Java实现一个带有虚拟节点的单链表版本

public class Node{
  private String data;
  private Node nextNode;
 
  public Node(String data){
    this.data = data;
    this.nextNode = null; 
  }

  //getters, setters, toString()
}

public class LinkedList {
private Node header;
private Node lastNode;
private int size;

public LinkedList() {
    this.header = new Node(null);
    this.lastNode = this.header;
    size = 0;
}

public void prepend(String data) {

    if (data == null || data.trim().length() == 0) {
        return;
    }

    Node newNode = new Node(data);

    // when the linked list is empty
    if (size == 0) {
        this.header.setNext(newNode);
        this.lastNode = newNode;
    } else { // when the list has nodes
        Node existingNode = this.header.getNext();

        newNode.setNext(existingNode);
        this.header.setNext(newNode);
    }
    size++;
}
}

我主要集中在这一部分

public LinkedList() {
    this.header = new Node(null);
    this.lastNode = this.header;
    size = 0;
}

创建并初始化链表对象时，标题和最后一个节点指向虚拟节点

这是实现链表的有效方法吗？或者，我必须按如下方式修改prepend（）方法中的代码吗

public void prepend(String data) {

    if (data == null || data.trim().length() == 0) {
        return;
    }

    Node newNode = new Node(data);

    // when the linked list is empty
    if (size == 0) {
        this.header = new Node(null);
        this.header.setNext(newNode);
        this.lastNode = newNode;
    } else { // when the list has nodes
        Node existingNode = this.header.getNext();

        newNode.setNext(existingNode);
        this.header.setNext(newNode);
    }
    size++;
}

另外，是否真的需要使用虚拟节点作为标头？我们可以使用第一个节点本身作为标头吗？如果使用了虚拟节点，在什么情况下应该使用虚拟节点

Answer 1

如果要对节点的链接字段强制执行非null约束，则虚拟节点非常有用。此外，它允许实现所有操作，而无需为第一个和最后一个节点实现特殊情况，例如

public class LinkedList {
    static final Node REMOVED = new Node();

    public static class Node {
        Node next, prev;
        String data;
        Node() {
            next = prev = this;
        }
        Node(String s, Node n, Node p) {
            data = s;
            next = n;
            prev = p;
        }
        public Node insertBefore(String s) {
            if(next == REMOVED) throw new IllegalStateException("removed node");
            Node node = new Node(s, this, prev);
            prev.next = node;
            prev = node;
            return node;
        }
        public Node insertAfter(String s) {
            return next.insertBefore(s);
        }
        public void remove() {
            if(next == REMOVED) throw new IllegalStateException("already removed");
            prev.next = next;
            next.prev = prev;
            next = prev = REMOVED;
        }

        @Override
        public String toString() {
            return data;
        }
    }

    final Node content = new Node();

    private Node first() {
        return content.next;
    }

    private Node last() {
        return content.prev;
    }

    public Node getFirst() {
        Node f = first();
        if(f == content)
            return null; // or throw new NoSuchElementException(string);
        return f;
    }

    public Node getLast() {
        Node f = last();
        if(f == content)
            return null; // or throw new NoSuchElementException(string);
        return f;
    }

    public Node prepend(String s) {
        return first().insertBefore(s);
    }

    public Node append(String s) {
        return last().insertAfter(s);
    }

    public Node findFirst(String string) {
        for(Node n = first(); n != content; n = n.next) {
            if(n.data.equals(string)) return n;
        }
        return null; // or throw new NoSuchElementException(string);
    }

    public Node findLast(String string) {
        for(Node n = last(); n != content; n = n.prev) {
            if(n.data.equals(string)) return n;
        }
        return null; // or throw new NoSuchElementException(string);
    }

    void printForward() {
        for(Node n = first(); n != content; n = n.next) {
            System.out.println(n.data);
        }
    }

    void printBackward() {
        for(Node n = last(); n != content; n = n.prev) {
            System.out.println(n.data);
        }
    }
}

这是一个双链接列表，其内部使用的伪节点的next和prev字段成为列表的“第一”和“最后”字段。这样，所有修改方法只需对Node类及其next和prev字段进行操作，并且对第一个和最后一个节点的引用将自动以正确的方式处理。请注意，所有的修改方法都仅位于两个实现方法之上，insertBefore和remove

它可以像这样使用

LinkedList l = new LinkedList();
l.append("H").insertAfter("l").insertAfter("l");
l.findFirst("l").insertBefore("e");
l.findLast("l").insertAfter("o");
l.printForward();

System.out.println();

l.getFirst().remove();
l.findFirst("l").remove();
l.getFirst().remove();
l.getLast().insertBefore("r");
l.getFirst().insertBefore("d");
l.append("W");
l.printBackward();

比如说。对于单个链表，虚拟节点可能不太有用。如果像在您的示例中那样，您没有从中获益，而是拥有所有的特殊情况处理，那么您不应该使用虚拟节点，这只会使代码更加复杂