Lista encadeada

Uma lista vinculada é uma sequência de nós que contêm dois campos: um valor inteiro e um link para o próximo nó. O último nó está ligado a um terminador usado para significar o fim da lista.

Na ciência da computação, uma lista encadeada é uma coleção linear de elementos de dados cuja ordem não é dada por seu posicionamento físico na memória. Em vez disso, cada elemento aponta para o próximo. É uma estrutura de dados que consiste em uma coleção de nós que, juntos, representam uma sequência. Em sua forma mais básica, cada nó contém: dados e uma referência (em outras palavras, um link) para o próximo nó na sequência. Essa estrutura permite a inserção ou remoção eficiente de elementos de qualquer posição na sequência durante a iteração. Variantes mais complexas adicionam links adicionais, permitindo inserção ou remoção mais eficiente de nós em posições arbitrárias. Uma desvantagem das listas encadeadas é que o tempo de acesso é linear (e difícil de canalizar). Acesso mais rápido, como acesso aleatório, não é viável. Arrays têm melhor localização de cache em comparação com listas encadeadas.

As listas encadeadas estão entre as estruturas de dados mais simples e comuns. Eles podem ser usados para implementar vários outros tipos de dados abstratos comuns, incluindo listas, pilhas, filas, matrizes associativas e expressões S, embora não seja incomum implementar essas estruturas de dados diretamente sem usar uma lista encadeada como base.

O principal benefício de uma lista encadeada sobre um array convencional é que os elementos da lista podem ser facilmente inseridos ou removidos sem realocação ou reorganização de toda a estrutura porque os itens de dados não precisam ser armazenados continuamente na memória ou no disco, enquanto reestruturar um array em tempo de execução é uma operação muito mais cara. As listas vinculadas permitem a inserção e remoção de nós em qualquer ponto da lista e permitem fazer isso com um número constante de operações, mantendo o link anterior ao link que está sendo adicionado ou removido na memória durante a travessia da lista.

Por outro lado, como as listas encadeadas simples por si só não permitem acesso aleatório aos dados ou qualquer forma de indexação eficiente, muitas operações básicas - como obter o último nó da lista, encontrar um nó que contenha um determinado datum ou localizar o local onde um novo nó deve ser inserido - pode exigir a iteração na maioria ou em todos os elementos da lista.

História

As listas encadeadas foram desenvolvidas em 1955–1956, por Allen Newell, Cliff Shaw e Herbert A. Simon na RAND Corporation e na Carnegie Mellon University como a estrutura de dados primária para sua Linguagem de Processamento de Informações. O IPL foi usado pelos autores para desenvolver vários programas iniciais de inteligência artificial, incluindo o Logic Theory Machine, o General Problem Solver e um programa de xadrez para computador. Relatórios sobre seu trabalho apareceram no IRE Transactions on Information Theory em 1956, e em vários anais de conferências de 1957 a 1959, incluindo Proceedings of the Western Joint Computer Conference em 1957 e 1958, e Information Processing (Proceedings of the first UNESCO International Conference on Information Processing) em 1959. O diagrama agora clássico que consiste em blocos representando nós de lista com setas apontando para nós de lista sucessivos aparece em "Programando a Máquina de Teoria Lógica" por Newell e Shaw em Proc. WJCC, fevereiro de 1957. Newell e Simon foram reconhecidos com o ACM Turing Award em 1975 por terem "feito contribuições básicas para a inteligência artificial, a psicologia da cognição humana e o processamento de listas". O problema da tradução automática para processamento de linguagem natural levou Victor Yngve, do Instituto de Tecnologia de Massachusetts (MIT), a usar listas encadeadas como estruturas de dados em sua linguagem de programação COMIT para pesquisa de computador no campo da lingüística. Um relatório sobre esta linguagem intitulado "Uma linguagem de programação para tradução mecânica" apareceu na Mechanical Translation em 1958.

Outra aparição inicial de listas encadeadas foi por Hans Peter Luhn, que escreveu um memorando interno da IBM em janeiro de 1953 sugerindo o uso de listas encadeadas em tabelas hash encadeadas.

LISP, que significa processador de listas, foi criado por John McCarthy em 1958 enquanto ele estava no MIT e em 1960 ele publicou seu design em um artigo na Communications of the ACM, intitulado "Recursive Functions of Symbolic Expressions and Sua Computação por Máquina, Parte I". Uma das principais estruturas de dados do LISP é a lista encadeada.

No início dos anos 1960, a utilidade de ambas as listas encadeadas e linguagens que usam essas estruturas como sua representação de dados primária foi bem estabelecida. Bert Green, do Laboratório Lincoln do MIT, publicou um artigo de revisão intitulado "Linguagens de computador para manipulação de símbolos" em IRE Transactions on Human Factors in Electronics em março de 1961, que resumiu as vantagens da abordagem de lista encadeada. Um artigo de revisão posterior, "Uma comparação de linguagens de computador de processamento de lista" por Bobrow e Raphael, apareceu em Communications of the ACM em abril de 1964.

Vários sistemas operacionais desenvolvidos pela Technical Systems Consultants (originalmente de West Lafayette Indiana, e mais tarde de Chapel Hill, Carolina do Norte) usavam listas vinculadas individualmente como estruturas de arquivo. Uma entrada de diretório apontava para o primeiro setor de um arquivo e as partes seguintes do arquivo eram localizadas por meio de ponteiros. Os sistemas que usam essa técnica incluem Flex (para a CPU Motorola 6800), mini-Flex (mesma CPU) e Flex9 (para a CPU Motorola 6809). Uma variante desenvolvida pela TSC e comercializada pela Smoke Signal Broadcasting na Califórnia, usava listas duplamente encadeadas da mesma maneira.

