Llista enllaçada és una estructura de dades lineal, en la qual els elements no s'emmagatzemen en una ubicació contigua, sinó que s'enllaçen mitjançant punters. La llista enllaçada forma una sèrie de nodes connectats, on cada node emmagatzema les dades i l'adreça del següent node.

Estructura del node: Un node d'una llista enllaçada normalment consta de dos components:
Dades: Conté el valor real o les dades associades amb el node.
Següent punter: Emmagatzema l'adreça de memòria (referència) del següent node de la seqüència.
Cap i cua: S'accedeix a la llista enllaçada a través del node principal, que apunta al primer node de la llista. L'últim node de la llista apunta a NULL o nullptr, que indica el final de la llista. Aquest node es coneix com el node de cua.

Per què cal una estructura de dades de llista enllaçada?

Aquests són alguns dels avantatges d'una llista enllaçada que s'enumeren a continuació, us ajudaran a entendre per què és necessari saber-ho.

• Estructura de dades dinàmiques: La mida de la memòria es pot assignar o desassignar en temps d'execució en funció de la inserció o supressió de l'operació.
• Facilitat d'inserció/eliminació: La inserció i la supressió d'elements són més senzilles que les matrius, ja que no cal desplaçar cap element després de la inserció i la supressió, només cal actualitzar l'adreça.
• Ús eficient de la memòria: Com sabem, la llista enllaçada és una estructura de dades dinàmica, la mida augmenta o disminueix segons el requisit, de manera que això evita el malbaratament de memòria.
• Implementació: Es poden implementar diverses estructures de dades avançades mitjançant una llista enllaçada com una pila, una cua, un gràfic, mapes hash, etc.

Exemple:

En un sistema, si mantenim una llista ordenada d'ID en una matriu id[] = [1000, 1010, 1050, 2000, 2040].

Si volem inserir un nou ID 1005, per mantenir l'ordre ordenat, haurem de moure tots els elements després de 1000 (excepte 1000).

La supressió també és cara amb les matrius fins que no s'utilitzen algunes tècniques especials. Per exemple, per suprimir 1010 a id[], tot després de 1010 s'ha de moure perquè s'està fent tanta feina que afecta l'eficiència del codi.

Tipus de llistes enllaçades :

Hi ha principalment tres tipus de llistes enllaçades:

1. Llista enllaçada única
2. Llista doble enllaçada
3. Llista enllaçada circular

1. Llista enllaçada única :

En una llista enllaçada individualment, cada node conté una referència al següent node de la seqüència. El recorregut d'una llista enllaçada individualment es fa en direcció cap endavant.

Llista enllaçada única

2. Llista de doble enllaç :

En una llista doblement enllaçada, cada node conté referències tant als nodes següents com als anteriors. Això permet el recorregut tant en direccions cap endavant com enrere, però requereix memòria addicional per a la referència cap enrere.

Llista de doble enllaç

3. Llista enllaçada circular :

En una llista enllaçada circular, l'últim node apunta cap al node principal, creant una estructura circular. Pot estar enllaçat individualment o doblement.

canviar el nom del directori de Linux

Llista enllaçada circular

Operacions sobre llistes enllaçades

1. Inserció : Afegir un nou node a una llista enllaçada implica ajustar els punters dels nodes existents per mantenir la seqüència adequada. La inserció es pot realitzar al principi, al final o a qualsevol posició de la llista
2. Supressió : L'eliminació d'un node d'una llista enllaçada requereix ajustar els punters dels nodes veïns per salvar el buit deixat pel node suprimit. La supressió es pot realitzar al principi, al final o a qualsevol posició de la llista.
3. Buscant : La cerca d'un valor específic en una llista enllaçada implica recórrer la llista des del node principal fins que es troba el valor o s'arriba al final de la llista.

Anàlisi de complexitat de la llista enllaçada :

• Complexitat temporal: O(n)
• Espai auxiliar: O(n)

Avantatges de les llistes enllaçades

• Mida dinàmica: Les llistes enllaçades poden créixer o reduir-se de forma dinàmica, ja que l'assignació de memòria es fa en temps d'execució.
• Inserció i eliminació: Afegir o eliminar elements d'una llista enllaçada és eficient, especialment per a llistes grans.
• Flexibilitat: Les llistes enllaçades es poden reorganitzar i modificar fàcilment sense requerir un bloc contigu de memòria.

Inconvenients de les llistes enllaçades

• Accés aleatori: A diferència de les matrius, les llistes enllaçades no permeten l'accés directe als elements per índex. La travessa és necessària per arribar a un node específic.
• Memòria extra: Les llistes enllaçades requereixen memòria addicional per emmagatzemar els punters, en comparació amb les matrius.

Conclusió:

Les llistes enllaçades són estructures de dades versàtils que proporcionen una assignació de memòria dinàmica i operacions d'inserció i supressió eficients. Comprendre els conceptes bàsics de les llistes enllaçades és essencial per a qualsevol programador o entusiasta de la informàtica. Amb aquest coneixement, podeu implementar llistes enllaçades per resoldre diversos problemes i ampliar la vostra comprensió de les estructures i algorismes de dades.