Lista vinculada - Linked list

Uma lista vinculada cujos nós contêm dois campos: um valor inteiro e um link para o próximo nó. O último nó está vinculado 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 sua colocação física 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, permitindo uma inserção ou remoção mais eficiente de nós em posições arbitrárias. Uma desvantagem das listas vinculadas é que o tempo de acesso é linear (e difícil de pipeline ). O acesso mais rápido, como o acesso aleatório, não é viável. Os arrays têm melhor localidade de cache em comparação com listas vinculadas.

Listas vinculadas 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 vinculada como base.

O principal benefício de uma lista encadeada em relação a uma matriz 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 contiguamente na memória ou no disco, durante a reestruturação de uma matriz em o tempo de execução é uma operação muito mais cara. 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 sendo adicionado ou removido na memória durante a travessia da lista.

Por outro lado, uma vez que listas vinculadas 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 contém um dado dado, ou localizar o local onde um novo nó deve ser inserido - pode exigir a iteração pela maioria ou todos os elementos da lista. As vantagens e desvantagens de usar listas vinculadas são fornecidas a seguir.

História

As listas vinculadas foram desenvolvidas em 1955–1956, por Allen Newell , Cliff Shaw e Herbert A. Simon na RAND Corporation 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 a Logic Theory Machine, o General Problem Solver e um programa de xadrez de computador. Relatórios sobre seu trabalho apareceram em 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 (Anais da primeira Conferência Internacional da UNESCO sobre Processamento de Informação ) em 1959. O diagrama agora clássico consistindo em blocos que representam nós de lista com setas apontando para nós de lista sucessivos aparece em "Programming the Logic Theory Machine" por Newell e Shaw em Proc. WJCC, fevereiro de 1957. Newell e Simon foram homenageados com o Prêmio ACM Turing 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 o processamento de linguagem natural levou Victor Yngve , do Massachusetts Institute of Technology (MIT), a usar listas vinculadas como estruturas de dados em sua linguagem de programação COMIT para pesquisa de computador no campo da lingüística . Um relatório sobre essa linguagem, intitulado "Uma linguagem de programação para tradução mecânica", apareceu na Mechanical Translation em 1958.

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

LISP , que significa processador de lista, foi criado por John McCarthy em 1958 enquanto ele estava no MIT e em 1960 ele publicou seu projeto em um artigo na Communications of the ACM , intitulado "Funções recursivas de expressões simbólicas e sua computação por máquina, parte EU". Uma das principais estruturas de dados do LISP é a lista vinculada.

No início da década de 1960, a utilidade das listas vinculadas e das linguagens que usam essas estruturas como sua representação primária de dados estava 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 vinculada. Um artigo de revisão posterior, "A Comparison of list-processing computer languages", de Bobrow e Raphael, apareceu em Communications of the ACM em abril de 1964.

Vários sistemas operacionais desenvolvidos por Consultores de Sistemas Técnicos (originalmente de West Lafayette Indiana, e mais tarde de Chapel Hill, Carolina do Norte) usavam listas unidas individualmente como estruturas de arquivos. Uma entrada de diretório apontava para o primeiro setor de um arquivo e as partes seguintes do arquivo foram localizadas por ponteiros de passagem. 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 vinculadas da mesma maneira.

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

Conceitos básicos e nomenclatura

Cada registro de uma lista vinculada é freqüentemente chamado de 'elemento' ou ' '.

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 campos 'dados', 'informações', 'valor', 'carga' ou 'carga útil'.

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

Lista unicamente ligada

Listas unidas individualmente contêm nós que possuem um campo de dados, bem como um campo 'próximo', que aponta para o próximo nó na linha de nós. As operações que podem ser realizadas em listas unidas individualmente incluem inserção, exclusão e passagem.

Uma lista vinculada individualmente 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 "valor" de dados ao final de uma lista vinculada individualmente:

node addNode(node head, int value) {
    node temp, p; // declare two nodes temp and p
    temp = createNode(); // assume createNode creates a new node with data = 0 and next pointing to NULL.
    temp->data = value; // add element's value to data part of node
    if (head == NULL) {
        head = temp;     // when linked list is empty
    }
    else {
        p = head; // assign head to p 
        while (p->next != NULL) {
            p = p->next; // traverse the list until p is the last node. The last node always points to NULL.
        }
        p->next = temp; // Point the previous last node to the new node created.
    }
    return head;
}

