Qual a diferença entre um array e uma lista encadeada?
Me lembro de ter ficado surpreso ao ter sido questionado sobre algo tão trivial. Queria responder quase que instintivamente, mas antes que eu pudesse abrir a boca me veio à cabeça: “Qual é?”.
Meu líder técnico na época me fez essa pergunta mostrando como era conduzida uma entrevista com qualquer dev que passava por ele (você pode estar aqui porque ele lhe fez essa pergunta!) e o quanto se conseguia inferir de um perfil baseado em uma pergunta que parece tão básica, mas que não é tão simples quanto parece.
Os conceitos de array e lista encadeada possuem muitas semelhanças, como a mutabilidade, capacidade de armazenamento indexável, iterabilidade e manuseabilidade. Mas suas diferenças podem fazer você ponderar entre qual escolher, principalmente se sua aplicação depender ferrenhamente de desempenho ou ser em baixo nível.
O quadro acima mostra bem as diferenças entre os dois tipos de dados; Todas essas diferenças, de alguma forma são relacionadas a como os dados se dispõem na memória, como mostra a imagem abaixo.
A utilização de ponteiros para indicar o próximo elemento na lista encadeada torna sua utilização mais dinâmica apesar de resultar em maior utilização da memória, devido à ocupação de 2 slots por elemento, sendo um para o ponteiro que aponta para próximo elemento e outro para o conteúdo; Enquanto o array é algo estático que ocupa menos memória, porém sendo mais rígido devido à alocação sequencial com número de elementos previamente estipulados dos slots ocupados.
A vantagem do array em relação à lista encadeada em sua indexação é a facilidade de localização do dado no contexto de recuperação e pesquisa, sendo bem performático devido à natureza estática da sua alocação. Enquanto a lista encadeada possui a dinamicidade do tamanho não fixo e o maior poder de manipulação, uma busca por um elemento específico é mais custosa.
À medida que o número de elementos aumenta, a complexidade da pesquisa de um elemento em uma lista encadeada aumenta, enquanto a de um array permanece. Isto é descrito em seu nível de complexidade em termos de busca, descrito pela notação Grande-O disposta no quadro abaixo.
Apesar das vantagens em relação a um array, na prática sua utilização é engessada e limitada, e é aí onde listas encadeadas aparecem mais como soluções em diversas aplicações, devido a facilidade no seu manuseio em relação à adição, e modificação de elementos e índices e sua diferença em performance na maioria das vezes não ser tão expressiva em relação a utilização de arrays, o que torna a discussão sobre qual tipo usar em um software dependendo da sua aplicação válida e relevante em termos de performance e mapeamento e recuperação de dados, afetando diretamente algoritmos.
É difícil dar uma resposta concisa para a pergunta, e o quanto você sabe sobre essas diferenças ou o que usa como resposta pode revelar o quão atento a detalhes você é, e quão suficiente é uma resposta para você.
Qualquer um dos itens citados pode ser utilizado para responder a pergunta, mas a intenção é perceber seu perfil através de qual resposta(s) você escolhe e como a(s) apresenta. Essa questão do mapeamento de perfil e o quão diferentes são as formas de se resolver o mesmo problema me fazem pensar sobre a real exatidão destas ciências e o que mais está envolvido em tudo que nós fazemos no dia a dia como analistas.
