Este post tem o enfoque ao que é a estrutura de dado lista, mas, cada linguagem de programação pode representá-la ao seu modo, alterando brevemente alguma característica.

O que define uma lista

Estrutura com dados sequenciais, sem necessidade de ordem na inserção ordem, armazenamento ou remoção de dados

Pense numa prateleira onde você pode colocar e remover itens em qualquer posição.

Enquanto a fila (FIFO) e a pilha (LIFO) impõem regras rígidas de entrada e saída, a lista permite mais liberdade de manipulação, sendo boa para representar coleções dinâmicas de elementos.

Ela é uma estrutura linear, ainda que os elementos possam estar armazenados de forma não contígua na memória (dependendo da implementação). O acesso é feito via índice (em listas sequenciais) ou via ponteiros (em listas encadeadas).

A lista é uma das estruturas mais flexíveis e versáteis.

---

Tipos comuns de lista

Lista sequencial

• Implementada geralmente sobre um array.
• Os elementos são armazenados em posições contíguas na memória.
• Acesso por índice é rápido (O(1)), mas inserções/remoções no meio podem ser custosas, elas exigem deslocamento dos elementos.

Lista encadeada

• Cada elemento (nó) guarda o dado e uma referência para o próximo elemento.
• Não exige armazenar sequencialmente na memória.
• Inserções e remoções são rápidas, desde que você tenha a referência correta.
• Acesso por índice é mais lento (O(n)), pois é preciso percorrer a lista.

Lista duplamente encadeada

• Cada nó guarda referência para o próximo e para o anterior.
• Facilita a navegação nos dois sentidos.
• Consome um pouco mais de memória por causa das referências extras.

Lista circular

• Similar encadeada, duplamente ou não, a diferença é que o o último elemento aponta para o primeiro, formando um ciclo.
• Permite percorrer a lista de forma contínua, sem precisar reiniciar manualmente.

---

Operações comuns em uma lista

• INSERT: inserir elemento em posição específica.
• REMOVE: remover elemento de posição específica.
• GET: acessar elemento pelo índice ou posição.
• SIZE: retornar o tamanho da lista.
• EMPTY: verificar se está vazia.
• SEARCH: buscar elemento pelo valor.