Uma lista encadeada é uma representação de uma sequência de objetos na memória do computador. Cada elemento da sequência é armazenado em uma célula da lista: o primeiro elemento na primeira célula, o segundo na segunda e assim por diante.

Uma lista encadeada é linear e dinâmica, composta por nós que apontam para o próximo elemento da lista, o ultimo elemento apontará para nulo (ou de volta para o primeiro, dependendo da implementação). Para compor uma lista encadeada, basta guardar seu primeiro elemento, embora as implementações mais comuns também guardem o último (de modo a poder inserir no final da lista em tempo constante). Às vezes se usa um elemento especial, chamado "sentinela", que não contém valor e serve somente para que a lista vazia não fique sem nenhum nó.

Uma lista pode ser simplesmente encadeada (se cada nó só aponta pro "próximo") ou duplamente encadeada (se cada nó também aponta pro "anterior"). Dessa forma troca-se uma memória adicional por nó pela capacidade de percorrer a lista na ordem inversa com o mesmo custo computacional de fazê-lo em ordem direta.

Ver também: