- La llista enllaçada es pot definir com una col·lecció d'objectes anomenada nodes que s'emmagatzemen aleatòriament a la memòria.
- Un node conté dos camps, és a dir, les dades emmagatzemades en aquesta adreça en particular i el punter que conté l'adreça del següent node a la memòria.
- L'últim node de la llista conté un punter al nul.
Usos de la llista enllaçada
- No cal que la llista estigui present de forma contigua a la memòria. El node pot residir en qualsevol lloc de la memòria i enllaçar entre ells per fer una llista. Això aconsegueix una utilització optimitzada de l'espai.
- La mida de la llista està limitada a la mida de la memòria i no cal declarar-la per endavant.
- El node buit no pot estar present a la llista enllaçada.
- Podem emmagatzemar valors de tipus o objectes primitius a la llista enllaçada individualment.
Per què utilitzar una llista enllaçada sobre la matriu?
Fins ara, estàvem utilitzant l'estructura de dades de matriu per organitzar el grup d'elements que s'han d'emmagatzemar individualment a la memòria. Tanmateix, Array té diversos avantatges i desavantatges que cal conèixer per decidir l'estructura de dades que s'utilitzarà al llarg del programa.
La matriu conté les limitacions següents:
- La mida de la matriu s'ha de conèixer per endavant abans d'utilitzar-la al programa.
- Augmentar la mida de la matriu és un procés que requereix temps. És gairebé impossible ampliar la mida de la matriu en temps d'execució.
- Tots els elements de la matriu s'han d'emmagatzemar de manera contigu a la memòria. La inserció de qualsevol element a la matriu necessita el canvi de tots els seus predecessors.
La llista enllaçada és l'estructura de dades que pot superar totes les limitacions d'una matriu. L'ús de la llista enllaçada és útil perquè,
for loop a bash
- Assigna la memòria de manera dinàmica. Tots els nodes de la llista enllaçada s'emmagatzemen de manera no contigua a la memòria i s'enllaçen amb l'ajuda de punters.
- La mida ja no és un problema ja que no cal definir-ne la mida en el moment de la declaració. La llista creix segons la demanda del programa i es limita a l'espai de memòria disponible.
Llista enllaçada individualment o cadena unidireccional
La llista enllaçada individualment es pot definir com la col·lecció d'un conjunt ordenat d'elements. El nombre d'elements pot variar segons la necessitat del programa. Un node de la llista enllaçada individualment consta de dues parts: part de dades i part d'enllaç. La part de dades del node emmagatzema informació real que ha de ser representada pel node mentre que la part d'enllaç del node emmagatzema l'adreça del seu successor immediat.
bucle do i while a java
La cadena unidireccional o la llista enllaçada individualment només es pot recórrer en una direcció. En altres paraules, podem dir que cada node conté només el punter següent, per tant, no podem recórrer la llista en sentit invers.
Considereu un exemple on les notes obtingudes per l'estudiant en tres assignatures s'emmagatzemen en una llista enllaçada tal com es mostra a la figura.
A la figura anterior, la fletxa representa els enllaços. La part de dades de cada node conté les notes obtingudes per l'estudiant en les diferents assignatures. L'últim node de la llista s'identifica amb el punter nul que està present a la part d'adreça de l'últim node. Podem tenir tants elements que necessitem, a la part de dades de la llista.
Complexitat
| Estructura de dades | Complexitat temporal | Complet de l'espai | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Mitjana | El pitjor | El pitjor | |||||||
| Accés | Cerca | Inserció | Eliminació | Accés | Cerca | Inserció | Eliminació | ||
| Llista enllaçada individualment | i(n) | i(n) | i (1) | i (1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Operacions en llista enllaçada individualment
Hi ha diverses operacions que es poden realitzar en una llista enllaçada individualment. A continuació es mostra una llista de totes aquestes operacions.
programa c per matriu bidimensional
Creació de nodes
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Inserció
La inserció en una llista enllaçada individualment es pot realitzar en diferents posicions. En funció de la posició del nou node que s'està inserint, la inserció es classifica en les categories següents.
| SN | Funcionament | Descripció |
|---|---|---|
| 1 | Inserció al començament | Implica inserir qualsevol element al capdavant de la llista. Només necessitem uns quants ajustos d'enllaç per fer que el nou node sigui el cap de la llista. |
| 2 | Inserció al final de la llista | Implica la inserció a l'últim de la llista enllaçada. El nou node es pot inserir com l'únic node de la llista o es pot inserir com a darrer. En cada escenari s'implementen diferents lògiques. |
| 3 | Inserció després del node especificat | Implica la inserció després del node especificat de la llista enllaçada. Hem de saltar el nombre desitjat de nodes per arribar al node després del qual s'inserirà el nou node. . |
Eliminació i travessa
La supressió d'un node d'una llista enllaçada individualment es pot realitzar en diferents posicions. En funció de la posició del node que s'elimina, l'operació es classifica en les categories següents.
| SN | Funcionament | Descripció |
|---|---|---|
| 1 | Eliminació al principi | Implica la supressió d'un node des de l'inici de la llista. Aquesta és l'operació més senzilla de totes. Només necessita uns quants ajustos als punters del node. |
| 2 | Eliminació al final de la llista | Implica esborrar l'últim node de la llista. La llista pot estar buida o plena. S'implementa una lògica diferent per als diferents escenaris. |
| 3 | Supressió després del node especificat | Implica suprimir el node després del node especificat a la llista. hem de saltar el nombre desitjat de nodes per arribar al node després del qual se suprimirà el node. Això requereix recórrer la llista. |
| 4 | Travessant | En el recorregut, simplement visitem cada node de la llista almenys una vegada per tal de realitzar-hi alguna operació específica, per exemple, imprimir part de dades de cada node present a la llista. |
| 5 | Buscant | En la cerca, fem coincidir cada element de la llista amb l'element donat. Si l'element es troba en qualsevol de les ubicacions, es retorna la ubicació d'aquest element, en cas contrari es retorna null. . |
Llista enllaçada a C: Programa impulsat per menús
#include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
Enter the location of the node after which you want to perform deletion
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } Sortida:
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9