O sistema operacional TSS/360, desenvolvido pela IBM para as máquinas System 360/370, usava uma lista dupla vinculada para seu catálogo de sistema de arquivos. A estrutura de diretórios era semelhante ao Unix, onde um diretório podia conter arquivos e outros diretórios e estender-se a qualquer profundidade.

Conceitos básicos e nomenclatura

Cada registro de uma lista vinculada geralmente é chamado de 'elemento' ou 'nó'.

O campo de cada nó que contém o endereço do próximo nó é geralmente chamado de 'próximo link' ou 'próximo ponteiro'. Os campos restantes são conhecidos como 'dados', 'informações', 'valor', 'carga' ou 'carga' 39; Campos.

A 'cabeça' de uma lista é seu primeiro nó. A 'cauda' de uma lista pode referir-se ao restante da lista após o cabeçalho ou ao último nó da lista. No Lisp e em algumas linguagens derivadas, o próximo nó pode ser chamado de 'cdr' (pronuncia-se could-er) da lista, enquanto a carga útil do nó principal pode ser chamada de 'carro'.

Lista de encadeamento simples

As listas vinculadas individualmente contêm nós que têm um 'valor' campo, bem como 'próximo' campo, que aponta para o próximo nó na linha de nós. As operações que podem ser executadas em listas vinculadas individualmente incluem inserção, exclusão e travessia.

Uma lista isoladamente vinculada cujos nós contêm dois campos: um valor inteiro e um link para o próximo nó

O código a seguir demonstra como adicionar um novo nó com o "valor" ao final de uma lista encadeada individualmente:

