CODEWITHSUNDEEP
javadata-structureslinked-list
AAA
AAA

Reputation: 17

implementation of LinkedList without last node

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();
}

Upvotes: 0

Views: 73

Answers (1)

trincot
trincot

Reputation: 350167

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();
}

Upvotes: 1

Related Questions