Lista ligada

Lista ligada
Instancia de Estrutura de dados vinculada (pt)  Subclase de lista  Composto por ponteiro (pt) nó (pt)
Implicados  Inventor/a ou descubridor/a Allen Newell Cliff Shaw (pt) Herbert A. Simon
Datas  Fundación / creación 1955
Fontes e ligazóns Freebase /m/04m5_ OpenAlex C146101286
Wikidata C:Commons

Unha lista ligada é unha secuencia de nós que conteñen dous campos: os datos (un valor enteiro neste exemplo) e unha ligazón ao nó seguinte. O último nó enlázase cun terminador que indica o final da lista.

En ciencias da computación, unha lista ligada é unha colección linear de elementos cuxa orde non vén dada pola súa posición física na memoria. No canto diso, cada elemento apunta ao seguinte. É unha estrutura de datos formada por unha colección de nós que, xuntos, representan unha secuencia. Na súa forma máis básica, cada nó contén datos e unha referencia (é dicir, unha ligazón) ao nó seguinte da secuencia. Esta estrutura permite inserir ou eliminar elementos de calquera posición da secuencia de forma eficiente durante a iteración. As variantes máis complexas engaden ligazóns adicionais, permitindo inserir ou eliminar nós en posicións arbitrarias de forma máis eficiente. Un inconveniente das listas ligadas é que o tempo de acceso aos datos é linear respecto do número de nós. Como os nós están ligados en serie, acceder a calquera nó require acceder antes ao anterior. Non é posible un acceso máis rápido, como o acceso aleatorio. Os vectores teñen mellor localidade de referencia cá lista ligada.

As listas ligadas están entre as estruturas de datos máis simples e comúns. Pódense usar para implementar outros tipos de datos abstractos, como listas, pilas, colas, táboas asociativas e expresión S, aínda que non é raro implementar esas estruturas directamente sen usar unha lista ligada como base.

O principal beneficio dunha lista ligada fronte a un vector convencional é que os elementos se poden inserir ou eliminar doadamente sen reasignar nin reorganizar toda a estrutura, porque os datos non necesitan estar contiguos en memoria ou disco. Os nós poden ocupar posicións contiguas ou dispersas: a orde lóxica da lista determínana as ligazóns entre eles, non a súa posición física.

Pola contra, como as listas ligadas simples non permiten o acceso aleatorio nin unha indexación eficiente, moitas operacións básicas —como obter o último nó, atopar un nó cun dato dado ou localizar o lugar onde inserir un novo nó— poden requirir percorrer os elementos.

Historia

O encadeamento da información precede á era dixital. Xa na época homérica, os copistas de papiros indicaban a orde de lectura escribindo ao final dun rolo a primeira palabra do rolo seguinte. A práctica reapareceu nos primeiros anos da imprenta mecánica en Europa, cando era común incluír ao final de cada páxina unha «palabra de reclamo» correspondente á primeira da páxina seguinte.

A primeira implementación do encadeamento no contexto informático desenvolveuse entre 1955 e 1956 por Allen Newell, Cliff Shaw e Herbert A. Simon na RAND Corporation e na Universidade Carnegie Mellon, como estrutura de datos principal da súa Information Processing Language (IPL). IPL empregouse para desenvolver varios programas temperáns de intelixencia artificial, como a Logic Theory Machine, o General Problem Solver e un programa de xadrez.

Outra aparición temperá foi a de Hans Peter Luhn, que nun memorando interno de IBM de xaneiro de 1953 suxeriu o uso de listas ligadas en táboas hash con encadeamento.

LISP, acrónimo de list processor, foi creado por John McCarthy en 1958 no MIT e publicado en 1960. Unha das súas estruturas de datos principais é a lista ligada.

Conceptos básicos e nomenclatura

Cada rexistro dunha lista ligada adoita chamarse «elemento» ou «nó». O campo que contén a dirección do nó seguinte chámase «ligazón seguinte» ou «punteiro seguinte». Os demais campos coñécense como «datos», «información», «valor» ou «carga útil».

A «cabeza» da lista é o seu primeiro nó. A «cola» pode referirse ao resto da lista tras a cabeza ou ao último nó. En Lisp e algunhas linguaxes derivadas, o nó seguinte chámase «cdr» e a carga útil da cabeza, «car».

Lista ligada simple

As listas ligadas simples conteñen nós cun campo «valor» e un campo «seguinte» que apunta ao nó seguinte. As operacións que se poden realizar inclúen inserción, borrado e percorrido.

Unha lista ligada simple con nós que conteñen dous campos: un valor enteiro e unha ligazón ao nó seguinte.

O código C seguinte mostra como engadir un nó ao final dunha lista simple:

#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node* next;
} Node;

Node* addNodeToTail(Node* head, int value) {
    Node* temp = (Node*)malloc(sizeof *temp);
    if (temp == NULL) {
        abort(); // Este exemplo remata se non pode reservar memoria.
    }
    temp->value = value;
    temp->next = NULL;

    if (!head) {
        head = temp;
    } else {
        Node* p = head;
        while (p->next) {
            p = p->next;
        }
        p->next = temp;
    }
    return head;
}

