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

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字段成为列表的"第一"one_answers"最后"字段。这样，所有的修改方法只需要对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();

例如。对于单个链表，虚拟节点可能不太有用。如果，就像你的例子一样，你没有从中受益，但有所有的特殊情况处理，你不应该使用虚拟节点，这只会使代码更加复杂。