Node addNode(Node cabeça, - Não. valor) ( Node Temp, p; // declarar dois nós temp e p Temp = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = criar Node(); // assumir criar O nó cria um novo nó com valor = 0 e próximo apontando para NULL. Temp- Sim.valor = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = valor; // adicionar elemento a uma parte de valor do nó se (cabeça - Sim. NULL) ( cabeça = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Temp; // quando a lista está vazia ? mais ( p = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = cabeça; // atribuir cabeça a p  enquanto (p- Sim.Próximo ! NULL) ( p = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = p- Sim.Próximo; // atravessar a lista até p ser o último nó. O último nó sempre aponta para NULL. ? p- Sim.Próximo = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Temp; // Apontar o último nó anterior ao novo nó criado. ? retorno cabeça;?

Lista duplamente encadeada

Em uma 'lista duplamente vinculada', cada nó contém, além do link do próximo nó, um segundo campo de link apontando para o 'anterior' nó na sequência. Os dois links podem ser chamados de 'avançar('s') e 'retroceder', ou 'próximo' e 'anterior'('anterior').

Uma lista duplamente vinculada cujos nós contêm três campos: um valor inteiro, o link para a frente para o próximo nó, e o link para trás para o nó anterior

Uma técnica conhecida como ligação XOR permite que uma lista duplamente encadeada seja implementada usando um único campo de ligação em cada nó. No entanto, essa técnica requer a capacidade de realizar operações de bit em endereços e, portanto, pode não estar disponível em algumas linguagens de alto nível.

Muitos sistemas operacionais modernos usam listas duplamente encadeadas para manter referências a processos ativos, threads e outros objetos dinâmicos. Uma estratégia comum para os rootkits escaparem da detecção é desvincular-se dessas listas.

Múltipla lista encadeada

Em uma 'lista multiplamente vinculada', cada nó contém dois ou mais campos de link, cada campo sendo usado para conectar o mesmo conjunto de registros de dados em uma ordem diferente do mesmo conjunto (por exemplo, por nome, por departamento, por data de nascimento, etc.). Embora as listas duplamente encadeadas possam ser vistas como casos especiais de listas multiplamente encadeadas, o fato de duas ou mais ordens serem opostas leva a algoritmos mais simples e eficientes, de modo que geralmente são tratadas como um caso separado.

Lista circular encadeada

No último nó de uma lista, o campo de link geralmente contém uma referência nula, um valor especial é usado para indicar a falta de outros nós. Uma convenção menos comum é apontar para o primeiro nó da lista; nesse caso, diz-se que a lista é 'circular' ou 'ligado circularmente'; caso contrário, diz-se que está 'aberto' ou 'linear'. É uma lista onde o último ponteiro aponta para o primeiro nó.

Uma lista circular ligada

No caso de uma lista circular duplamente encadeada, o primeiro nó também aponta para o último nó da lista.

Nodos sentinela

Em algumas implementações, uma 'sentinela' ou 'manequim' nó pode ser adicionado antes do primeiro registro de dados ou após o último. Essa convenção simplifica e acelera alguns algoritmos de manipulação de listas, garantindo que todos os links possam ser desreferenciados com segurança e que toda lista (mesmo uma que não contenha elementos de dados) sempre tenha um "primeiro" e "último" nó.

Listas vazias

Uma lista vazia é uma lista que não contém registros de dados. Isso geralmente é o mesmo que dizer que ele tem zero nós. Se os nodos sentinelas estiverem sendo usados, a lista geralmente é considerada vazia quando possui apenas nodos sentinelas.

Link de hash

Os campos de link não precisam fazer parte fisicamente dos nós. Se os registros de dados forem armazenados em uma matriz e referenciados por seus índices, o campo de link pode ser armazenado em uma matriz separada com os mesmos índices dos registros de dados.

Listar alças

Como uma referência ao primeiro nó dá acesso a toda a lista, essa referência geralmente é chamada de 'endereço', 'ponteiro' ou 'identificador' da lista. Algoritmos que manipulam listas encadeadas geralmente obtêm esses manipuladores para as listas de entrada e retornam os manipuladores para as listas resultantes. De fato, no contexto de tais algoritmos, a palavra "lista" muitas vezes significa "identificador de lista". Em algumas situações, porém, pode ser conveniente referir-se a uma lista por um identificador que consiste em dois links, apontando para seu primeiro e último nó.

Combinando alternativas

As alternativas listadas acima podem ser combinadas arbitrariamente em quase todas as formas, então pode-se ter listas circulares duplamente encadeadas sem sentinelas, listas circulares encadeadas individualmente com sentinelas, etc.

Compensações

Como acontece com a maioria das opções em programação e design de computadores, nenhum método é adequado para todas as circunstâncias. Uma estrutura de dados de lista encadeada pode funcionar bem em um caso, mas causar problemas em outro. Esta é uma lista de algumas compensações comuns envolvendo estruturas de lista encadeada.

Listas vinculadas x arrays dinâmicos

Um array dinâmico é uma estrutura de dados que aloca todos os elementos contiguamente na memória e mantém uma contagem do número atual de elementos. Se o espaço reservado para o array dinâmico for excedido, ele é realocado e (possivelmente) copiado, o que é uma operação cara.

Listas encadeadas têm várias vantagens sobre arrays dinâmicos. A inserção ou exclusão de um elemento em um ponto específico de uma lista, assumindo que já indexamos um ponteiro para o nó (antes daquele a ser removido, ou antes do ponto de inserção), é uma operação de tempo constante (caso contrário, sem isso referência é O(n)), enquanto a inserção em uma matriz dinâmica em locais aleatórios exigirá mover metade dos elementos em média e todos os elementos no pior caso. Embora se possa "excluir" um elemento de uma matriz em tempo constante marcando de alguma forma seu slot como "vago", isso causa fragmentação que impede o desempenho da iteração.

Além disso, arbitrariamente muitos elementos podem ser inseridos em uma lista encadeada, limitada apenas pela memória total disponível; enquanto uma matriz dinâmica acabará por preencher sua estrutura de dados de matriz subjacente e terá que realocar - uma operação cara, que pode nem ser possível se a memória estiver fragmentada, embora o custo de realocação possa ser calculado em média sobre inserções e o custo de uma inserção por realocação ainda seria amortizada O(1). Isso ajuda a anexar elementos no final da matriz, mas inserir (ou remover) posições intermediárias ainda acarreta custos proibitivos devido à movimentação de dados para manter a contiguidade. Uma matriz da qual muitos elementos são removidos também pode precisar ser redimensionada para evitar o desperdício de muito espaço.

Por outro lado, arrays dinâmicos (assim como estruturas de dados de array de tamanho fixo) permitem acesso aleatório em tempo constante, enquanto listas encadeadas permitem apenas acesso sequencial aos elementos. Na verdade, as listas encadeadas individualmente podem ser facilmente percorridas em apenas uma direção. Isso torna as listas vinculadas inadequadas para aplicativos em que é útil procurar um elemento por seu índice rapidamente, como heapsort. O acesso sequencial em arrays e arrays dinâmicos também é mais rápido do que em listas encadeadas em muitas máquinas, porque eles têm localidade de referência ideal e, portanto, fazem bom uso do cache de dados.

Outra desvantagem das listas encadeadas é o armazenamento extra necessário para referências, o que muitas vezes as torna impraticáveis para listas de pequenos itens de dados, como caracteres ou valores booleanos, porque a sobrecarga de armazenamento para os links pode exceder em um fator de dois ou mais o tamanho dos dados. Em contraste, um array dinâmico requer apenas o espaço para os próprios dados (e uma quantidade muito pequena de dados de controle). Também pode ser lento e com um alocador ingênuo, um desperdício, alocar memória separadamente para cada novo elemento, um problema geralmente resolvido usando pools de memória.

Algumas soluções híbridas tentam combinar as vantagens das duas representações. As listas vinculadas não roladas armazenam vários elementos em cada nó da lista, aumentando o desempenho do cache e diminuindo a sobrecarga de memória para referências. A codificação CDR faz ambos também, substituindo as referências pelos dados reais referenciados, que se estendem até o final do registro de referência.

Um bom exemplo que destaca os prós e contras do uso de arrays dinâmicos versus listas encadeadas é a implementação de um programa que resolva o problema de Josephus. O problema de Josefo é um método de eleição que funciona com um grupo de pessoas formando um círculo. Começando em uma pessoa predeterminada, pode-se contar ao redor do círculo n vezes. Assim que a nésima pessoa for alcançada, deve-se removê-la do círculo e fazer com que os membros fechem o círculo. O processo é repetido até que reste apenas uma pessoa. Essa pessoa ganha a eleição. Isso mostra os pontos fortes e fracos de uma lista encadeada versus uma matriz dinâmica, porque se as pessoas são vistas como nós conectados em uma lista encadeada circular, mostra a facilidade com que a lista encadeada é capaz de excluir nós (já que só precisa reorganizar os links para os diferentes nós). No entanto, a lista encadeada não conseguirá encontrar a próxima pessoa a ser removida e precisará pesquisar na lista até encontrar essa pessoa. Uma matriz dinâmica, por outro lado, será ruim na exclusão de nós (ou elementos), pois não pode remover um nó sem deslocar individualmente todos os elementos da lista em um. No entanto, é excepcionalmente fácil encontrar a nª pessoa no círculo referenciando-a diretamente por sua posição na matriz.

O problema de classificação de lista diz respeito à conversão eficiente de uma representação de lista encadeada em uma matriz. Embora trivial para um computador convencional, resolver esse problema por um algoritmo paralelo é complicado e tem sido objeto de muitas pesquisas.

Uma árvore balanceada tem padrões de acesso à memória semelhantes e sobrecarga de espaço para uma lista encadeada, permitindo uma indexação muito mais eficiente, levando tempo O(log n) em vez de O(n) para um acesso aleatório. No entanto, as operações de inserção e exclusão são mais caras devido à sobrecarga de manipulações de árvore para manter o equilíbrio. Existem esquemas para que as árvores se mantenham automaticamente em um estado equilibrado: árvores AVL ou árvores rubro-negras.

Listas lineares vinculadas individualmente versus outras listas

Embora as listas duplamente encadeadas e circulares tenham vantagens sobre as listas lineares encadeadas individualmente, as listas lineares oferecem algumas vantagens que as tornam preferíveis em algumas situações.

Uma lista linear vinculada individualmente é uma estrutura de dados recursiva, porque contém um ponteiro para um objeto menor do mesmo tipo. Por esse motivo, muitas operações em listas lineares vinculadas individualmente (como mesclar duas listas ou enumerar os elementos na ordem inversa) geralmente têm algoritmos recursivos muito simples, muito mais simples do que qualquer solução usando comandos iterativos. Embora essas soluções recursivas possam ser adaptadas para listas duplamente vinculadas e circularmente vinculadas, os procedimentos geralmente precisam de argumentos extras e casos básicos mais complicados.

As listas lineares ligadas individualmente também permitem o compartilhamento de cauda, o uso de uma parte final comum da sublista como a parte terminal de duas listas diferentes. Em particular, se um novo nó for adicionado no início de uma lista, a lista anterior permanecerá disponível como o fim da nova — um exemplo simples de uma estrutura de dados persistente. Novamente, isso não é verdade com as outras variantes: um nó nunca pode pertencer a duas listas circulares ou duplamente vinculadas diferentes.

Em particular, nós end-sentinela podem ser compartilhados entre listas não circulares ligadas individualmente. O mesmo nó end-sentinela pode ser usado para cada tal lista. Em Lisp, por exemplo, toda lista adequada termina com um link para um nó especial, denotado por nil ou (), cujo CAR e CDR apontam para si mesmo. Assim, um procedimento Lisp pode seguramente pegar o CAR ou CDR de qualquer lista.

As vantagens das variantes sofisticadas geralmente se limitam à complexidade dos algoritmos, não à sua eficiência. Uma lista circular, em particular, geralmente pode ser emulada por uma lista linear juntamente com duas variáveis que apontam para o primeiro e último nós, sem nenhum custo extra.

Duplamente vinculado vs. vinculado individualmente

Listas duplamente encadeadas requerem mais espaço por nó (a menos que se use ligação XOR), e suas operações elementares são mais caras; mas geralmente são mais fáceis de manipular porque permitem acesso sequencial rápido e fácil à lista em ambas as direções. Em uma lista duplamente vinculada, pode-se inserir ou excluir um nó em um número constante de operações, dado apenas o endereço desse nó. Para fazer o mesmo em uma lista encadeada individualmente, deve-se ter o endereço do ponteiro para esse nó, que é o identificador de toda a lista (no caso do primeiro nó) ou o campo de link no nó anterior. Alguns algoritmos requerem acesso em ambas as direções. Por outro lado, listas duplamente encadeadas não permitem compartilhamento de cauda e não podem ser usadas como estruturas de dados persistentes.

Ligadas circularmente vs. Vinculadas linearmente

Uma lista encadeada circularmente pode ser uma opção natural para representar arrays que são naturalmente circulares, por exemplo os cantos de um polígono, um pool de buffers que são usados e liberados na ordem FIFO ("primeiro a entrar, primeiro a sair") ou um conjunto de processos que devem ser compartilhados no tempo em ordem round-robin. Nessas aplicações, um ponteiro para qualquer nó serve como um manipulador para toda a lista.

Com uma lista circular, um ponteiro para o último nó dá acesso fácil também ao primeiro nó, seguindo um link. Assim, em aplicações que exigem acesso a ambas as extremidades da lista (por exemplo, na implementação de uma fila), uma estrutura circular permite manipular a estrutura por um único ponteiro, em vez de dois.

Uma lista circular pode ser dividida em duas listas circulares, em tempo constante, fornecendo os endereços do último nó de cada parte. A operação consiste em trocar o conteúdo dos campos de ligação desses dois nós. Aplicar a mesma operação a quaisquer dois nós em duas listas distintas une as duas listas em uma. Essa propriedade simplifica bastante alguns algoritmos e estruturas de dados, como quad-edge e face-edge.

A representação mais simples para uma lista circular vazia (quando tal coisa faz sentido) é um ponteiro nulo, indicando que a lista não possui nós. Sem essa escolha, muitos algoritmos precisam testar esse caso especial e tratá-lo separadamente. Por outro lado, o uso de null para denotar uma lista linear vazia é mais natural e geralmente cria menos casos especiais.

Para algumas aplicações, pode ser útil usar listas encadeadas individualmente que podem variar entre circulares e lineares, ou mesmo circulares com um segmento inicial linear. Algoritmos para pesquisar ou operar neles devem tomar precauções para evitar entrar acidentalmente em um loop infinito. Um método bem conhecido é fazer com que um segundo ponteiro percorra a lista na metade ou no dobro da velocidade e, se os dois ponteiros se encontrarem no mesmo nó, você saberá que encontrou um ciclo.

Usando nodos sentinela

O nó sentinela pode simplificar certas operações de lista, garantindo que os nós seguintes ou anteriores existam para cada elemento e que mesmo as listas vazias tenham pelo menos um nó. Pode-se também usar um nodo sentinela no final da lista, com um campo de dados apropriado, para eliminar alguns testes de fim de lista. Por exemplo, ao escanear a lista em busca de um nó com um determinado valor x, definir o campo de dados do sentinela como x torna desnecessário testar of-list dentro do loop. Outro exemplo é a fusão de duas listas ordenadas: se suas sentinelas tiverem campos de dados definidos como +∞, a escolha do próximo nó de saída não precisa de tratamento especial para listas vazias.

No entanto, nós sentinelas ocupam espaço extra (especialmente em aplicativos que usam muitas listas curtas) e podem complicar outras operações (como a criação de uma nova lista vazia).

No entanto, se a lista circular for usada apenas para simular uma lista linear, pode-se evitar parte dessa complexidade adicionando um único nó sentinela a cada lista, entre o último e o primeiro nó de dados. Com essa convenção, uma lista vazia consiste apenas no nó sentinela, apontando para si mesmo por meio do link do próximo nó. O identificador da lista deve ser um ponteiro para o último nó de dados, antes da sentinela, se a lista não estiver vazia; ou para a própria sentinela, se a lista estiver vazia.

O mesmo truque pode ser usado para simplificar o manuseio de uma lista linear duplamente encadeada, transformando-a em uma lista circular duplamente encadeada com um único nó sentinela. No entanto, neste caso, o identificador deve ser um único ponteiro para o próprio nó fictício.

Operações de lista vinculada

Ao manipular listas encadeadas no local, tome cuidado para não usar valores que você invalidou em atribuições anteriores. Isso torna os algoritmos para inserir ou excluir nós de lista vinculada um tanto sutis. Esta seção fornece pseudocódigo para adicionar ou remover nós de listas vinculadas simples, duplas e circulares no local. Ao longo usaremos null para nos referir a um marcador de fim de lista ou sentinela, que pode ser implementado de várias maneiras.

Listas ligadas linearmente

Listas ligadas individualmente

Nossa estrutura de dados do nó terá dois campos. Também mantemos uma variável firstNode que sempre aponta para o primeiro nó da lista, ou é null para uma lista vazia.

registro Node(
dados; // Os dados armazenados no nó Node Próximo // Uma referência para o próximo nó, null para o último nó?

registro Lista(
 Node Primeiro primeiro. Node // pontos para o primeiro nó da lista; null para lista vazia?

A travessia de uma lista encadeada individualmente é simples, começando no primeiro nó e seguindo cada próximo link até chegarmos ao fim:

node:= list.firstNode
enquanto node não null
 (fazer algo com nó.dados)node:= node.next

O código a seguir insere um nó após um nó existente em uma lista vinculada individualmente. O diagrama mostra como funciona. Inserir um nó antes de um já existente não pode ser feito diretamente; em vez disso, deve-se acompanhar o nó anterior e inserir um nó depois dele.

Diagrama de inserir um nó em uma lista isoladamente vinculada

função insertAfter(Node Node, Node newNode) // inserir novo nó após o nónewNode.next:= node.next
Node.next: novo nó

Inserir no início da lista requer uma função separada. Isso requer a atualização de firstNode.

função insertBeginning()Lista lista, Node newNode) // inserir o nó antes do primeiro nó atualnewNode.next:= list.firstNode
list.firstNode:= novoNode

Da mesma forma, temos funções para remover o nó depois de um determinado nó e para remover um nó do início da lista. O diagrama demonstra o primeiro. Para localizar e remover um determinado nó, deve-se novamente rastrear o elemento anterior.

Diagrama de excluir um nó de uma lista isoladamente vinculada

função removerAfter(Node Node) // remover o nó passado este:= node.next
Node.next:= node.next.next.next
destruir obsoleto Node

função removerBeginning(Lista lista) // remover primeiro nó:= list.firstNode
list.firstNode:= list.firstNode.next // ponto passado nó excluídodestruir obsoleto Node

Observe que removeBeginning() define list.firstNode como null ao remover o último nó da lista.

Como não podemos iterar para trás, as operações insertBefore ou removeBefore eficientes não são possíveis. Inserir em uma lista antes de um nó específico requer percorrer a lista, que teria um tempo de execução de pior caso de O(n).

Aplicando uma lista vinculada a outra pode ser ineficiente, a menos que uma referência à cauda seja mantida como parte da estrutura da Lista, porque devemos atravessar toda a primeira lista para encontrar a cauda e, em seguida, anexar a segunda lista a isso. Assim, se duas listas linearmente vinculadas são de comprimento nNão., list appending tem complexidade de tempo assintotic O(n)O(n)}. Na família Lisp de línguas, a list appending é fornecida pela append procedimento.

Muitos dos casos especiais de operações de lista encadeada podem ser eliminados incluindo um elemento fictício na frente da lista. Isso garante que não haja casos especiais para o início da lista e torna desnecessários insertBeginning() e removeBeginning(). Neste caso, os primeiros dados úteis na lista serão encontrados em list.firstNode.next.

Lista com links circulares

Em uma lista encadeada circularmente, todos os nós são encadeados em um círculo contínuo, sem usar nulo. Para listas com frente e verso (como uma fila), armazena-se uma referência ao último nó da lista. O nó próximo após o último nó é o primeiro nó. Os elementos podem ser adicionados ao final da lista e removidos da frente em tempo constante.

As listas encadeadas circularmente podem ser encadeadas simples ou duplamente.

Ambos os tipos de listas vinculadas circularmente se beneficiam da capacidade de percorrer a lista completa começando em qualquer nó. Isso geralmente nos permite evitar o armazenamento de firstNode e lastNode, embora se a lista estiver vazia, precisamos de uma representação especial para a lista vazia, como um lastNode variável que aponta para algum nó na lista ou é nulo se estiver vazio; usamos tal lastNode aqui. Essa representação simplifica significativamente a adição e remoção de nós com uma lista não vazia, mas as listas vazias são um caso especial.

Algoritmos

Assumindo que someNode é algum nó em uma lista unificada circular não vazia, este código itera através dessa lista começando com someNode:

função iterate (someNode)
 se algunsNode ≠ NullNão. alguns Node
 doFaz alguma coisa com nó. valor
node:= node.next
 enquanto node ≠ alguns Node

Observe que o nó de teste "while ≠ someNode" deve estar no final do loop. Se o teste fosse movido para o início do loop, o procedimento falharia sempre que a lista tivesse apenas um nó.

Esta função insere um nó "newNode" em uma lista encadeada circular após um determinado nó "nó". Se "nó" for nulo, assume que a lista está vazia.

função insertAfter(Node Node, Node newNode)
 se Node = Null // assuma que a lista está vazia
Nova informação. novo nó
 maisnewNode.next:= node.next
Node.next: novo nó
atualização último nó variável se necessário

Suponha que "L" é uma variável que aponta para o último nó de uma lista encadeada circular (ou null se a lista estiver vazia). Para acrescentar "novoNó" ao fim da lista, pode-se fazer

insertAfter (L, newNode)
Eu... novo nó

Para inserir "newNode" no início da lista, pode-se fazer

insertAfter (L, newNode)
se L = NullEu... novo nó

Esta função insere um valor "newVal" antes de um determinado nó "nó" em tempo O(1). Criamos um novo nó entre "nó" e o próximo nó e, em seguida, coloque o valor de "nó" nesse novo nó e coloque "newVal" em "nó". Assim, uma lista vinculada circularmente vinculada individualmente com apenas uma variável firstNode pode inserir tanto para a frente quanto para trás em tempo O(1).

função insertBefore()Node Node, newVal)
 se Node = Null // assuma que a lista está vazia
