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

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

创建并初始化链表object时，header和最后一个节点指向一个虚拟节点。

这是实现链表的有效方法吗？或者，我是否必须如下更改 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++;
}

另外，header真的有必要使用虚拟节点吗？我们可以使用第一个节点本身作为 header 吗？在什么情况下我们应该使用虚拟节点（如果使用的话）？

Answer 1

如果您想对节点的 link 字段强制执行非 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);
        }
    }
}

这是一个双重 linked 列表，其内部使用的虚拟节点的 next 和 prev 字段成为列表的“第一个”和“最后一个”字段。这样，所有修改方法只需对 Node class 及其 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();

例如。对于单个 linked 列表，虚拟节点可能不太有用。如果像在您的示例中一样，您没有从中获益但有所有特殊情况处理，则不应使用只会使代码更加复杂的虚拟节点。

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

When to initialize a dummy node in a linked list

java

collections

linked-list