Remove Last

• Removes last element (element referenced by tail) from linked list

public Node removeLast() {
}

Case: Linked List is empty

Simply return null as there is no element to delete.

public class LinkedList {
    
    public Node removeLast() {
        if (length == 0) {
            return null;
    }
}

Case: Linked List is not empty

To get to the last node, you need to start with head and navigate along its next value. You repeat this process until the next value is null.

While removing the last element, you also need to keep track of second last node as tail needs to point to this node (remember tail always points to last node).

public class LinkedList {
    
    public Node removeLast() {
        if (length == 0) {
            return null;
        } else {
            Node pre = head; // holds node before curr (eventually second last element)
            Node curr = head; // holds current node (eventually last element)
            while (last.next != null) {
                pre = curr;
                curr = curr.next;
            }
        }
    }
}

Let’s have a closer look at while block

Node pre = head;
Node curr = head;
while (curr.next != null) {
    pre = curr;
    curr = curr.next;
}

This code block basically navigates along head’s next and its next and so on until it encounters null (i.e. end of linked list).

Step One

Initially pre (second last) and curr (last) both starts from first node.

Step Two

Step Three

Step Four

After this step condition curr.next != null doesn’t satisfy as curr points to node with value 4 whose next’s is null. At this stage you have the last and second last element, only thing left now is to set the second last node’s next (pre’s next) to null.

pre.next = null;

Since pre is now the last element, tail must also reference to pre.

tail = pre;

Also, decrement the length of linked list.

length--;

Combine the above logic.

public class LinkedList {
    
    public Node removeLast() {
        if (length == 0) {
            return null;
        } else {
            Node pre = head; // holds node before curr (eventually second last element)
            Node curr = head; // holds current node (eventually last element)
            while (last.next != null) {
                pre = curr;
                curr = curr.next;
            }
            pre.next = null;
            tail = pre;
            length--;
            return curr; // returning the removed node
        }
    }
}

You also need to handle another edge case when linked list contains exactly one element. In such case simply set head and tail to null.

public class LinkedList {
    
    public Node removeLast() {
        if (length == 0) {
            return null;
        } else {
            Node pre = head;
            Node curr = head;
            while (last.next != null) {
                pre = curr;
                curr = curr.next;
            }
            pre.next = null;
            tail = pre;
            length--;
            if (length == 0) { // since length is decremented by 1 above, it means linked list had length 1
                head = null;
                tail = null;
            }
            return curr; 
        }
    }
}

Testing

public class LinkedListTest {

    @Test
    void removeLast() {
        LinkedList linkedList = new LinkedList();
        //  remove from empty linked list should return null
        assertNull(linkedList.removeLast());

        // remove when list consists one element
        linkedList.append(1);
        linkedList.removeLast();
        assertEquals(0, linkedList.getLength());

        // remove on list with length greater than one
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        var temp = linkedList.removeLast();
        assertEquals(3, linkedList.getLength());
        assertEquals(4, temp.getValue());
        assertEquals(List.of(1, 2, 3), convertToArrayList(linkedList));
    }
}

Time complexity

Removing an element from the end of a linked list has linear worst-case time complexity - O(n) as you need to navigate linked list to find last node.