Delete Last Node of a Linked List

Question

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

Solution 1

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.

Solution 2

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

}

prev.next = null;

Try this:

Solution 3

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

Solution 4

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

Solution 5

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

View more solutions

Comments

[Calgar99]

Your right about if (prev.getNext() == null) { prev.setNext(null). Feeling pretty foolish about that. However is the do - while loop neccessary. It works with a regular while loop. Just want to make sure Im not missing anything.

[Calgar99]

What is the appropriate way of setting headOfList-> nextNode. I was trying this but to no avail.if(temp.getData().equals(str)) { if(temp.getData().equals(list.getData())) { temp.setNext(temp.getNext()); } else { prev.setNext(prev.getNext().getNext()); } }

[DwB]

Delete the node before entering the loop. It is a boundary condition.

[Calgar99]

Do you know what the appropriate syntax is? Sorry Ive been trying multiple approaches but I get the same result.

[OldCurmudgeon]

@Calgar99 - You can use any loop form you like so long as you a) visit every node and b) correctly deal with head, tail, empty list and one-entry list. It is worth trying a do loop to achieve a) sometimes.

[Calgar99]

Thanks for taking the time to help

[Alper Fırat Kaya]

if list contains 1 element then temp.next.next will refer to nothing and it will crash