Questão 67402

Uma professora de programação para um curso técnico está ensinando a diferença entre arrays (listas em Python) e listas encadeadas (linked lists). Ela quer que seus alunos compreendam os trade-offs de desempenho de cada estrutura de dados em relação a diferentes operações. Ela apresenta um trecho de um livro-texto: "Um **array** armazena seus elementos em um bloco contíguo de memória. Isso permite o acesso a qualquer elemento em tempo constante, $O(1)$, usando seu índice (ex: `array[i]`). No entanto, a inserção ou remoção de um elemento no meio do array é uma operação cara, com complexidade $O(n)$, pois pode exigir o deslocamento de todos os elementos subsequentes. Uma **lista encadeada**, por outro lado, armazena seus elementos em 'nós' que podem estar espalhados pela memória. Cada nó contém o dado e um ponteiro para o próximo nó. O acesso a um elemento pelo índice requer percorrer a lista desde o início, uma operação $O(n)$. No entanto, a inserção ou remoção de um elemento no meio da lista é muito eficiente, $O(1)$, se já tivermos um ponteiro para o nó anterior, pois requer apenas a atualização de alguns ponteiros, sem deslocamento de dados." A professora então propõe dois cenários de aplicação:

Cenário 1: Um sistema precisa armazenar uma coleção de 1 milhão de registros de clientes, e a operação mais comum é buscar um cliente rapidamente pelo seu número de ID (que pode ser usado como índice).

Cenário 2: Um editor de texto precisa gerenciar uma longa sequência de caracteres, onde as operações mais comuns são a inserção e a remoção de caracteres no local do cursor (no meio do texto).

Qual estrutura de dados seria mais apropriada para cada cenário, com base nos trade-offs de desempenho?