CODEWITHSUNDEEP
javadata-structureslinked-list
jpherrerias18
jpherrerias18

Reputation: 11

How can I remove the last node of a Linked List in java?

I need to implement two methods removeFirst and removeLast of a LinkedList in Java

The first method i solved it like this:

@Override
public E removeFirst() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    E element = top.next.data;
    top.next = top.next.next;
    numElements--;
    return element;
}

I'm having problems with removeLast method

     public E removeLast() {
     if(isEmpty()){
         throw new NoSuchElementException();
     }

      for (int i = 0; i < numElements;i++) {


      }

}

My idea is using a for cycle to look for the last element, but i don't know what to do after that

Any suggestions?

My Node class is the following:

public class Node<E> {

E data;
Node<E> next; 

public Node(E data) {
    this(data,null);
}

public Node(E data, Node<E> next) {
    this.data = data;
    this.next = null;
}

@Override
public String toString () {
    return data.toString();


}

}

Upvotes: 1

Views: 5934

Answers (5)

steve
steve

Reputation: 1

public node removelast() {
    if(isEmpty())
        return null;
    node temp =head;
    node temp2 =head.getNext();
    while(temp!=null && temp2!=null) {
        if(temp2.getNext()==null) {
            tail=temp;
            temp.setNext(null);
        }
        temp2=temp2.getNext();
        temp=temp.getNext();
    }   
    if(head.getNext()==null)
        tail=head;
    return tail;
}

Upvotes: 0

RRIL97
RRIL97

Reputation: 868

This logic shall work -

Node <E> tmp;
tmp = next;


while(tmp.next.next != null)
tmp = tmp.next;
tmp.setNext(null);

So if we have 1->3->4->null

Whenever it gets to 3 it shall setNext to null so the new array will look like this 1->3->null

Upvotes: 0

Ravi Sharma
Ravi Sharma

Reputation: 170

We have to keep two pointers previous and current. Since we are keeping a record for the number of elements in the list we can use for loop to traversal the list and find the last node pointed by currentNode pointer and previous node pointed by previousNode pointer. At last, update the previous next pointer to null and return currentNode data.

 public E removeLast() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    Node previousNode = top;
    Node currentNode = top;
    for (int i = 0; i < numElements -1 ;i++) {
        previousNode = currentNode;
        currentNode = currentNode.next;
    }
    // removed the last element and return the data
    previousNode.next = null;
    numElements-- 
    return currentNode.data;

}

Upvotes: 3

Bill Shubert
Bill Shubert

Reputation: 536

Something like this may work, it's hard to say without seeing your list class because I can't test it:

  public E removeLast() {
    if(isEmpty()){
        throw new NoSuchElementException();
    }
    Node<E> node = top;
    while (true) {
      Node<E> nextNode = node.next;
      if (nextNode.next == null) {
        node.next = null;
        return nextNode.data;
      } else {
        node = nextNode;
      }
    }
  }

But it's worth adding that usually in a singly linked list, you want the containing class to keep a tail pointer (otherwise you can't append to the end efficiently). If you do this, you will need to update your tail as well.

And another comment, if you do find yourself removing the last on a regular basis, you want to switch to a doubly linked list...and why aren't you just using the builtin java.util.LinkedList class? Is this for a school project or something?

Upvotes: 0

Zelig
Zelig

Reputation: 1808

removeFirst and removeLast already exist in the LinkedList class (LinkedList javadoc). No need to create them from scratch then.

Upvotes: 0

Related Questions