有人能解释一下我如何删除双链接列表中的第一个和最后一个节点吗

Question

我创建了一个类SLList，在其中我接受了一个双链表SLList并对其进行了一些调整。

现在，我试图通过两个称为public T firstout()和public T lastout()的函数来删除双链表中的第一个节点和双链表中最后一个节点，我认为每个函数的目的都是不言自明的。

根据StackOverflow用户的建议，我决定只使用一个哨兵来帮助我完成任务。然而，我正在努力使哨兵对我有利。

这是我到目前为止的代码：

public class SLList<T>{ // Add Generics here
private class IntNode {
private T data;
private IntNode previous;
private IntNode next;
public IntNode (T data, IntNode previous, IntNode next) {
this.data = data;
this.previous = previous;
this.next = next;
}
public IntNode () { // Self-referencing node
next = previous = this;
}
}
IntNode sentinel; // One sentinel can serve both purposes
private int length = 0;
public SLList(){
sentinel = new IntNode(); // Self referencing previous/next
}
public void addFirst(T data) {
IntNode node = new IntNode(data, sentinel, sentinel.next);
sentinel.next = node;
node.next.previous = node;
}
public boolean isempty() {
return length == 0;
}

public T firstout() {
return sentinel.previous == null;
}
public T lastout() {
return sentinel.next == null;
}

根据我试图找到的，我认为.previous指向列表的开头，将其设置为null将有效地删除第一个节点，.next指向下一个节点，将其设为null也将删除最后一个节点。

我的理解哪里出了问题？将非常感谢任何提示或代码改进

Answer 1

首先，您不需要length来知道列表是否为空。您也可以这样定义isEmpty方法：

public boolean isEmpty() {
return sentinel.next == sentinel;
}

注意：我更喜欢camelCase而不是所有小写的方法名，所以isEmpty而不是isempty，firstOut而不是firstout。

对于firstOut和lastOut方法，我首先定义一个私有方法，该方法从列表中删除给定节点(假设它在列表中(：

private T removeNode(IntNode node) {
// Link neighbors to eachother, skipping over given node
node.previous.next = node.next;
node.next.previous = node.previous;
return node.data;
}

然后可以按如下方式使用：

public T firstOut() {
return removeNode(sentinel.next);
}

public T lastOut() {
return removeNode(sentinel.previous);
}

在这个版本中，如果列表为空并且调用了firstOut或lastOut，则removeNode调用不会对列表进行任何更改，因为它得到的节点将是链接到自己的sentinel节点，因此这两个分配都只是确认了已经存在的情况。CCD_ 18或CCD_。

或者，当调用removeNode时，当列表为空时，也可以抛出异常。但是异常处理本身就是一个主题，所以我不会在这里深究。