Lista duplamente vinculada

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 nó 'anterior' na sequência. Os dois links podem ser chamados de 'para frente (' s ') e' para trás ', ou' próximo 'e' anterior '(' anterior ').

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

Uma técnica conhecida como vinculação XOR permite que uma lista duplamente vinculada seja implementada usando um único campo de link em cada nó. No entanto, essa técnica requer a capacidade de fazer operações de bits 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 vinculadas para manter referências a processos ativos, threads e outros objetos dinâmicos. Uma estratégia comum para que os rootkits evitem a detecção é desvincular-se dessas listas.

Multiplicar lista vinculada

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 vinculadas possam ser vistas como casos especiais de listas multiplamente vinculadas, o fato de as duas ou mais ordens serem opostas uma à outra leva a algoritmos mais simples e eficientes, portanto, geralmente são tratadas como um caso separado.

Lista circular ligada

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, a lista é considerada 'circular' ou 'ligada circularmente'; caso contrário, diz-se que é '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 ligada, o primeiro nó também aponta para o último nó da lista.

Nódulos sentinela

Em algumas implementações, um nó 'sentinela' ou 'fictício' extra 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 lista, garantindo que todos os links possam ser desreferenciados com segurança e que cada 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. Geralmente, isso é o mesmo que dizer que tem zero nós. Se os nódulos sentinela estão sendo usados, a lista é geralmente considerada vazia quando tem apenas nódulos sentinela.

Hash linking

Os campos de link não precisam fazer parte fisicamente dos nós. Se os registros de dados são 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.

Alças de lista

Visto que uma referência ao primeiro nó dá acesso a toda a lista, essa referência é freqüentemente chamada de 'endereço', 'ponteiro' ou 'identificador' da lista. Os algoritmos que manipulam listas vinculadas geralmente obtêm esses identificadores para as listas de entrada e retornam os identificadores para as listas resultantes. Na verdade, no contexto de tais algoritmos, a palavra "lista" geralmente significa "identificador de lista". Em algumas situações, entretanto, pode ser conveniente referir-se a uma lista por meio de um identificador que consiste em dois links, apontando para seu primeiro e último nós.

Combinando alternativas

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

Tradeoffs

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

Listas vinculadas x matrizes dinâmicas

Comparação de estruturas de dados de lista
Olhadinha Transformar (inserir ou excluir) em ... Excesso de espaço,
média
Começo Fim Meio
Lista ligada Θ ( n ) Θ (1) Θ (1), elemento final conhecido;
Θ ( n ), elemento final desconhecido
Hora de
espiar + Θ (1)
Θ ( n )
Variedade Θ (1) N / D N / D N / D 0
Array dinâmico Θ (1) Θ ( n ) Θ (1) amortizado Θ ( n ) Θ ( n )
Árvore balanceada Θ (log n) Θ (log n) Θ (log n ) Θ (log n ) Θ ( n )
Lista de acesso aleatório Θ (log n) Θ (1) N / D N / D Θ ( n )
Árvore de matriz com hash Θ (1) Θ ( n ) Θ (1) amortizado Θ ( n ) Θ (√ n )

Uma matriz dinâmica é uma estrutura de dados que aloca todos os elementos de forma contígua 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 será realocado e (possivelmente) copiado, o que é uma operação cara.

As listas vinculadas têm várias vantagens sobre os 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á a movimentação de metade dos elementos em média e todos os elementos no pior caso. Embora seja possível "excluir" um elemento de uma matriz em tempo constante, de alguma forma, marcando seu slot como "vago", isso causa fragmentação que impede o desempenho da iteração.

Além disso, muitos elementos arbitrariamente 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 não ser possível se a memória estiver fragmentada, embora o custo de realocação possa ser calculado em relação às inserções e o custo de uma inserção por realocação ainda seria amortizada O (1). Isso ajuda a anexar elementos no final do array, 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 ter que ser redimensionada para evitar o desperdício de muito espaço.

Por outro lado, matrizes dinâmicas (bem como estruturas de dados de matrizes de tamanho fixo ) permitem acesso aleatório em tempo constante , enquanto listas vinculadas permitem apenas acesso sequencial aos elementos. De fato, as listas unidas individualmente podem ser facilmente percorridas em apenas uma direção. Isso torna as listas vinculadas inadequadas para aplicativos em que é útil pesquisar um elemento por seu índice rapidamente, como o heapsort . O acesso sequencial em arrays e arrays dinâmicos também é mais rápido do que em listas vinculadas 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 vinculadas é 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 por um fator de dois ou mais o tamanho de os dados. Em contraste, uma matriz dinâmica 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. Listas vinculadas desenroladas armazenam vários elementos em cada nó da lista, aumentando o desempenho do cache enquanto diminui a sobrecarga de memória para referências. A codificação CDR também faz isso, 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 os contras do uso de matrizes dinâmicas versus listas vinculadas é a implementação de um programa que resolve 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 com uma pessoa predeterminada, pode-se contar ao redor do círculo n vezes. Uma vez que o n th pessoa é atingido, deve-se removê-los do círculo e possuem os membros fechar o círculo. O processo é repetido até que apenas uma pessoa reste. Essa pessoa vence a eleição. Isso mostra os pontos fortes e fracos de uma lista encadeada vs. uma matriz dinâmica, porque se as pessoas são vistas como nós conectados em uma lista encadeada circular, então mostra quão facilmente a lista encadeada é capaz de deletar nós (já que só precisa reorganizar os links para os diferentes nós). No entanto, a lista vinculada não conseguirá encontrar a próxima pessoa a ser removida e precisará pesquisar a lista até encontrar essa pessoa. Uma matriz dinâmica, por outro lado, será pobre em excluir nós (ou elementos), pois não pode remover um nó sem deslocar individualmente todos os elementos para cima na lista por um. No entanto, é extremamente fácil de encontrar o n th pessoa no círculo referenciando-los directamente pela 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 um array. 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, enquanto permite 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 das manipulações da árvore para manter o equilíbrio. Existem esquemas para que as árvores se mantenham automaticamente em um estado de equilíbrio: árvores AVL ou árvores vermelho-pretas .

Listas lineares com link único vs. outras listas

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

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

Listas lineares unidas individualmente também permitem o compartilhamento de cauda , o uso de uma parte final comum da sub-lista 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 final da nova - um exemplo simples de uma estrutura de dados persistente . Novamente, isso não é verdade com as outras variantes: um nó pode nunca pertencer a duas listas circulares diferentes ou duplamente vinculadas.

Em particular, os nodos sentinela finais podem ser compartilhados entre listas não circulares unidas individualmente. O mesmo nó sentinela final pode ser usado para cada uma dessas listas. Em Lisp , por exemplo, toda lista própria termina com um link para um nó especial, denotado por nilou (), cujos links CARe CDRapontam para si mesmo. Assim, um procedimento Lisp pode obter com segurança o CARou CDRde qualquer lista.

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

Ligado duplamente vs. ligado individualmente

