英文:
implementation of LinkedList without last node
问题
以下是你要翻译的内容:
我被要求重新实现一个没有使用尾节点的链表。因此,我必须更改链表的方法,使其在没有使用尾节点的情况下也能工作。
removeLast
方法让我感到困惑:以下是我尝试做的,但它并没有移除节点。
我的尝试有什么问题吗?
public E removeLast()
{
if(isEmpty()) return null;
Node<E> temp = head;
while (temp.getNext() != null) {
temp = temp.getNext();
}
E a = temp.getData();
temp = null;
size--;
// if(head == temp)
if (head.getNext() == null)
head = null;
return a;
}
测试类
public static void main(String arg[]) {
LinkedListWm<Integer> r = new LinkedListWm<>();
r.addFirst(1);
r.addFirst(3);
r.addFirst(7);
r.addFirst(50);
r.addLast(5);
System.out.println(r.last());
System.out.println(r.first());
r.removeLast();
System.out.println(r.last());
r.removeFirst();
r.display();
}
英文:
I have been asked to re-implement a linked list without the use of a tail. So I have to change its methods so it can work without using a tail node.
The removeLast
method confused me: here is what I tried to do, but it didn't remove the node.
What is wrong with my attempt?
public E removeLast()
{
if(isEmpty()) return null;
Node<E> temp=head;
while (temp.getNext()!=null) {
temp=temp.getNext();
}
E a=temp.getData();
temp=null;
size--;
// if(head==temp)
if (head.getNext()==null)
head=null;
return a;
}
Test class
public static void main(String arg[]) {
LinkedListWm<Integer> r = new LinkedListWm<>();
r.addFirst(1);
r.addFirst(3);
r.addFirst(7);
r.addFirst(50);
r.addLast(5);
System.out.println(r.last());
System.out.println(r.first());
r.removeLast();
System.out.println(r.last());
r.removeFirst();
r.display();
}
答案1
得分: 1
你需要跟踪位于 temp
之前的节点。你将需要用它来结束位于前一个节点的列表,方法是将其 next
属性设置为 null。
目前你尝试使用以下方式实现:
temp = null;
...但这只是清除变量 temp
的内容。它并不改变列表。要想实现改变,你必须修改一个 next
属性。
因此,定义一个在 temp
之后的 prev
变量:
Node<E> prev = null;
while (temp.getNext()!=null) {
prev = temp;
temp = temp.getNext();
}
然后,将:
temp = null;
改为:
prev.next = null;
当然,后者仅在 prev
不为 null 时才能实现,或者换句话说,当 head
不是最后一个节点(即 temp
)时才能实现。
所以把它整体写在一起:
public E removeLast()
{
if (isEmpty()) return null;
Node<E> prev = null;
Node<E> temp = head;
while (temp.getNext() != null) {
prev = temp;
temp = temp.getNext();
}
size--;
if (prev == null)
head = null;
else
prev.next = null;
return temp.getData();
}
英文:
You need to keep track of the node that precedes temp
. You'll need it to end the list at the preceding node, by setting its next
property to null.
Currently you try to do that with:
temp = null;
...but that is just clearing the content of the variable temp
. It does not alter the list. For that to happen, you must alter a next
property.
So define a prev
variable that will follow after temp
:
Node<E> prev = null;
while (temp.getNext()!=null) {
prev = temp;
temp = temp.getNext();
}
And instead of:
temp = null;
do:
prev.next = null;
Of course, the latter can only happen when prev
is not null, or in other words, when head
is not the last node (i.e. temp
).
So taking it all together:
public E removeLast()
{
if (isEmpty()) return null;
Node<E> prev = null;
Node<E> temp = head;
while (temp.getNext() != null) {
prev = temp;
temp = temp.getNext();
}
size--;
if (prev == null)
head = null;
else
prev.next = null;
return temp.getData();
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论