Implementing a Node Removal Method in a Custom LinkedList Class in Java

Question

I'm working on a custom LinkedList implementation in Java and facing challenges with my remove method. The goal is to remove a node from the linked list and update the index values associated with each node. I'm unsure if my logic for updating the node indexes is correct.

Here's the key part of my code:

public class LinkedList<E> {
    LLNode<E> head;
    LLNode<E> tail;
    int llSize;

    // Constructor and other methods...

    public E remove(E data) {
        LLNode<E> nodeToRemove = findNode(data); // Assuming there's a method to find the node
        // Logic to remove the node and update indexes...
    }
}

public class LLNode<E> {
    E obj;
    LLNode<E> previousPointer;
    LLNode<E> nextPointer;
    int index;

    // Constructor and other methods...
}

My specific issues are with the logic in the remove method, especially in updating the index of each node after a removal. I have written some code for different cases (like when removing the head, a middle node, or the tail), but I'm not confident it's working as expected.

How should I correctly update the index of each node in the linked list after a removal?

Are there best practices or common pitfalls I should be aware of in implementing this functionality?

The LinkedList class is a custom implementation, not the Java standard library's LinkedList. I'm particularly struggling with the index updating part of the remove method.

Answer 1

You should only need to renumber the nodes that follow after the removed node.

So:

public E remove(E data) {
    LLNode<E> nodeToRemove = new LLNode<>(data);

    if(head == null){
        return null;
    }

    // Adapt head and tail when necessary
    if(tail.getObj().equals(nodeToRemove.getObj())){
        tail = nodeToRemove.previousPointer;
    }
    if(head.getObj().equals(nodeToRemove.getObj())){
        head = nodeToRemove.nextPointer;
    }

    // Rewire the list so it skips the node to remove
    if(nodeToRemove.nextPointer != null){
        nodeToRemove.nextPointer.previousPointer = nodeToRemove.previousPointer;
    }
    if(nodeToRemove.previousPointer != null){
        nodeToRemove.previousPointer.nextPointer = nodeToRemove.nextPointer;
    }

    // Renumber the nodes that follow the removed node. 
    // (Those before it retain their index)
    LLNode<E> currentNode = nodeToRemove.nextPointer;
    int index = nodeToRemove.getIndex();
    while (currentNode != null) {
        currentNode.setIndex(index);
        index++;
        currentNode = currentNode.nextPointer;
    }
    
    this.llSize--;
    return nodeToRemove.getObj();
}