Lista ligada

Uma lista encadeada ou lista ligada é uma estrutura de dados linear e dinâmica. Ela é composta por várias células que estão interligadas através de ponteiros, ou seja, cada célula possui um ponteiro que aponta para o endereço de memória da próxima célula. Desse modo, as células da estrutura não precisam estar em posições contíguas da memória. Isso faz com que a estrutura se torne dinâmica, pois há qualquer momento, é possível alocar uma nova célula e mudar os ponteiros das células já existentes, de modo que a nova célula seja inserida na estrutura com êxito, na posição desejada pelo programador. Ao lado temos um exemplo de uma lista encadeada. Nela, cada célula aponta para o endereço de memória da próxima célula através de um ponteiro. Como o último elemento da lista (célula 5) não possui próximo, ele apontará para nulo, que representa uma posição inválida na memória que não pode sofrer escrita ou ser dereferenciada. Para inserir dados ou remover dados é necessário, no mínimo, um ponteiro que aponta para a primeira célula da lista. Esse ponteiro é normalmente chamado de head. A partir dele, podemos acessar a segunda célula, e a partir da segunda célula, podemos acessar a terceira, e assim em diante. Ou seja, com o ponteiro para a primeira célula, podemos acessar qualquer célula de uma lista encadeada.