Nova informação: novo novo Node(data:=newVal, next:=newNode)
 maisNova informação: novo novo Node(data:=node.data, next:=node.next)
Node.data: novo novo Val
Node.next: novo nó
atualização Primeiro primeiro. Node variável se necessário

Esta função remove um nó não nulo de uma lista de tamanho maior que 1 em tempo O(1). Ele copia os dados do próximo nó para o nó e, em seguida, define o ponteiro próximo do nó para pular o próximo nó.

função remover (Node Node)
 se node ≠ Null e tamanho da lista > 1
removeData:= node.data
node.data:= node.next.data
node.next = node.next.next.next
 retorno removido Dados

Listas vinculadas usando matrizes de nós

As linguagens que não suportam nenhum tipo de referência ainda podem criar links substituindo ponteiros por índices de array. A abordagem é manter uma matriz de registros, onde cada registro possui campos inteiros indicando o índice do próximo (e possivelmente anterior) nó na matriz. Nem todos os nós da matriz precisam ser usados. Se os registros também não forem suportados, matrizes paralelas podem ser usadas em seu lugar.

Como exemplo, considere o seguinte registro de lista vinculada que usa matrizes em vez de ponteiros:

registro Entrada (
 Intérprete a seguir; // índice da próxima entrada no array Intérprete prev; // entrada anterior (se dupla ligação) string nome;
 real equilíbrio;
?

Uma lista vinculada pode ser construída criando um array dessas estruturas e uma variável inteira para armazenar o índice do primeiro elemento.

Intérprete lista Cabeça
Entrada Registros[1000]

As ligações entre os elementos são formadas colocando o índice da matriz da célula seguinte (ou anterior) no campo Próximo ou Anterior dentro de um determinado elemento. Por exemplo:

No exemplo acima, ListHead seria definido como 2, o local da primeira entrada na lista. Observe que as entradas 3 e 5 a 7 não fazem parte da lista. Essas células estão disponíveis para quaisquer adições à lista. Ao criar uma variável inteira ListFree, uma lista livre pode ser criada para acompanhar quais células estão disponíveis. Se todas as entradas estiverem em uso, o tamanho da matriz deverá ser aumentado ou alguns elementos deverão ser excluídos antes que novas entradas possam ser armazenadas na lista.

O código a seguir percorreria a lista e exibiria os nomes e o saldo da conta:

Eu... lista Cabeça
enquanto I ≥ 0 // loop através da listaprint i, Records[i].name, Records[i].balance // entrada de impressãoi:= Registros[i].next

Quando confrontado com uma escolha, as vantagens desta abordagem incluem:

• A lista vinculada é relocatable, o que significa que pode ser movido em memória à vontade, e também pode ser serializado rapidamente e diretamente para armazenamento no disco ou transferência em uma rede.
• Especialmente para uma pequena lista, os índices de array podem ocupar significativamente menos espaço do que um ponteiro completo em muitas arquiteturas.
• Localidade de referência pode ser melhorada, mantendo os nós juntos na memória e periodicamente reorganizá-los, embora isso também pode ser feito em uma loja geral.
• Os alocadores de memória dinâmicos ingênuos podem produzir uma quantidade excessiva de armazenamento aéreo para cada nó alocado; quase nenhuma sobrecarga é incorrida por nó nesta abordagem.
• A obtenção de uma entrada de um array pré-alocado é mais rápida do que usar alocação de memória dinâmica para cada nó, já que a alocação de memória dinâmica normalmente requer uma busca por um bloco de memória livre do tamanho desejado.

No entanto, essa abordagem tem uma desvantagem principal: ela cria e gerencia um espaço de memória privado para seus nós. Isso leva aos seguintes problemas:

• Aumenta a complexidade da implementação.
• Crescer um grande array quando ele está cheio pode ser difícil ou impossível, ao passo que encontrar espaço para um novo nó de lista vinculado em um grande, pool de memória geral pode ser mais fácil.
• Adicionando elementos a uma matriz dinâmica ocasionalmente (quando está cheio) inesperadamente tomar linear (O(n))) em vez de tempo constante (embora ainda seja uma constante amortizada).
• Usar um pool de memória geral deixa mais memória para outros dados se a lista for menor do que o esperado ou se muitos nós forem liberados.

