链表的实现,不包括最后一个节点。

huangapple go评论74阅读模式
英文:

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&lt;E&gt; 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&lt;Integer&gt; r = new LinkedListWm&lt;&gt;();
	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&lt;E&gt; 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&lt;E&gt; prev = null;
    Node&lt;E&gt; temp = head;
    
    while (temp.getNext() != null) {
        prev = temp;
        temp = temp.getNext();
    }
    
    size--;
    if (prev == null)
        head = null;
    else
        prev.next = null;
        
    return temp.getData();
}

huangapple
  • 本文由 发表于 2020年10月17日 19:39:24
  • 转载请务必保留本文链接:https://go.coder-hub.com/64402013.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定