Remove

Removes the element at the specified position in the list. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the node that was removed from the list.

public Node remove(int index) {
}

Case: Invalid index

If index is

• less than 0 or
• equal to than linked list length or
• greater than linked list length

simply return null

public class LinkedList {

    public Node remove(int index) {
        if (index < 0 || index >= length) return null;
    }
}

Case: Index is equal to zero

To remove element at beginning, simply perform a removeFirst() operation.

public class LinkedList {

    public Node remove(int index) {
        if (index < 0 || index >= length) return null;
        if (index == 0) {
            return removeFirst();
        }
    }
}

Case: Index is equal to length

To remove element at end, simply perform a removeLast() operation.

public class LinkedList {

    public Node remove(int index) {
        if (index < 0 || index >= length) return null;
        if (index == 0) {
            return removeFirst();
        } else if (index == length - 1) {
            return removeLast();
        }
    }
}

Case: Index is between zero and length of linked list

Consider following list.

Say you want to remove at index 3. All you need to is point node 2 to node 4 and node 3 to null. To do this you need to find the node before desired node (removing node).

Node pre = get(index - 1);

Now to get to desired node (say temp) you can simply traverse to pre’s next.

Node temp = pre.next;

pre’s next must point to temp’s next as you are removing temp node.

pre.next = temp.next;

All left to do is to set temp’s next to null.

temp.next = null;

Rearranging them

public class LinkedList {

    public Node remove(int index) {
        if (index < 0 || index >= length) return null;
        if (index == 0) {
            return removeFirst();
        } else if (index == length - 1) {
            return removeLast();
        } else {
            Node pre = get(index -1);
            Node temp = pre.next;

            pre.next = temp.next;
            temp.next = null;
            length--;
            return temp;
        }
    }
}

Testing

public class LinkedListTest {

    @Test
    void remove() {
        LinkedList linkedList = new LinkedList();
        linkedList.append(0);
        linkedList.append(1);
        linkedList.append(2);
        linkedList.append(3);
        linkedList.append(4);
        linkedList.append(5);
        linkedList.append(6);

        // when index is out of range
        assertNull(linkedList.remove(93));

        // when index is equal to zero
        assertEquals(0, linkedList.remove(0).getValue());
        assertEquals(List.of(1, 2, 3, 4, 5, 6), convertToArrayList(linkedList));

        // when index is equal to linked list length
        assertEquals(6, linkedList.remove(5).getValue());
        assertEquals(List.of(1, 2, 3, 4, 5), convertToArrayList(linkedList));

        // when index is in range
        assertEquals(4, linkedList.remove(3).getValue());
        assertEquals(List.of(1, 2, 3, 5), convertToArrayList(linkedList));
    }
}

Time Complexity

At worst case removing at desired index requires traversing through node’s next so, this operation has worst-case time complexity of O(n).