Por esses motivos, essa abordagem é usada principalmente para idiomas que não suportam alocação dinâmica de memória. Essas desvantagens também são atenuadas se o tamanho máximo da lista for conhecido no momento em que o array é criado.

Suporte a idiomas

Muitas linguagens de programação, como Lisp e Scheme, possuem listas vinculadas individualmente. Em muitas linguagens funcionais, essas listas são construídas a partir de nós, cada um chamado de cons ou cons cell. O contras tem dois campos: o car, uma referência aos dados desse nó, e o cdr, uma referência ao próximo nó. Embora as células cons possam ser usadas para construir outras estruturas de dados, esse é seu objetivo principal.

Em linguagens que suportam tipos de dados abstratos ou modelos, ADTs ou modelos de lista encadeada estão disponíveis para a construção de listas encadeadas. Em outros idiomas, as listas encadeadas geralmente são construídas usando referências junto com registros.

Armazenamento interno e externo

Ao construir uma lista encadeada, depara-se com a escolha entre armazenar os dados da lista diretamente nos nós da lista encadeada, chamados de armazenamento interno, ou simplesmente armazenar uma referência ao dados, chamados de armazenamento externo. O armazenamento interno tem a vantagem de tornar o acesso aos dados mais eficiente, exigindo menos armazenamento geral, tendo melhor localidade de referência e simplificando o gerenciamento de memória para a lista (seus dados são alocados e desalocados ao mesmo tempo que os nós da lista).