Lista ligada dobre

Nunha «lista ligada dobre», cada nó contén, ademais da ligazón ao seguinte, un segundo campo que apunta ao nó «anterior». As dúas ligazóns poden chamarse «seguinte» e «anterior».

Unha lista ligada dobre con nós que conteñen tres campos: un valor enteiro, a ligazón ao seguinte e a ligazón ao anterior.

Unha técnica chamada ligazón XOR permite implementar unha lista dobre cun só campo de ligazón por nó, aínda que require operacións de bits sobre as direccións e, polo tanto, pode non estar dispoñible en linguaxes de alto nivel.

Moitos sistemas operativos modernos usan listas dobres para manter referencias a procesos, fíos e outros obxectos dinámicos.

Lista ligada múltiple

Nunha «lista ligada múltiple», cada nó contén dous ou máis campos de ligazón, cada un usado para conectar o mesmo conxunto de datos ordenado de forma distinta (por exemplo, por nome, por departamento, por data de nacemento).

Lista ligada circular

No último nó dunha lista, o campo de ligazón adoita conter unha referencia nula. Unha convención menos común é facelo apuntar ao primeiro nó; nese caso a lista dise «circular». Nunha lista circular dobre, o primeiro nó tamén apunta ao último.

Unha lista ligada circular.

Nós sentinela

Nalgunhas implementacións engádese un nó «sentinela» ou «ficticio» antes do primeiro rexistro ou despois do último. Isto simplifica algúns casos límite: por exemplo, unha lista circular cunha sentinela mantén sempre un nó accesible mesmo cando non contén datos. O uso dunha sentinela por si só non fai segura a desreferencia de calquera ligazón.

Listas baleiras

Unha lista baleira é a que non contén rexistros. Se se usan sentinelas, dise que está baleira cando só ten sentinelas.

Ligazóns en vectores separados

Os campos de ligazón non teñen por que formar parte fisicamente dos nós. Se os rexistros se gardan nun vector referenciados polos seus índices, o campo de ligazón pódese gardar nun vector separado cos mesmos índices.

Descritores de lista

Como unha referencia ao primeiro nó dá acceso a toda a lista, esa referencia chámase «dirección», «punteiro» ou «descritor». Nalgúns casos convén referirse a unha lista cun descritor formado por dúas ligazóns, ao primeiro e ao último nó.

Compromisos

Listas ligadas fronte a vectores dinámicos

Un vector dinámico asigna todos os elementos de forma contigua e mantén un contador do número de elementos. Se se supera o espazo reservado, reasígnase e (posiblemente) cópiase, o que é custoso.

As listas ligadas permiten insercións e borrados en tempo constante cando xa se dispón das ligazóns necesarias. Nunha lista simple, inserir despois dun nó require coñecelo, pero borrar un nó require tamén coñecer o seu predecesor, salvo ao borrar a cabeza. Nunha lista dobre, o propio nó fornece esa ligazón. Localizar previamente a posición pode levar . Nun vector dinámico, inserir nunha posición intermedia require desprazar os elementos posteriores e, cando se esgota a capacidade, pode ser necesario reasignar o vector.

Pola contra, os vectores dinámicos permiten acceso aleatorio en tempo constante, mentres que as listas ligadas só permiten acceso secuencial. O acceso secuencial nos vectores tamén é máis rápido, porque teñen mellor localidade de referencia.

Outro inconveniente das listas ligadas é o almacenamento extra para as referencias, o que a miúdo as fai pouco prácticas para elementos pequenos. Ademais pode ser lento asignar memoria por separado para cada elemento, problema que se resolve xeralmente con pools de memoria.

Algunhas solucións híbridas combinan as vantaxes das dúas representacións: as listas ligadas desenroladas gardan varios elementos en cada nó, mellorando o rendemento da caché e reducindo a sobrecarga de referencias.

Unha árbore equilibrada ten patróns de acceso e sobrecarga de espazo similares, pero permite unha indexación moito máis eficiente, en no canto de ; con todo, as insercións e os borrados son máis custosos.

Listas simples lineais fronte a outras listas

Unha lista simple linear é unha estrutura recursiva. Por iso, moitas operacións (como fusionar dúas listas ou enumerar os elementos en orde inversa) teñen algoritmos recursivos moi simples. As listas lineais simples tamén permiten a compartición de cola (tail-sharing), usando unha porción final común como parte terminal de dúas listas distintas. As variantes circulares e dobres non permiten isto.

Lista dobre fronte a simple

As listas dobres requiren máis espazo por nó e as súas operacións elementais son máis custosas, pero adoitan ser máis doadas de manipular porque permiten o acceso secuencial en ambas as direccións.

Lista circular fronte a lineal

Unha lista circular pode ser a opción natural para representar conxuntos inherentemente circulares, como os vértices dun polígono, un buffer FIFO ou un conxunto de procesos que se reparten en quenda rotatoria.

Uso de nós sentinela

Os nós sentinela poden simplificar certas operacións. Nunha lista dobre circular cunha sentinela, cada nó de datos ten sempre ligazóns anterior e seguinte válidas, mesmo nos extremos; isto non se deduce de engadir unha sentinela a calquera lista. Con todo, consomen espazo extra e poden complicar outras operacións.

