miniatura|450px|alt=Unha lista ligada simple: cada nó ten un valor e unha ligazón ao seguinte.|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. miniatura|centro|450px|alt=Lista ligada simple con dous campos por nó.|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». miniatura|centro|450px|alt=Lista ligada dobre con tres campos por nó.|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. miniatura|centro|450px|alt=Lista ligada circular.|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.