如何删除 Double Link 列表中的尾部？

Question

我的老师在这个activity中指导我们如何删除双link列表的尾部。他创建了一个循序渐进的流程或算法供我们遵循。我跟着它，但它不起作用。或者也许我听错了。这是算法

Check if the list is empty

If not Empty

Check if there is only one node in the list

If only one node, set the head and tail reference to null.

if more than one node

create a temptail to point to next tail (tail.prev)

set the prev of the tail and next of temptail to null

assign the temptail value to the tail

这是我的代码

    public void delTail(){
    DoubleNode temp;
    
   if(isEmpty()){
       return;
   }
   else if(!isEmpty()){
       if(head == tail){
           head = tail = null;
       }
       else{
            temp = tail.next;
            tail.prev = null;
            temp.next = null;
            temp = tail;
       }
   }
    
}

这是我看到的错误error in my terminal

我认为我是否正确地遵循了它？非常感谢您的帮助:)

这是我的构造函数*

public class DoubleNode{

public DoubleNode prev;
public int data;
public DoubleNode next;

public DoubleNode(int d){
    this(null, d, null);
}
public DoubleNode(DoubleNode p, int d, DoubleNode n){
    prev = p;
    data = d;
    next = n;
}
}

这是mt整个运营商代码*

public class operator{
DoubleNode head;
DoubleNode tail;
DoubleNode laman;

String output = "";

public operator(){
    head = tail = null;
}
public boolean isEmpty(){
    return head == null;
}
public void addHead(int i){
    
    if(isEmpty()){
      head = tail =new DoubleNode(i);
    }
    else{
        head = new DoubleNode(null, i, head);
        head.prev = head;
    }
}
public void addTail(int i){
    DoubleNode last = new DoubleNode(i);  
    if(isEmpty()){
        head = tail = new DoubleNode(i);
    }
    else{
      tail.next = last;
      tail = last;
    }
}
public void delHead(){
    DoubleNode temp = head.next; 
    if(head==tail){ //this if condition is testing if the head and tail is one only, 
        head = tail =null;  //if there is only one this will set the tail and head to null
    }
    else{
        head = head.next;
        head = temp;

    }
}

public void delTail(){
        DoubleNode temp;
        if(isEmpty()) {  
            return;  
        }  
        else {  
            if(head != tail) {   
            tail = tail.prev;
            temp = tail;
               
            }
            
            else {  
                head = tail = null;  
            }  
        }  
}
public void display(){
    DoubleNode tmp = head;
    output = "<html>";
    
    for(tmp = head; tmp != null; tmp = tmp.next){
        output = output + "<br>" + tmp.data + "<b>" + "<br>";
        
    }
    output = output + "</html>";
}
}

这是我到目前为止的全部代码，我有一个带有 jframe 的主 class，但我认为它很好，因为我也将它用于单个 link 列表。但是我在双 link 列表中确实遇到了关于删除最后一个节点

的问题

Answer 1

你的问题是你只是分配给 temp 但实际上并没有使用它。此外，您没有将 link 正确设置回前一个元素。

假设 tail.next 再次指向 head，您可以执行以下操作：

tail.prev.next = tail.next; //you might need to check for `tail.prev` being null 
tail.next.prev = tail.prev; //you might need to check for `tail.next` being null
//delete tail

举例说明：

A -next-> Tail -next-> Head
^---prev--+  ^---prev--+

第 1 步：

+----next--------------V
A         Tail -next-> Head
^---prev--+  ^---prev--+

第 2 步：

+----next--------------V
A         Tail -next-> Head
^---prev--+            |
^--------------prev----+

实际上，如果 tail.next == head 删除尾部与删除任何其他节点没有什么不同。

Answer 2

您的 else 块中有两个错误：

您永远不会更改 tail 引用。最后一条语句实际上应该是对 tail.
的赋值
您似乎假设 tail 有一个 non-null next 引用，但这是矛盾的。尾部应该是最后一个节点，因此它的 next 引用将始终为空（除非您应该创建一个 circular 列表）。因此，temp 将为空，语句 temp.next = tail 将触发空指针异常。

tail比较有意思的属性是它的prev属性，指的是当前尾巴之后会变成tail的节点节点已被删除。 tail.prev 在您的作业中明确提及。

所以：

   else {
        temp = tail.prev; // <--- should point to the new tail
        tail.prev = null;
        temp.next = tail;
        tail = temp;  // <--- reverse the assignment
   }

其他几个问题...

在 addHead 中您没有正确设置 prev 属性。你把它设为 self-reference。意识到 head 已经在引用新节点。变化：

head.prev = head;

至：

head.next.prev = head;

在 addTail 中缺少对 prev 的分配。变化：

tail.next = last;
tail = last;

至：

tail.next = last;
last.prev = tail; // needed!
tail = last;

在 delHead 中，您必须确保新头的 prev 为空。所以改变：

head = temp;

至：

head = head.next;
head.prev = null;

注意：在该方法中您不需要 DoubleNode temp = head.next;。

如何删除 Double Link 列表中的尾部？

How to delete tail in Double Link List?

java

constructor

linked-list

double

tail

其他几个问题...