Listas Encadeadas

Inserção:

• Primeiro atualize o novo nó inserido
• Em seguida modifique os nós desconhecidos (como x)
• Finalmente ajuste os nós conhecidos (como y, z)

Esta sequência pode ser aplicada a todas as operações lógicas de listas encadeadas

Remoção: Da mesma forma, quando não há novos nós adicionados, os nós desconhecidos são y e z, resultando na remoção do nó x.

Definição usando arrays simulados: Utilize os arrays prev[] e next[] para registrar predecessores e sucessores:

// Definindo nó cabeça
nodes[0].next = 1;
nodes[1].prev = 0, nodes[1].next = 0, nodes[1].value = 1;
// Onde nodes[1].next = 0 indica a cauda, ou seja, o ponto final do programa
// Percorrer
for (int current = nodes[0].next; current != 0; current = nodes[current].next) 
    cout << nodes[current].value << ' ';

Ambas as formas de percorrer verificam diretamente quem é o próximo nó, continuando até que o próximo não seja a cauda

Clique para ver o código

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e5 + 10;
int total, queries, value, position, next_node[MAX_SIZE], active[MAX_SIZE], prev_node[MAX_SIZE];

int main() {
    cin >> total;
    next_node[0] = 1;
    active[1] = 1;
    for(int i = 2; i <= total; ++i) {
        active[i] = 1;
        cin >> value >> position;
        
        if(!position) { // Inserir à esquerda
            next_node[prev_node[value]] = i;
            prev_node[i] = prev_node[value];
            prev_node[value] = i;
            next_node[i] = value;
        }
        else { // Inserir à direita
            prev_node[next_node[value]] = i;
            next_node[i] = next_node[value];
            next_node[value] = i;
            prev_node[i] = value;
        }
    }
    cin >> queries;
    for(int i = 1; i <= queries; ++i) {
        int target;
        cin >> target;
        if(!active[target]) continue;
        active[target] = 0;
        // Remover este elemento
        int temp = prev_node[target];
        next_node[prev_node[target]] = next_node[target];
        prev_node[next_node[target]] = temp;
    }
    // Percorrer a lista
    int current = next_node[0];
    while(current != 0) {
        cout << current << ' ';
        current = next_node[current];
    }
    cout << endl;
}

Usando estrutura de dados:

// Definindo nó cabeça
next_node[0] = 1;
next_node[1] = 0; // Indicando a cauda
// Percorrendo a lista
int current = next_node[0];
while(current != 0) {
    cout << current << ' ';
    current = next_node[current];
}

Clique para ver o código

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int data, previous, next;
};

ListNode nodes[1000010];
int count, operations, left_pos, right_pos;

void insert_node(int node_id, int reference, int side) { // Insere node_id à esquerda/direita de reference
    nodes[node_id].data = node_id;
    if(side == 0) { // Esquerda
        // Processar lado anterior
        nodes[node_id].previous = nodes[reference].previous;
        nodes[nodes[reference].previous].next = node_id;
        
        nodes[node_id].next = reference, nodes[reference].previous = node_id;
    }
    else { // Direita
        // Processar lado posterior
        nodes[nodes[reference].next].previous = node_id;
        nodes[node_id].next = nodes[reference].next;
        
        nodes[node_id].previous = reference, nodes[reference].next = node_id;
    }
}

void remove_node(int node_id) {
    nodes[node_id].data = -1;
    nodes[nodes[node_id].previous].next = nodes[node_id].next;
    nodes[nodes[node_id].next].previous = nodes[node_id].previous;
}

int main() {
    cin >> count;
    nodes[0].next = 1;
    nodes[1].previous = 0, nodes[1].next = 0, nodes[1].data = 1; // Lembre-se de definir também o valor
    
    for(int i = 2; i <= count; ++i) {
        cin >> left_pos >> right_pos;
        insert_node(i, left_pos, right_pos); // Valor, onde inserir
    }
    
    cin >> operations;
    while(operations--) {
        cin >> left_pos;
        if(nodes[left_pos].data == -1) continue;
        remove_node(left_pos);
    }
    
    for (int i = nodes[0].next; i != 0; i = nodes[i].next) 
        cout << nodes[i].data << ' ';
    
    return 0;
}

Por que existem dois métodos de inicialização do nó cabeça? O array apenas registra posições sem armazenar valores, enquanto a estrutura define uma tripla e next[1] = 0 registra o nó cauda para evitar erros de percurso e garantir a correta remoção dos nós.