Estruturas de Dados: Listas Encadeadas - Prof. Roger Silva

INSTITUTO FEDERAL Rio Grande do Sul Canoas ESTRUTURAS DE DADOS Listas Encadeadas Prof Roger Silva 20222 ESTRUTURAS DE DADOS Listas Encadeadas 1 Introdução 2 Armazenamento 3 Listas Encadeadas 4 Operações 5 Exercícios 1 INSTITUTO FEDERAL Rio Grande do Sul Canoas 1 Introdução INTRODUÇÃO Onde estamos Tipos de dados básicos int float char etc estruturados arrays matrizes struct union ponteiros malloc free a a ab etc abstratos datas pessoas listas etc 2 INTRODUÇÃO Onde estamos Algoritmos complexidade Of n Ωf n Θf n etc ordenação insertion sort bubble sort etc recursão hanoi merge sort quick sort etc busca linear e binária inserção e remoção 3 INTRODUÇÃO Aula de hoje O que é uma lista tipo abstrato de dado estrutura linear coleção ordenada ordered de itens pode ser vazia várias operações inserção remoção busca etc lista encadeada armazenamento encadeado 4 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INTRODUÇÃO Exemplos Exemplos de listas Menu lista de preços ingredientes passos Lista de tarefas compras serviços Voos cidades hotéis Clientes contatos Processos arquivos usuários etc 5 INSTITUTO FEDERAL Rio Grande do Sul Canoas 2 Armazenamento ARMAZENAMENTO Há pelo menos duas formas comuns de armazenar estruturas de dados na memória podemos armazenar um elemento ao lado do outro em uma região de memória limitada armazenamento contíguo ou podemos ir alocando e desalocando espaços de memória em locais aleatórios conforme a necessidade do programa armazenamento encadeado No caso de armazenamento contíguo a posição de cada elemento dentro da estrutura de dados que o contém é definida implicitamente pela própria posição desse elemento em memória Já no caso de armazenamento encadeado é necessário ir derreferenciando os ponteiros ou seja seguir o encadeamento para alcançar a posição desejada 6 ARMAZENAMENTO 1 2 3 4 5 6 7 8 1 5 4 6 7 3 8 2 9 10 armazenamento os elementos podem ser armazenados um ao lado do outro em uma região fixa ou podem ser espalhados na memória dinamicamente Exemplo um vetor com oito de dez posições ocupadas e uma lista encadeada com oito elementos 7 ARMAZENAMENTO Armazenamento contíguo O armazenamento contíguo tem algumas vantagens Proteção de memória porque é alocada antes da execução Velocidade transferência de dados por causa da cache Velocidade de acesso por causa da indexação Simples de trabalhar Representação natural de algumas estruturas simples Porém também traz alguns problemas Difícil compartilhar memória Tamanho fixo a priori Difícil usar com estruturas complexas Difícil incluir e excluir elementos 8 ARMAZENAMENTO Armazenamento encadeado Algumas vantagens das vantagens dos armazenamento encadeado Fácil compartilhar memória Estrutura mais dinâmica e flexível Fácil inserir e remover elementos Alguns dos seu problemas Transferência de dados mais lenta Necessário fazer o gerenciamento da memória É uma representação menos intuitiva Acesso serial sem o benefício da indexação 9 INSTITUTO FEDERAL Rio Grande do Sul Canoas 3 Listas Encadeadas LISTAS ENCADEADAS Nodo int valor Um simples nodo da lista Arquivo ListaContiguah 1 typedef struct 2 int valor 3 Nodo 10 LISTAS ENCADEADAS Nodo lista Nodo 0 int valor Nodo 1 int valor Nodo 2 int valor Nodo 3 int valor Nodo 4 int valor Nodo 5 int valor Uma lista contígua Arquivo ListaContiguah 1 typedef struct 2 int valor 3 Nodo 4 5 Uma Lista contígua é um 6 vetor de Nodos 7 Nodo lista 6 8 9 Podemos acessar assim 10 lista 10 valor 50 11 LISTAS ENCADEADAS Nodo int valor Nodo prox Um nodo com ponteiro Arquivo ListaEncadeadah 1 typedef struct nodo 2 int valor 3 struct nodo prox 4 Nodo 12 LISTAS ENCADEADAS Nodo lista Nodo 0 int valor Nodo prox Nodo 1 int valor Nodo prox Nodo 2 int valor Nodo prox Uma lista encadeada Arquivo ListaEncadeadah 1 typedef struct nodo 2 int valor 3 struct nodo prox 4 Nodo 5 6 Uma Lista é só um ponteiro 7 para o primeiro Nodo 8 Nodo lista declaracao 13 LISTAS ENCADEADAS Lista lista Nodo 1 int valor Nodo prox Nodo 2 int valor Nodo prox Nodo 3 int valor Nodo prox Uma lista encadeada Arquivo ListaEncadeadah 1 typedef struct nodo 2 int valor 3 struct nodo prox 4 Nodo 5 6 Então fica melhor assim 7 typedef Nodo Lista 8 Lista lista declaracao 14 LISTAS ENCADEADAS Lista lista Uma lista vazia Uma lista vazia é apenas um ponteiro para NULL Lista lista NULL 15 INSTITUTO FEDERAL Rio Grande do Sul Canoas 4 Operações OPERAÇÕES Armazenamento encadeado Arquivo ListaEncadeadah 16 Imprime os valores dos Nodos na tela 17 void imprimirLista lista 18 Insere um Nodo com valor em uma posição 19 Lista inserirLista lista int posicao int valor 20 Acessa o valor de um Nodo em uma posição 21 int pegarLista lista int posicao 22 Remove um Nodo de uma posição 23 Lista removerLista lista int posicao 24 Quantos Nodos tem na Lista 25 int comprimentoLista lista 26 Destrói todos os Nodos e deixa a Lista vazia 27 Lista limparLista lista 16 OPERAÇÕES Inserção no início Lista lista 0 1 2 inserir Nodo 0 como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista depois de conectar o novo Nodo aos outros 17 OPERAÇÕES Inserção no início Lista lista 0 1 2 x Nodo novo mallocsizeof novo novovalor valor Criar um novo Nodo inserir Nodo 0 como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista depois de conectar o novo Nodo aos outros 17 OPERAÇÕES Inserção no início Lista lista 0 1 2 x Nodo novo mallocsizeof novo novovalor valor novoprox lista Conectar ao primeiro Nodo da Lista inserir Nodo 0 como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista depois de conectar o novo Nodo aos outros 17 OPERAÇÕES Inserção no início Lista lista 1 2 3 0 Nodo novo mallocsizeof novo novovalor valor novoprox lista lista novo Reconectar a Lista ao novo primeiro Nodo inserir Nodo 0 como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista depois de conectar o novo Nodo aos outros 17 OPERAÇÕES Inserção em outro lugar Lista lista 0 1 2 inserir em outro lugar é preciso encontrar o Nodo imediatamente anterior conectar o novo Nodo ao próximo e reconectar o anterior 18 OPERAÇÕES Inserção em outro lugar Lista lista 0 1 2 anterior Encontrar o Nodo imediatamente anterior à posição desejada Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL inserir em outro lugar é preciso encontrar o Nodo imediatamente anterior conectar o novo Nodo ao próximo e reconectar o anterior 18 OPERAÇÕES Inserção em outro lugar Lista lista 0 1 2 x Criar um novo Nodo Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo novo mallocsizeof novo novovalor valor inserir em outro lugar é preciso encontrar o Nodo imediatamente anterior conectar o novo Nodo ao próximo e reconectar o anterior 18 OPERAÇÕES Inserção em outro lugar Lista lista 0 1 2 x Conectar o novo Nodo ao próximo Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo novo mallocsizeof novo novovalor valor novoprox anteriorprox inserir em outro lugar é preciso encontrar o Nodo imediatamente anterior conectar o novo Nodo ao próximo e reconectar o anterior 18 OPERAÇÕES Inserção em outro lugar Lista lista 0 1 3 2 Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo novo mallocsizeof novo novovalor valor novoprox anteriorprox anteriorprox novo Reconectar o Nodo anterior ao novo inserir em outro lugar é preciso encontrar o Nodo imediatamente anterior conectar o novo Nodo ao próximo e reconectar o anterior 18 OPERAÇÕES Remoção do início Lista lista 1 2 3 0 remover do início como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista antes de remover o Nodo 19 OPERAÇÕES Remoção do início Lista lista 1 2 3 0 Nodo deletar lista assertdeletar NULL Nodo deletar Marcar o Nodo para liberar mais tarde remover do início como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista antes de remover o Nodo 19 OPERAÇÕES Remoção do início Lista lista 0 1 2 x Nodo deletar lista assertdeletar NULL lista deletarprox Nodo deletar Reconectar o início da Lista remover do início como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista antes de remover o Nodo 19 OPERAÇÕES Remoção do início Lista lista 0 1 2 Nodo deletar lista assertdeletar NULL lista deletarprox freedeletar Liberar a memória do Nodo remover do início como a Lista aponta para o primeiro Nodo é preciso atualizar o próprio ponteiro da Lista antes de remover o Nodo 19 OPERAÇÕES Remoção de outro lugar Lista lista 1 2 3 0 remover de outro lugar é preciso encontrar o Nodo imediatamente anterior e reconectar ele antes de remover o Nodo 20 OPERAÇÕES Remoção de outro lugar Lista lista 1 2 3 0 anterior Encontrar o Nodo imediatamente anterior à posição desejada Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL remover de outro lugar é preciso encontrar o Nodo imediatamente anterior e reconectar ele antes de remover o Nodo 20 OPERAÇÕES Remoção de outro lugar Lista lista 1 2 3 0 anterior Marcar o Nodo seguinte para liberar mais tarde Nodo deletar Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo deletar anteriorprox assertdeletar NULL remover de outro lugar é preciso encontrar o Nodo imediatamente anterior e reconectar ele antes de remover o Nodo 20 OPERAÇÕES Remoção de outro lugar Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo deletar anteriorprox assertdeletar NULL anteriorprox deletarprox Lista lista 1 x 2 0 Reconectar o Nodo anterior Nodo deletar remover de outro lugar é preciso encontrar o Nodo imediatamente anterior e reconectar ele antes de remover o Nodo 20 OPERAÇÕES Remoção de outro lugar Nodo anterior lista assertanterior NULL for int i 0 i posicao1 i anterior anteriorprox assertanterior NULL Nodo deletar anteriorprox assertdeletar NULL anteriorprox deletarprox freedeletar Lista lista 1 2 0 Liberar a memória do Nodo remover de outro lugar é preciso encontrar o Nodo imediatamente anterior e reconectar ele antes de remover o Nodo 20 INSTITUTO FEDERAL Rio Grande do Sul Canoas 5 Exercícios EXERCÍCIOS 1 Crie uma lista encadeada com três Nodos de maneira estática sem usar malloc ou algo parecido 2 Implemente a operação imprimir e teste com a sua lista estática Essa operação deve mostrar algo do tipo 10 20 30 NULL 3 Implemente a operação comprimento Qual é a complexidade dessa operação 4 Implemente as operações inserir e remover que estão descritas nos slides e teste com alguns números Qual é a complexidade dessas operações 5 Implemente a operação limpar removendo o primeiro Nodo até que não reste nenhum Qual é a complexidade dessa operação 21 EXERCÍCIOS 6 Insira 100 mil inteiros em uma lista todos na primeira posição Quanto tempo leva 7 Agora insira 100 mil inteiros todos na primeira posição e insira mais um inteiro na última posição posição 100 mil Quanto tempo leva Por quê 8 Agora tente inserir os mesmos 100 mil inteiros mas o primeiro na posição 0 o segundo na posição 1 e assim por diante Quanto tempo leva Por quê 9 Implemente a operação pegar usando um laço 10 Agora implemente a operação pegar de maneira recursiva Qual a complexidade dessa operação 11 Qual é a melhor posição para inserir ou remover Nodos 22