如何删除 Double Link 列表中的尾部?
How to delete tail in Double Link List?
我的老师在这个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 列表中确实遇到了关于删除最后一个节点
的问题
你的问题是你只是分配给 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
删除尾部与删除任何其他节点没有什么不同。
您的 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;
。
我的老师在这个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 列表中确实遇到了关于删除最后一个节点
的问题你的问题是你只是分配给 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
删除尾部与删除任何其他节点没有什么不同。
您的 else
块中有两个错误:
您永远不会更改
的赋值tail
引用。最后一条语句实际上应该是对tail
.您似乎假设
tail
有一个 non-nullnext
引用,但这是矛盾的。尾部应该是最后一个节点,因此它的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;
。