Trabalhos

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO AMAPÁ
LICENCIATURA EM INFORMÁTICA
DOCENTE: LUÍS
DISCENTE: DORA ALVES MACEDO MARCO ANTONIO DE OLIVEIRA PALHETA

ESTRUTURA DE DADOS C/C++

MACAPÁ-AP
2014
Lista ligada ou Lista encadeada
É uma estrutura de dados linear e dinâmica. Ela é composta por uma sequência de nodos ou células que contém seus dados e também uma ou duas referências ("links") que apontam para o nodo anterior ou posterior. Há diversos modelos de lista ligadas como lista-encadeada simples, listas duplamente ligadas e listas encadeadas circulares.
Para se "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. O esquema a seguir representa uma lista ligada com 5 elementos:
Célula 1 ---> Célula 2 ---> Célula 3 ---> Célula 4 ---> Célula 5 ---> (Nulo)
Para manipularmos estas listas nomeadamente: inserir dados ou remover dados temos que ter sempre em atenção em ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, isto porque se queremos inserir ou apagar dados que estão no inicio ou no fim da lista então a operação é rápidamente executada caso seja um nó que esteja no meio da lista pois terá que haver uma procura até encontrar a posição desejada.
Diagrama conceitual de uma lista ligada

Lista encadeada simples
Uma lista encadeada simples é aquela que contém apenas um link por nodo. Este link aponta para o próximo nodo da lista, ou para um valor nulo (vazio) quando se trata do nodo final.

Lista encadeada simples com três valores inteiros

Lista duplamente encadeada
Listas duplamente encadeadas ou lista de duas vias, são um modelo mais sofisticado das listas simples: cada nodo possui dois ponteiros - um que aponta para o nodo anterior (ou null se é o primeiro valor ou a lista está vazia) e outro que aponta