O armazenamento externo, por outro lado, tem a vantagem de ser mais genérico, pois a mesma estrutura de dados e código de máquina podem ser usados para uma lista vinculada, independentemente do tamanho dos dados. Também facilita a colocação dos mesmos dados em várias listas vinculadas. Embora com o armazenamento interno os mesmos dados possam ser colocados em várias listas, incluindo várias referências próximo na estrutura de dados do nó, seria necessário criar rotinas separadas para adicionar ou excluir células com base em cada campo. É possível criar listas vinculadas adicionais de elementos que usam armazenamento interno usando armazenamento externo e fazer com que as células das listas vinculadas adicionais armazenem referências aos nós da lista vinculada que contém os dados.

Em geral, se um conjunto de estruturas de dados precisa ser incluído em listas encadeadas, o armazenamento externo é a melhor abordagem. Se um conjunto de estruturas de dados precisa ser incluído em apenas uma lista encadeada, o armazenamento interno é um pouco melhor, a menos que um pacote genérico de lista encadeada usando armazenamento externo esteja disponível. Da mesma forma, se diferentes conjuntos de dados que podem ser armazenados na mesma estrutura de dados forem incluídos em uma única lista encadeada, o armazenamento interno seria adequado.

Outra abordagem que pode ser usada com alguns idiomas envolve ter diferentes estruturas de dados, mas todas com os campos iniciais, incluindo o próximo (e anterior se for uma lista duplamente vinculada) referências no mesmo local. Após definir estruturas separadas para cada tipo de dados, pode-se definir uma estrutura genérica que contenha a quantidade mínima de dados compartilhados por todas as outras estruturas e contida no topo (início) das estruturas. Em seguida, podem ser criadas rotinas genéricas que usam a estrutura mínima para executar operações do tipo lista encadeada, mas rotinas separadas podem manipular os dados específicos. Esta abordagem é frequentemente utilizada em rotinas de análise de mensagens, onde vários tipos de mensagens são recebidas, mas todas começam com o mesmo conjunto de campos, geralmente incluindo um campo para o tipo de mensagem. As rotinas genéricas são usadas para adicionar novas mensagens a uma fila quando são recebidas e removê-las da fila para processar a mensagem. O campo de tipo de mensagem é então usado para chamar a rotina correta para processar o tipo específico de mensagem.

