Lista Encadeada: Estrutura, Operações e Implementação em C

Introdução Estrutura de lista São sequências de elementos Ei Utiliza ponteiros Pi para referenciar o próximo elemento da sequência E1 P1 E2 P2 En1 Pn1 En Pn NULL C 2022 Bruno Prado Departamento de Computação UFS 2 51 Introdução Lista encadeada Armazenamento descontínuo em memória Tempo de acesso sequencial E1 P1 E2 P2 En1 Pn1 En Pn NULL Vetor Armazenamento contínuo em memória Tempo de acesso constante E1 E2 En1 En 0 1 n2 n1 C 2022 Bruno Prado Departamento de Computação UFS 3 51 Introdução Lista encadeada Armazenamento descontínuo em memória Tempo de acesso sequencial E1 P1 E2 P2 En1 Pn1 En Pn NULL Vetor Armazenamento contínuo em memória Tempo de acesso constante E1 E2 En1 En 0 1 n2 n1 C 2022 Bruno Prado Departamento de Computação UFS 4 51 Introdução Operações principais Busca Inserção Remoção Modificação C 2022 Bruno Prado Departamento de Computação UFS 5 51 Lista encadeada Coleção de elementos Cabeça primeiro elemento da lista Cauda último elemento da lista E1 P1 E2 P2 En1 Pn1 En Pn NULL Cabeça Cauda Cada elemento possui somente um ponteiro unidirecional para o próximo elemento da sequência C 2022 Bruno Prado Departamento de Computação UFS 6 51 Lista encadeada Coleção de elementos Cabeça primeiro elemento da lista Cauda último elemento da lista E1 P1 E2 P2 En1 Pn1 En Pn NULL Cabeça Cauda Cada elemento possui somente um ponteiro unidirecional para o próximo elemento da sequência C 2022 Bruno Prado Departamento de Computação UFS 7 51 Lista encadeada Implementação em C Definição do elemento 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Valor 7 uint32t E 8 Ponteiro 9 elemento P 10 elemento C 2022 Bruno Prado Departamento de Computação UFS 8 51 Lista encadeada Implementação em C Definição da lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de lista 5 typedef struct lista 6 Ponteiro 7 elemento L 8 lista C 2022 Bruno Prado Departamento de Computação UFS 9 51 Lista encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada NULL C 2022 Bruno Prado Departamento de Computação UFS 10 51 Lista encadeada Inserção É feita a alocação dinâmica do elemento O ponteiro é atualizado para referenciar o novo elemento inserido na lista E1 P1 NULL C 2022 Bruno Prado Departamento de Computação UFS 11 51 Lista encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada E1 P1 E2 P2 NULL C 2022 Bruno Prado Departamento de Computação UFS 12 51 Lista encadeada Inserção É feita a alocação dinâmica do elemento O ponteiro é atualizado para referenciar o novo elemento inserido na lista E1 P1 E2 P2 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 13 51 Lista encadeada Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 14 51 Lista encadeada Remoção É feita a busca pelo valor do elemento E2 O ponteiro P1 é preparado para remoção E1 P1 E2 P2 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 15 51 Lista encadeada Remoção É removido da sequência o elemento E2 O ponteiro P1 é atualizado para referenciar o elemento E3 que é o sucessor do elemento removido E1 P1 E3 P3 NULL E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 16 51 Lista encadeada Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 17 51 Lista encadeada Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro P1 é armazenado E1 P1 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 18 51 Lista encadeada Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado E1 P1 E3 P3 NULL C 2022 Bruno Prado Departamento de Computação UFS 19 51 Lista encadeada Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 20 51 Lista circular É uma lista encadeada cíclica As operações são equivalentes as realizadas nas listas encadeadas mantendo o ponteiro do último elemento apontando para o primeiro E1 P1 E2 P2 En1 Pn1 En Pn C 2022 Bruno Prado Departamento de Computação UFS 21 51 Lista circular Inserção Como não existem elementos em uma lista vazia não existe a referência circular NULL C 2022 Bruno Prado Departamento de Computação UFS 22 51 Lista circular Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 23 51 Lista circular Inserção É feita a alocação dinâmica do elemento O novo elemento é apontado e faz referência ao primeiro elemento da lista E1 P1 E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 24 51 Lista circular Inserção É feita a alocação dinâmica do elemento O novo elemento é apontado e faz referência ao primeiro elemento da lista E1 P1 E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 25 51 Lista circular Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 26 51 Lista circular Remoção É feita a busca pelo valor do elemento E1 O ponteiro da lista é preparado para remoção E1 P1 E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 27 51 Lista circular Remoção É removido da sequência o elemento E1 O ponteiro da lista é atualizado para referenciar o elemento E2 e assim como o último elemento E3 E2 P2 E3 P3 E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 28 51 Lista circular Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 29 51 Lista circular Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro P2 é armazenado E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 30 51 Lista circular Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado E2 P2 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 31 51 Lista circular Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 32 51 Lista duplamente encadeada Lista encadeada com dois ponteiros Ponteiros do elemento referenciam o elemento anterior e próximo da sequência Navegação em ambas direções A1 E1 P1 A2 E2 P2 An1 En1 Pn1 An En Pn C 2022 Bruno Prado Departamento de Computação UFS 33 51 Lista duplamente encadeada Implementação em C Definição do elemento 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de elemento 5 typedef struct elemento 6 Valor 7 uint32t E 8 Ponteiro para anterior 9 elemento A 10 Ponteiro para próximo 11 elemento P 12 elemento C 2022 Bruno Prado Departamento de Computação UFS 34 51 Lista duplamente encadeada Implementação em C Definição da lista 1 Padrão de tipos por tamanho 2 include stdinth 3 4 Estrutura de lista 5 typedef struct lista 6 Ponteiro 7 elemento L 8 lista C 2022 Bruno Prado Departamento de Computação UFS 35 51 Lista duplamente encadeada Inserção A cabeça da lista é acessada É feita a busca do ponteiro para o próximo elemento até que uma referência nula seja encontrada NULL C 2022 Bruno Prado Departamento de Computação UFS 36 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 C 2022 Bruno Prado Departamento de Computação UFS 37 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 A2 E2 P2 C 2022 Bruno Prado Departamento de Computação UFS 38 51 Lista duplamente encadeada Inserção É feita a alocação dinâmica do elemento Os ponteiros são atualizados para referenciar o novo elemento inserido na lista A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 39 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Inserção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 40 51 Lista duplamente encadeada Remoção É feita a busca pelo valor do elemento E2 Os ponteiros P1 e A3 são preparados para remoção A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 41 51 Lista duplamente encadeada Remoção O elemento E2 é removido da sequência Os ponteiros P1 e A3 são atualizados A1 E1 P1 A2 E2 P2 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 42 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Remoção Θ1 C 2022 Bruno Prado Departamento de Computação UFS 43 51 Lista duplamente encadeada Modificação É feita a busca pelo valor do elemento E3 O valor do ponteiro A1 ou P1 é armazenado A1 E1 P1 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 44 51 Lista duplamente encadeada Modificação A estrutura do elemento E3 é acessado através de sua referência e o seu valor é atualizado A1 E1 P1 A3 E3 P3 C 2022 Bruno Prado Departamento de Computação UFS 45 51 Lista duplamente encadeada Análise de complexidade Busca Ω1 e On Modificação Θ1 C 2022 Bruno Prado Departamento de Computação UFS 46 51 Aplicacoes Vantagens V Permite alocacdo descontinua e incremental de memoria sem necessidade de realocado V Realizacdo de operacées de insercdo de remocgdao e de modificagao em tempo constante C 2022 Bruno Prado Departamento de Computaao UFS 4751 Aplicacoes Vantagens V Permite alocacdo descontinua e incremental de memoria sem necessidade de realocado V Realizacdo de operacées de insercdo de remocgdao e de modificagao em tempo constante Desvantagens X Necessidade de busca sequencial para realizagao das operagoes sobre elementos xO espaco utilizado pelos ponteiros por ser maior que o dado armazenado como o tipo caractere C 2022 Bruno Prado Departamento de Computado UFS 4851