Listas duplamente vinculadas requerem mais espaço por nó (a menos que se use vinculaçã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 unida individualmente, deve-se ter o endereço do ponteiro para aquele nó, que é o identificador de toda a lista (no caso do primeiro nó) ou o campo do link no nó anterior . Alguns algoritmos requerem acesso em ambas as direções. Por outro lado, as listas duplamente vinculadas não permitem o compartilhamento de cauda e não podem ser usadas como estruturas de dados persistentes .

Ligado circularmente vs. ligado linearmente

Uma lista ligada circularmente pode ser uma opção natural para representar matrizes que são naturalmente circulares, por exemplo, os cantos de um polígono , um conjunto de buffers que são usados ​​e liberados em ordem FIFO ("primeiro a entrar , primeiro a sair") ou um conjunto de processos que devem ser compartilhados no tempo em ordem de rodízio . Nesses aplicativos, um ponteiro para qualquer nó serve como um identificador 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 aplicativos que requerem acesso a ambas as extremidades da lista (por exemplo, na implementação de uma fila), uma estrutura circular permite tratar a estrutura por um único ponteiro, em vez de dois.

Uma lista circular pode ser dividida em duas listas circulares, em tempo constante, dando os endereços do último nó de cada peça. 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 muito 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. Em contraste, o uso de nulo para denotar uma lista linear vazia é mais natural e geralmente cria menos casos especiais.

Usando nós sentinela

O nó sentinela pode simplificar certas operações de lista, garantindo que o próximo nó ou o nó anterior existam para cada elemento e que mesmo listas vazias tenham pelo menos um nó. Pode-se também usar um nó sentinela no final da lista, com um campo de dados apropriado, para eliminar alguns testes de final de lista. Por exemplo, ao varrer a lista à procura de um nó com um determinado valor x , definir o campo de dados da sentinela como x torna desnecessário testar o fim da lista dentro do loop. Outro exemplo é a fusão de duas listas classificadas: se suas sentinelas têm campos de dados configurados como + ∞, a escolha do próximo nó de saída não precisa de tratamento especial para listas vazias.

No entanto, os nós sentinela usam 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 tratamento de uma lista linear duplamente vinculada, transformando-a em uma lista circular duplamente vinculada 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 vinculadas no local, deve-se tomar cuidado para não usar valores que você invalidou em atribuições anteriores. Isso torna os algoritmos para inserir ou excluir nós de listas vinculadas um pouco sutis. Esta seção fornece um pseudocódigo para adicionar ou remover nós de listas unidas, duplamente ou circularmente no local. Ao longo do tempo, usaremos null para nos referir a um marcador de fim de lista ou sentinela , que pode ser implementado de várias maneiras.

Listas com link linear

Listas unidas individualmente

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

record Node
{
    data; // The data being stored in the node
    Node next // A reference to the next node, null for last node
}
record List
{
    Node firstNode // points to first node of list; null for empty list
}

A travessia de uma lista unida individualmente é simples, começando no primeiro nó e seguindo cada link seguinte até chegarmos ao final:

node := list.firstNode
while node not null
    (do something with node.data)
    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. A inserção de um nó antes de um existente não pode ser feita diretamente; em vez disso, deve-se acompanhar o nó anterior e inserir um nó depois dele.

Diagrama de inserção de um nó em uma lista unida individualmente
function insertAfter(Node node, Node newNode) // insert newNode after node
    newNode.next := node.next
    node.next    := newNode

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

function insertBeginning(List list, Node newNode) // insert node before current first node
    newNode.next   := list.firstNode
    list.firstNode := newNode

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

Diagrama de exclusão de um nó de uma lista unida individualmente
function removeAfter(Node node) // remove node past this one
    obsoleteNode := node.next
    node.next := node.next.next
    destroy obsoleteNode
function removeBeginning(List list) // remove first node
    obsoleteNode := list.firstNode
    list.firstNode := list.firstNode.next // point past deleted node
    destroy obsoleteNode

Observe que removeBeginning()define list.firstNodecomo nullao remover o último nó da lista.

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

Anexar 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 percorrer toda a primeira lista para encontrar a cauda e, em seguida, anexar a segunda lista a ela. Assim, se duas listas ligadas linearmente têm comprimento , o acréscimo de lista tem complexidade de tempo assintótica de . Na família de linguagens Lisp, o acréscimo de lista é fornecido pelo procedimento. append

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

Lista ligada circularmente

Em uma lista ligada circularmente, todos os nós são ligados 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 próximo nó 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 com links circulares podem ser simples ou duplamente vinculadas.

Ambos os tipos de listas ligadas 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 possa estar vazia, precisamos de uma representação especial para a lista vazia, como uma variável lastNode que aponta para algum nó na lista ou é nula se estiver vazia; usamos esse 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

Supondo que someNode seja algum nó em uma lista circular não vazia vinculada individualmente, este código itera por meio dessa lista começando com someNode :

function iterate(someNode)
    if someNode ≠ null
        node := someNode
    do
        do something with node.value
        node := node.next
    while node ≠ someNode

Observe que o teste " while node ≠ 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 ligada circular após um determinado nó "nó". Se "nó" for nulo, ele assume que a lista está vazia.

function insertAfter(Node node, Node newNode)
    if node = null    // assume list is empty
        newNode.next := newNode
    else
        newNode.next := node.next
        node.next := newNode
    update lastNode variable if necessary

Suponha que "L" seja uma variável apontando para o último nó de uma lista ligada circular (ou nula se a lista estiver vazia). Para acrescentar "newNode" ao final da lista, pode-se fazer

insertAfter(L, newNode)
L := newNode

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

insertAfter(L, newNode)
if L = null
    L := newNode

Esta função insere um valor "newVal" antes de um determinado nó "nó" no tempo O (1). Criamos um novo nó entre "nó" e o próximo nó e, em seguida, colocamos o valor de "nó" nesse novo nó e colocamos "newVal" em "nó". Assim, uma lista ligada circularmente com apenas uma variável firstNode pode ser inserida na frente e atrás no tempo O (1).

function insertBefore(Node node, newVal)
    if node = null    // assume list is empty
        newNode := new Node(data:=newVal, next:=newNode)
    else
        newNode := new Node(data:=node.data, next:=node.next)
        node.data := newVal
        node.next := newNode
    update firstNode variable if necessary

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

function remove(Node node)
    if node ≠ null and size of list > 1
        removedData := node.data
        node.data := node.next.data
        node.next = node.next.next
        return removedData

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 tem 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, as matrizes paralelas podem ser usadas em seu lugar.

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

record Entry {
    integer next; // index of next entry in array
    integer prev; // previous entry (if double-linked)
    string name;
    real balance;
}

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

integer listHead
Entry Records[1000]

Os links entre os elementos são formados colocando-se o índice da matriz da célula seguinte (ou anterior) no campo Próximo ou Anterior dentro de um determinado elemento. Por exemplo:

Índice Próximo Anterior Nome Equilíbrio
0 1 4 Jones, John 123,45
1 -1 0 Smith, Joseph 234,56
2 (listHead) 4 -1 Adams, Adam 0,00
3 Ignore, Inácio 999,99
4 0 2 Outra, anita 876,54
5
6
7

No exemplo acima, ListHeadseria definido como 2, a localização 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 qualquer adição à lista. Ao criar uma ListFreevariável inteira, uma lista livre pode ser criada para controlar 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 percorrerá a lista e exibirá os nomes e o saldo da conta:

i := listHead
while i ≥ 0 // loop through the list
    print i, Records[i].name, Records[i].balance // print entry
    i := Records[i].next

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

  • A lista vinculada é relocável, o que significa que pode ser movida à vontade na memória e também pode ser serializada de forma rápida e direta para armazenamento em disco ou transferência pela rede.
  • Especialmente para uma lista pequena, os índices de array podem ocupar significativamente menos espaço do que um ponteiro completo em muitas arquiteturas.
  • A localidade de referência pode ser melhorada mantendo os nós juntos na memória e reorganizando-os periodicamente, embora isso também possa ser feito em um armazém geral.
  • Alocadores de memória dinâmica ingênuos podem produzir uma quantidade excessiva de armazenamento de sobrecarga para cada nó alocado; quase nenhuma sobrecarga de alocação é incorrida por nó nesta abordagem.
  • Capturar uma entrada de uma matriz pré-alocada é mais rápido do que usar a alocação de memória dinâmica para cada nó, uma vez que a alocação de memória dinâmica normalmente requer uma busca por um bloco de memória livre do tamanho desejado.

Essa abordagem tem uma desvantagem principal, no entanto: 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.
  • Aumentar uma grande matriz quando ela está cheia pode ser difícil ou impossível, enquanto encontrar espaço para um novo nó de lista vinculada em um grande conjunto de memória geral pode ser mais fácil.
  • Adicionar elementos a um array dinâmico irá ocasionalmente (quando ele estiver cheio) inesperadamente demorar linear ( O (n)) em vez de tempo constante (embora ainda seja uma constante amortizada ).
  • O uso de 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 linguagens que não oferecem suporte à alocação de memória dinâmica. Essas desvantagens também são atenuadas se o tamanho máximo da lista for conhecido no momento em que o array é criado.

Suporte de linguas

Muitas linguagens de programação , como Lisp e Scheme, têm listas vinculadas individualmente integradas. 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 carro , 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 oferecem suporte a tipos de dados abstratos ou modelos, ADTs ou modelos de lista vinculada estão disponíveis para a construção de listas vinculadas. Em outras linguagens, as listas vinculadas são normalmente construídas usando referências junto com registros .

Armazenamento interno e externo

Ao construir uma lista encadeada, enfrenta-se a escolha de armazenar os dados da lista diretamente nos nós da lista encadeada, denominado armazenamento interno , ou simplesmente armazenar uma referência aos dados, denominado 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 encadeada, independentemente do tamanho dos dados. Também torna mais fácil colocar os 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 próximas referências 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 fazendo 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 vinculadas, o armazenamento externo é a melhor abordagem. Se um conjunto de estruturas de dados precisar ser incluído em apenas uma lista vinculada, o armazenamento interno é um pouco melhor, a menos que um pacote genérico de lista vinculada 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 vinculada, o armazenamento interno seria adequado.

Outra abordagem que pode ser usada com algumas linguagens envolve ter estruturas de dados diferentes, mas todas têm os campos iniciais, incluindo as próximas referências (e anterior se a lista de ligação dupla) no mesmo local. Depois de definir estruturas separadas para cada tipo de dados, uma estrutura genérica pode ser definida que contém a quantidade mínima de dados compartilhados por todas as outras estruturas e contidos no topo (início) das estruturas. Em seguida, rotinas genéricas podem ser criadas que usam a estrutura mínima para executar operações de tipo de lista vinculada, mas rotinas separadas podem então lidar com os dados específicos. Essa abordagem é frequentemente usada em rotinas de análise de mensagens, onde vários tipos de mensagens são recebidos, 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 do 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 vinculada de famílias e seus membros. Usando o armazenamento interno, a estrutura pode ser semelhante a esta:

record member { // member of a family
    member next;
    string firstName;
    integer age;
}
record family { // the family itself
    family next;
    string lastName;
    string address;
    member members // head of list of members of this family
}

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

aFamily := Families // start at head of families list
while aFamily ≠ null // loop through list of families
    print information about family
    aMember := aFamily.members // get head of list of this family's members
    while aMember ≠ null // loop through list of members
        print information about member
        aMember := aMember.next
    aFamily := aFamily.next

Usando armazenamento externo, criaríamos as seguintes estruturas:

record node { // generic link structure
    node next;
    pointer data // generic pointer for data at node
}
record member { // structure for family member
    string firstName;
    integer age
}
record family { // structure for family
    string lastName;
    string address;
    node members // head of list of members of this family
}

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

famNode := Families // start at head of families list
while famNode ≠ null // loop through list of families
    aFamily := (family) famNode.data // extract family from node
    print information about family
    memNode := aFamily.members // get list of family members
    while memNode ≠ null // loop through list of members
        aMember := (member)memNode.data // extract member from node
        print information about member
        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 adequado. Isso ocorre porque a lista de famílias e a lista de membros dentro da família são armazenadas em duas listas vinculadas usando a mesma estrutura de dados ( ), e esta linguagem não possui tipos paramétricos.

Contanto que o número de famílias às quais um membro pode pertencer seja conhecido no momento da compilação, o armazenamento interno funciona 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, o armazenamento externo seria necessário.

Acelerando a pesquisa

Encontrar um elemento específico em uma lista encadeada, mesmo que seja classificado, normalmente requer tempo O ( n ) ( pesquisa linear ). Esta é uma das principais desvantagens das listas vinculadas 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 pesquisa é a heurística mover para a frente , que simplesmente move um elemento para o início da lista assim que é 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 novamente.

Outra abordagem comum é " indexar " uma lista vinculada usando uma estrutura de dados externa mais eficiente. Por exemplo, pode-se construir uma árvore vermelho-preto ou uma tabela hash cujos elementos são referências aos nós da lista vinculada. Vários desses índices podem ser construídos 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 de acesso aleatório binária skew usando o sistema numérico binário skew , 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. Listas de acesso aleatório podem ser implementadas como estruturas de dados persistentes .

As listas de acesso aleatório podem ser vistas como listas vinculadas imutáveis, pois da mesma forma suportam as mesmas operações O (1) de início e fim.

Uma extensão simples para listas de acesso aleatório é a lista mínima , 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 são frequentemente implementadas usando listas vinculadas e simplesmente restringem o tipo de operações com suporte.

A lista de pular é 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 vinculada em que os próprios elementos são listas vinculadas da mesma natureza. O resultado é que cada nó pode incluir uma referência ao primeiro nó de uma ou duas outras listas vinculadas, que, juntamente com seu conteúdo, formam as subárvores abaixo desse nó.

Uma lista encadeada desenrolada é uma lista encadeada 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 menor sobrecarga de memória, porque menos metadados precisam ser armazenados para cada elemento da lista.

Uma tabela hash pode usar listas vinculadas para armazenar as cadeias de itens que fazem hash na mesma posição na tabela hash.

Um heap compartilha algumas das propriedades de ordenação de uma lista vinculada, mas quase sempre é implementado usando uma matriz. 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 os tempos de busca para recuperação de dados, mantendo os nós comumente acessados ​​no topo da lista.

Notas

Referências

Leitura adicional

links externos