Exemplo de armazenamento interno e externo

Suponha que você queira criar uma lista encadeada de famílias e seus membros. Usando o armazenamento interno, a estrutura pode ter a seguinte aparência:

registro membro (// membro de uma família membro a seguir;
 string Primeiro primeiro. Nome;
 Intérprete idade;
?
registro família (// a própria família família a seguir;
 string último nome;
 string endereço;
 membro membros // chefe da lista de membros desta família?

Para imprimir uma lista completa de famílias e seus membros usando o armazenamento interno, podemos escrever:

A família... Famílias // começar na cabeça da lista de famíliasenquanto AFamily ≠ Null // loop através da lista de famíliasimprimir informações sobre a família
aMember:= aFamily.members // obter a lista dos membros desta família enquanto aMember ≠ Null // loop através da lista de membrosimprimir informações sobre o membro
aMember:= aMember.next
aFamily:= aFamily.next

Usando armazenamento externo, criaríamos as seguintes estruturas:

registro Node (// estrutura de ligação genérica Node a seguir;
 ponteiro dados // ponteiro genérico para dados no nó?
registro membro (// estrutura para membro da família string Primeiro primeiro. Nome;
 Intérprete idade
?
registro família (// estrutura para família string último nome;
 string endereço;
 Node membros // chefe da lista de membros desta família?

Para imprimir uma lista completa de famílias e seus membros usando armazenamento externo, podemos escrever:

famNode:= Famílias // começar na cabeça da lista de famíliasenquanto FamNode ≠ Null // loop através da lista de famíliasaFamily:= (família) famNode.data // extraia a família do nóimprimir informações sobre a família
memNode:= aFamily.members // obter lista de membros da família enquanto memNode ≠ Null // loop através da lista de membrosaMember:= (membro)memNode.data // extrair membro do nóimprimir informações sobre o membro
memNode:= memNode.next
famNode:= famNode.next

Observe que ao usar armazenamento externo, uma etapa extra é necessária para extrair o registro do nó e convertê-lo no tipo de dados apropriado. Isso ocorre porque tanto a lista de famílias quanto a lista de membros dentro da família são armazenadas em duas listas vinculadas usando a mesma estrutura de dados (nó) e essa linguagem não possui tipos paramétricos.

Contanto que o número de famílias às quais um membro pode pertencer seja conhecido em tempo de compilação, o armazenamento interno funcionará bem. Se, no entanto, um membro precisasse ser incluído em um número arbitrário de famílias, com o número específico conhecido apenas em tempo de execução, seria necessário armazenamento externo.

Acelerando a pesquisa

Encontrar um elemento específico em uma lista vinculada, mesmo que esteja classificado, normalmente requer O(n) tempo (pesquisa linear). Essa é uma das principais desvantagens das listas encadeadas em relação a outras estruturas de dados. Além das variantes discutidas acima, abaixo estão duas maneiras simples de melhorar o tempo de pesquisa.

Em uma lista não ordenada, uma heurística simples para diminuir o tempo médio de busca é a heurística mover para a frente, que simplesmente move um elemento para o início da lista quando ele é encontrado. Esse esquema, útil para criar caches simples, garante que os itens usados mais recentemente também sejam os mais rápidos de serem encontrados.

Outra abordagem comum é "indexar" uma lista encadeada usando uma estrutura de dados externa mais eficiente. Por exemplo, pode-se construir uma árvore rubro-negra ou tabela hash cujos elementos são referências aos nós da lista encadeada. Vários desses índices podem ser criados em uma única lista. A desvantagem é que esses índices podem precisar ser atualizados cada vez que um nó é adicionado ou removido (ou pelo menos, antes que o índice seja usado novamente).

Listas de acesso aleatório

Uma lista de acesso aleatório é uma lista com suporte para acesso aleatório rápido para ler ou modificar qualquer elemento da lista. Uma implementação possível é uma lista binária de acesso aleatório assimétrica usando o sistema numérico binário assimétrico, que envolve uma lista de árvores com propriedades especiais; isso permite operações de cabeça/contras de tempo constante de pior caso e acesso aleatório de tempo logarítmico de pior caso a um elemento por índice. As listas de acesso aleatório podem ser implementadas como estruturas de dados persistentes.

As listas de acesso aleatório podem ser vistas como listas encadeadas imutáveis, pois também suportam as mesmas operações de cabeça e cauda O(1).

Uma extensão simples para listas de acesso aleatório é a min-list, que fornece uma operação adicional que produz o elemento mínimo em toda a lista em tempo constante (sem complexidades de mutação).

Estruturas de dados relacionadas

Tanto as pilhas quanto as filas geralmente são implementadas usando listas encadeadas e simplesmente restringem o tipo de operações que são suportadas.

A lista de salto é uma lista vinculada aumentada com camadas de ponteiros para saltar rapidamente sobre um grande número de elementos e, em seguida, descer para a próxima camada. Esse processo continua até a camada inferior, que é a lista real.

Uma árvore binária pode ser vista como um tipo de lista encadeada onde os elementos são listas encadeadas da mesma natureza. O resultado é que cada nó pode incluir uma referência ao primeiro nó de uma ou duas outras listas encadeadas, que, juntamente com seus conteúdos, formam as subárvores abaixo desse nó.

Uma lista vinculada desenrolada é uma lista vinculada na qual cada nó contém uma matriz de valores de dados. Isso leva a um melhor desempenho do cache, uma vez que mais elementos da lista são contíguos na memória e reduz a sobrecarga de memória, porque menos metadados precisam ser armazenados para cada elemento da lista.

Uma tabela hash pode usar listas encadeadas para armazenar as cadeias de itens que têm hash para a mesma posição na tabela hash.

Um heap compartilha algumas das propriedades de ordenação de uma lista encadeada, mas quase sempre é implementado usando um array. Em vez de referências de nó a nó, os índices de dados anteriores e seguintes são calculados usando o índice de dados atual.

Uma lista auto-organizada reorganiza seus nós com base em alguma heurística que reduz o tempo de busca para recuperação de dados, mantendo os nós comumente acessados no topo da lista.