corresponde a um registro pre-definido que contem informacoes de tipos diferentes, permitindo desta forma, que se possa armazenar uma lista encadeada dentro da estrutura de matrizes Desta forma, para declarar uma lista encadeada vamos fazer da seguinte forma:Primeiro criamos o Registro para armazenar os dados da lista:REG_LISTA:REGISTROLETRA:CHARPROXIMO:INTEIROFIM_REGISTRODepois declaramos a lista pripriamento dita:LISTA:MATRIZ [ N ] DE REG_LISTAAlem de tudo isto , ainda existe um outro conceito a ser discutido, o valor NULO.O NULO e um valor especial que ira retornar todas as vezes que algum algoritmo tentar acessar um elemento alem do final da lista. O nulo e um valor que indica que nao existem mais posicoes a serem pesquisadas na lista . AtravessamentoAtravessar uma lista significa percorre-la , em ordem, de forma que cada um de seus elementos seja visitado uma unica vez.Como foi feito na Lista contigua, o atravessamento comeca pelo incio da lista e vai mostrando todos os seus elementos ate o final. A diferenca aqui , e que o atravessamento nao e feito pela ordem fisica , mas sim pela ordem logica.O atravessamento deve comecar pelo Descritor, e ir mostrado os elementos um por um , sempre indo para o proximo, ate que o proximo seja nulo.INICIOARGUMENTOSLISTA : MATRIZ [ N ] DE REG_LISTA {DECLARACAO DA LISTA }N :INTEIRO {NUMERO DE ELEMENTOS DA LISTA}DESCRITOR: INTEIRO {POSICAO FISICA DO INICIO DA LISTA}VARIAVEISREG_LISTA : REGISTROLETRA:CHAR {DECLARACAO DO REGISTRO DA LISTA}PROXIMO : INTEIROFIM_REGISTRO CONT:INTEIRO {VARIAVEL DE CONTROLE DO LOOP}PROCEDA ATRAVESSAMENTO_ENCASE DESCRITOR = NULOMOSTRE (LISTA VAZIA!!!!!)SENAOCONT: = DESCRITOR {INICIO DA LISTA}ENQUANTO CONT <> NULOMOSTRE (LISTA [CONT].LETRA) CONT : = LISTA [CONT].PROXIMOFIM_ENQUANTOFIM-SEFIM. Busca do Espaco Vazio.Nas listas encadeadas podera ocorrer uma situacao que nao era possivel nas lista contiguas:Na lista encadeada o algoritmo de exclusao podera deixar um elemento vazio no meio da lista, e neste caso , nos poderiamos aproveitar este espaco para fazer novas inclusoes na lista , evitando assim que a lista fique cheia de espacos em branco no transcorrer de diversas atualizacoes.Para tanto, sera necessario a criaao de um algoritmo capaz de identificar e reutilizar estes espacos em branco. Nos vamos chama-lo de ELEMENTO_VAZIO.Este algoritmo devera percorrer a lista pela ordem fisica, e procurar pelo primeiro espaco vazio que encontrar. Caso o algoritmo nao localize nenhum espaco vazio, ele devera "CRIAR" este espaco, simplesmente aumentando o numero de elementos da lista(N).INICIOARGUMENTOSLISTA : MATRIZ [N] DE REG_LISTA {DECLARACAO DA LISTA}N:INTEIRO {NUMERO DE ELEMENTOS DA LISTA}VARIAVEISREG_LISTA : REGISTROLETRA: CHAR {DECLARACAO DO REGISTRO DA LISTA}PROXIMO : INTEIROFIM_REGISTROCONT:INTEIRO {VARIAVEL DE CONTROLE DO LOOP}PROCEDA ELEMENTO_VAZIOCONT: = 1 ENQUANTO CONT < = N E LISTA [CONT].LETRA < > NULO CONT: = CONT + 1 {ATE ACABAR A LISTA OU ACHAR UM NOME NULO}FIM_ENQUANTOSE CONT > N N : = N + 1RETORNE (N) {NAO ACHOU ESPACO VAZIO E AUMENTOU A LISTA}SENAORETORNE (CONT) {ACHOU ESPACO VAZIO}FIM_SEFIM. Inclusao em Listas Encadeadas.O processo de inclusao de um elemento B , apos um elemento A , dentro de uma lista encadeada e feito da seguinte forma : Procura-se um elemento vazio Coloca-se ali a informacao do elemento B O proximo de B passa a ser o proximo de A