CODEWITHSUNDEEP
javalinked-listnodes
Calgar99
Calgar99

Reputation: 1688

Delete Last Node of a Linked List

I am practicing working with Linked List Nodes and have come upon a problem I don't know how to answer. How do you go about deleting the last node in a linked list. The code below works for all entry's bar the last node. The last does not get deleted.

Node Class

public class Node {

    private String data;
    private Node next;

    Node(String data, Node next)
    {
        this.data = data;
        this.next = next;
    }

    public void setData(String d)
    {
        data = d;
    }

    public void setNext(Node n)
    {
        next = n;
    }

    public String getData()
    {
        return data;
    }

    public Node getNext()
    {
        return next;
    }

Main

Node list = new Node("NODE 1",new Node("NODE 2",new Node("NODE 3", null)));
        list = insertSecond(list,"New Node");
        list = addLast(list,"LAST NODE");

        printList(list);
        System.out.println();
        deleteNode(list,"LAST NODE");
        printList(list);    
    }

    public static Node deleteNode(Node list,String str)
    {
        Node temp = list;
        Node prev = list;

        while(temp.getNext() != null)
        {
            if(temp.getData().equals(str))
            {
                if(prev.getNext() == null)
                    prev.setNext(null);
                else{
                prev.setNext(prev.getNext().getNext());
                }

            }
            prev = temp;
            temp = temp.getNext();
        }

Upvotes: 2

Views: 58385

Answers (15)

Init_One
Init_One

Reputation: 1

This is way more simpler and perfectly works.
public void deleteLastNode() {
    Node curr = head;
    Node prevNode = null;
    if(head == null) return;
    while(curr != null && curr.next != null) {
        prevNode = curr;
        curr = curr.next;
    }
    if(head.next != null) prevNode.next = null;
    else head = null;
}

Upvotes: 0

kundan kumar
kundan kumar

Reputation: 1

This Will Work :)

public void deleteFromLast()
{   Node secondLastNode=null;
    Node currentNode=first;
    while(currentNode.next!=null)
    {   secondLastNode=currentNode;
        currentNode=currentNode.next;
        if(currentNode.next==null)
        {
            secondLastNode.next=null;;
            break;
        }
    }
}

Upvotes: 0

AmbujaAK
AmbujaAK

Reputation: 1

/**
 * Deletion From End
 */
public static LinkedList DeletionFromEnd(LinkedList list){
    Node currNode = list.head;
    Node prevNode = null;

    while( currNode.getNext() != null) {
        prevNode = currNode;
        currNode = currNode.getNext();
    }
    prevNode.setNext(null);

    return list;
}

Upvotes: 0

ajurge
ajurge

Reputation: 1

Given the following singly linked list implementation the last node can be removed using removeLast() or removeLastRecursive() methods that are traversing the list starting form the first node:

public class LinkedList<T> {
    Node<T> first;
    Node<T> last;
    int length;

    public LinkedList() {

    }

    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        linkedList.add("D");

        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
        linkedList.removeLast();
        linkedList.printListParams();
    }

    public void add(T data) {
        if (isEmpty()) {
            first = new Node(data);
            last = first;
        } else {
            last.next = new Node(data);
            last = last.next;
        }
        length++;
    }

    public void removeLast() {
        Node current = first;
        if (isEmpty()) return;
        if (current.next != null) {
            while (current.next != null) {
                if (current.next.next == null) {
                    current.next = null;
                    last = current;
                    length--;
                    return;
                }
                current = current.next;
            }
        } else {
            first = null;
            last = null;
            length--;
        }
    }

    public void removeLastRecursive() {
        if (isEmpty()) return;
        if (first.next != null) {
            removeLast(first);
        } else {
            first = null;
            last = null;
            length--;
        }
    }

    private void removeLast(Node node) {
        if (node.next.next != null) {
            removeLast(node.next);
        } else {
            node.next = null;
            last = node;
            length--;
            return;
        }
    }

    public boolean isEmpty() {
        return first == null;
    }

    public void printList() {
        Node current = first;
        while (current != null) {
            System.out.print(current.data);
            current = current.next;
        }
        System.out.println();
    }

    public void printListParams() {
        printList();
        System.out.println("Length: " + length);
        System.out.println("Last node data: " + ((last != null) ? last.data : last));
        System.out.println("***********************");
    }

    private class Node<T> {
        T data;
        Node next;

        public Node(T data) {
            this.data = data;
        }
    }

}

Upvotes: 0

Sriharsha g.r.v
Sriharsha g.r.v

Reputation: 510

public  Node deleteEnd(Node node)

{

if(node==null)

{

  throw new IllegalStateException();

}

    if(node.getNext()==null)
    return null;

    Node headF=node;

    while (node.getNext().getNext()!=null)
    {
        node=node.getNext();
    }
    node.setNext(null);
    return headF;

}

Upvotes: 0

Kalpa Gunarathna
Kalpa Gunarathna

Reputation: 1107