Operacións

Ao manipular listas ligadas in situ, hai que ter coidado de non usar valores invalidados en asignacións previas.

• Inserción nunha lista simple: se se coñece o nó anterior, créase o novo nó, faise que a súa ligazón apunte ao nó seguinte do anterior e que a ligazón do anterior apunte ao novo.
• Borrado: localízase o nó, actualízase a ligazón do anterior para saltar o nó eliminado e libérase a súa memoria.
• Percorrido: pártese da cabeza e séguense as ligazóns «seguinte» ata chegar ao final.

Listas ligadas con vectores de nós

En lugar de asignar cada nó por separado, pódese reservar un vector de nós e usar índices no canto de punteiros. Este enfoque fai a lista reubicable, serializable e eficiente en espazo, aínda que crea un espazo de memoria privado e pode complicar o crecemento.

Soporte nas linguaxes

Moitas linguaxes, como Lisp e Scheme, teñen listas ligadas simples integradas. En moitas linguaxes funcionais, estas listas constrúense a partir de nós chamados cons. O cons ten dous campos: o car, referencia aos datos, e o cdr, referencia ao nó seguinte. Nas linguaxes que admiten tipos abstractos ou modelos, hai tipos ou modelos de lista ligada dispoñibles; noutras, constrúense con referencias e rexistros.

Almacenamento interno e externo

Ao construír unha lista ligada, hai que escoller entre gardar os datos directamente nos nós (almacenamento interno) ou gardar só unha referencia aos datos (almacenamento externo). O interno evita unha indirección adicional e pode aforrar espazo e asignacións cando os datos son pequenos e non se comparten. O externo permite usar a mesma estrutura para distintos tamaños de datos e facilita incluír os mesmos datos en varias listas.

En xeral, se un conxunto de datos ten que estar en varias listas, o almacenamento externo é a mellor opción.

Acelerar a busca

Atopar un elemento nunha lista ligada, mesmo ordenada, require normalmente (busca linear). Dúas formas simples de mellorar o tempo de busca son:

• A heurística de mover á fronte: cando se atopa un elemento, móvese ao comezo da lista. Isto garante que os elementos usados recentemente sexan os máis rápidos de atopar, útil para cachés sinxelas.
• Indexar a lista cunha estrutura externa máis eficiente, como unha árbore rubinegra ou unha táboa hash con referencias aos nós; o inconveniente é que hai que actualizar o índice cando se engade ou elimina un nó.

Listas de acceso aleatorio

Unha lista de acceso aleatorio admite acceso rápido para ler ou modificar calquera elemento. Unha implementación posible é a lista de acceso aleatorio binaria sesgada, que permite operacións de cabeza e cons de tempo constante no peor caso e acceso aleatorio logarítmico por índice. As listas de acceso aleatorio pódense implementar como estruturas de datos persistentes.

Estruturas de datos relacionadas

Tanto as pilas como as colas adoitan implementarse con listas ligadas, restrinxindo simplemente o tipo de operacións admitidas.

A skip list é unha lista ligada aumentada con capas de punteiros para saltar rapidamente sobre grandes números de elementos. Unha árbore binaria tamén pode enlazar nós mediante punteiros, pero organízaos xerarquicamente, non como unha lista linear. Unha lista ligada desenrolada é unha lista ligada na que cada nó contén un vector de valores de datos. Unha táboa hash pode usar listas ligadas para almacenar as cadeas de elementos que se dispersan na mesma posición. Unha lista autoorganizada reorganiza os seus nós segundo algunha heurística que reduce os tempos de busca.

Véxase tamén

Bibliografía

• Donald Knuth. The Art of Computer Programming, volume 1: Fundamental Algorithms, terceira edición, Addison-Wesley, 1997. ISBN 0-201-89683-4. Sección 2.2.3. (en inglés)
• Thomas H. Cormen et al. Introduction to Algorithms, segunda edición, MIT Press, 2001. Capítulo 10.2: «Linked lists», páxinas 204–209. ISBN 0-262-03293-7. (en inglés)
• Allen Newell e J. C. Shaw. «Programming the Logic Theory Machine», Proceedings of the Western Joint Computer Conference, páxinas 230–240, 1957. (en inglés)
• Robert Sedgewick. Algorithms in C, Addison Wesley, 1998, páxinas 90–109. ISBN 0-201-31452-5. (en inglés)
• Chris Okasaki. «Purely Functional Random-Access Lists», Proceedings of the seventh international conference on Functional programming languages and computer architecture (FPCA '95), ACM Press, páxinas 86–95, 1995, doi 10.1145/224164.224187. (en inglés)

Outros artigos

• Vector
• Lista ligada dobre
• Pila
• Cola
• Táboa hash
• Estrutura de datos persistente

Ligazóns externas

• Listas ligadas en Wikimedia Commons (en inglés)
• Open Data Structures – Listas ligadas, Pat Morin (en inglés)
• Linked list basics, Nick Parlante, Stanford University (en inglés)