O que acontece dentro de uma lista ligada quando insere um novo elemento exatamente no seu meio?

Ao inserir um novo elemento no meio de uma lista ligada, vários passos são realizados:

1. Um novo nó é criado com o valor necessário.
2. Encontra-se o nó após o qual o novo deve ser inserido (por exemplo, o nó com índice n).
3. O novo nó recebe uma referência ao próximo nó após o encontrado (ou seja, newNode.next = current.next).
4. A referência do nó atual é atualizada para apontar para o novo nó (current.next = newNode).

Dessa forma, o novo elemento é inserido entre dois nós existentes, e a cadeia de referências é preservada.

Exemplo em Java:

class Node {
    int value;
    Node next;
    Node(int val) { value = val; }
}

void insertAfter(Node current, int newValue) {
    Node newNode = new Node(newValue);
    newNode.next = current.next;
    current.next = newNode;
}