The logic is simple here and it is the same as getting the last node. The tricky thing here is to when you reach the last node, you will have to remember the node before the last and set it to null so that it will be the new last node. In the code below when you reach the last element which will be n2 get n1 and set it to null.

public void removeLast(){
    if(head==null) System.out.println("List is empty");
    else {
    Node n1 = null;
    Node n2 = head;
        while(n2.next != null)
        {
            n1 = n2;
            n2 = n2.next;
        }
        n1.next = null;
    }

Upvotes: 0

gopalaa
gopalaa

Reputation: 1

This one worked for me.. 

public void removeLastNode(){
    System.out.println("\n Inside removeLastNode");
    next=firstLink;
    prev=firstLink;
    if(next == null) System.out.println("\n The link List is Empty");
    while(next.getNext()!=null) { 
        prev=next;
        next=next.getNext();
    }
    prev.setNext(null);  
}

Upvotes: 0

Georgi Koemdzhiev
Georgi Koemdzhiev

Reputation: 11931

This is very simple technique that I used to delete the last Node.

public void deleteLast() {
    Node curr = null;

    for (curr = this.first; curr.next.next != null;curr = curr.next) {

    }

    curr.next = null;
}

Upvotes: 4

Debasis
Debasis

Reputation: 3740

This can be done in a much simpler way by using the Java container class "LinkedList". The class LinkedList in Java implements the Deque (Double ended queue) interface which supports get/add/remove First/Last methods. An elementary code snippet follows:

LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);
list.addLast(2);
System.out.println(list.removeLast());

Upvotes: 0

Here to Learn.
Here to Learn.

Reputation: 693

This is my attempt at it with assumption that last node's next variable will always be null:

public class LastNodeRemoval {

  private static class Node {
      String item;
      Node next;
  }

  public static void main(String[] args) {
      Node third = new Node();
      third.item = "Third";

      Node second = new Node();
      second.item = "Second";
      second.next = third;

      Node first = new Node();
      first.item = "First";
      first.next = second;

      removalLastNode(first);
   }

   private static void removalLastNode(Node first) {
      Node temp = first;

      while(temp.next.next != null) {
          temp = temp.next;
      }

      temp.next = null;

      System.out.println("Last node: "+temp.item);
   }

}

Upvotes: 0

DwB
DwB

Reputation: 38300

Deleting a node in a singly linked list

Assumptions

  1. Each node in the list has a nextNode pointer.
  2. The headOfList pointer points to the first node in the list.
  3. The next pointer of each node, that is already in the list, is correct.
  4. The next pointer of the last node in the list is some meaningful value (for instance, null).

Steps to implement

  1. If the list is empty, done. Desired node not found.
  2. If the first node is the desired node, set the headOfList pointer to the headOfList->nextNode value. Done. Desired node found.
  3. Set the currentNode pointer equal to the headOfList pointer value.
  4. If the currentNode node is the last node. Done. Desired node not found.
  5. If the currentNode->nextNode node is the desired node, set the currentNode->nextNode to the currentNode->nextNode->nextNode value. Done. Desired node found.
  6. goto step 4.

Notes

Since this is a singly linked list, you can not back up. Because of this, you need to point to the node parent and check to see if the the node child is the node that you wish to delete. There will be boundry conditions.

Some code

This is a member function of a LinkedList class. startOfList is a class member and points to the start of the linked list.

 public boolean delete(final String target)
    {
        if (startOfList != null)
        {
            if (StringUtils.equals(startOfList.getData(), target))
            {
                startOfList = startOfList.getNext();
                return true;
            }

            Node current = startOfList;

            for (Node next = current.getNext(); next != null; next = current.getNext())
            {
                if (StringUtils.equals(next.getData(), target))
                {
                    current.setNext(next.getNext());
                    return true;
                }
                else // advance one node.
                {
                    current = next;
                }
            }
        }

        return false;
    }

Upvotes: 1

Achintya Jha
Achintya Jha

Reputation: 12843

while(temp != null){
  prev = temp;
  temp = temp.getNext();

}

prev.next = null;

Try this:

Upvotes: 5

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

You need something like this:

public static Node deleteNode(Node list, String str) {
  Node temp = list;
  Node prev = list;

  do {
    if (temp.getData().equals(str)) {
      if (prev.getNext() == null) {
        prev.setNext(null);
      } else {
        prev.setNext(prev.getNext().getNext());
      }
    }
    prev = temp;
    temp = temp.getNext();
  } while (temp != null);

  return list;
}

You were stopping your loop too early.

BTW: if (prev.getNext() == null) { prev.setNext(null); ... doesn't make sense but I'll leave that bug to you.

Upvotes: 1

Kai
Kai

Reputation: 39641

I would guess while(temp.getNext() != null) fails for your last element. The last element won't have a next element. So the last element is not compared against the passed string. You should trace this with the debugger.

Upvotes: 1

Sean Patrick Floyd
Sean Patrick Floyd

Reputation: 298898

It's easiest if you use a doubly-linked List, where your list knows both start and end.

Then you can just do something like this:

public void removeLastItem(){
    this.lastNode = this.lastNode.prev;
}

Upvotes: 3

Related Questions