- La lista collegata può essere definita come una raccolta di oggetti chiamati nodi che vengono memorizzati in modo casuale nella memoria.
- Un nodo contiene due campi, ovvero i dati memorizzati in quel particolare indirizzo e il puntatore che contiene l'indirizzo del nodo successivo nella memoria.
- L'ultimo nodo dell'elenco contiene il puntatore al null.
Usi della lista collegata
- Non è necessario che l'elenco sia presente in modo contiguo nella memoria. Il nodo può risiedere in qualsiasi punto della memoria e collegato insieme per creare un elenco. In questo modo si ottiene un utilizzo ottimizzato dello spazio.
- la dimensione dell'elenco è limitata alla dimensione della memoria e non è necessario dichiararla in anticipo.
- Il nodo vuoto non può essere presente nell'elenco collegato.
- Possiamo memorizzare valori di tipi o oggetti primitivi nell'elenco collegato singolarmente.
Perché utilizzare l'elenco collegato su array?
Fino ad ora utilizzavamo la struttura dati array per organizzare il gruppo di elementi che devono essere archiviati individualmente nella memoria. Tuttavia, Array presenta diversi vantaggi e svantaggi che devono essere conosciuti per decidere la struttura dei dati che verrà utilizzata nel programma.
L'array contiene le seguenti limitazioni:
- La dimensione dell'array deve essere nota in anticipo prima di utilizzarla nel programma.
- L'aumento delle dimensioni dell'array è un processo che richiede tempo. È quasi impossibile espandere la dimensione dell'array in fase di esecuzione.
- Tutti gli elementi dell'array devono essere archiviati in modo contiguo nella memoria. L'inserimento di qualsiasi elemento nell'array richiede lo spostamento di tutti i suoi predecessori.
L'elenco concatenato è la struttura dati in grado di superare tutte le limitazioni di un array. L'uso dell'elenco collegato è utile perché,
nodo dell'elenco Java
- Alloca la memoria in modo dinamico. Tutti i nodi della lista concatenata vengono archiviati in memoria in modo non contiguo e collegati tra loro con l'aiuto di puntatori.
- Il dimensionamento non è più un problema poiché non è necessario definirne la taglia al momento della dichiarazione. L'elenco cresce in base alla richiesta del programma e limitato allo spazio di memoria disponibile.
Elenco collegato singolarmente o catena unidirezionale
L'elenco collegato singolarmente può essere definito come la raccolta di insiemi ordinati di elementi. Il numero di elementi può variare a seconda delle necessità del programma. Un nodo nell'elenco collegato singolarmente è costituito da due parti: parte dati e parte collegamento. La parte dati del nodo memorizza le informazioni effettive che devono essere rappresentate dal nodo mentre la parte collegamento del nodo memorizza l'indirizzo del suo immediato successore.
Una catena unidirezionale o un elenco collegato singolarmente può essere attraversato solo in una direzione. In altre parole possiamo dire che ogni nodo contiene solo il puntatore successivo, quindi non possiamo percorrere la lista in senso inverso.
Consideriamo un esempio in cui i voti ottenuti dallo studente in tre materie sono memorizzati in un elenco collegato come mostrato in figura.
un milione in numeri
Nella figura sopra, la freccia rappresenta i collegamenti. La parte dati di ogni nodo contiene i voti ottenuti dallo studente nelle diverse materie. L'ultimo nodo della lista è identificato dal puntatore nullo presente nella parte dell'indirizzo dell'ultimo nodo. Possiamo avere tutti gli elementi di cui abbiamo bisogno, nella parte dati dell'elenco.
Complessità
| Struttura dati | Complessità temporale | Completezza spaziale | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Media | Peggio | Peggio | |||||||
| Accesso | Ricerca | Inserimento | Cancellazione | Accesso | Ricerca | Inserimento | Cancellazione | ||
| Elenco collegato singolarmente | In) | In) | io(1) | io(1) | SU) | SU) | O(1) | O(1) | SU) |
Operazioni su liste singolarmente collegate
Ci sono varie operazioni che possono essere eseguite su elenchi collegati singolarmente. Di seguito viene fornito un elenco di tutte queste operazioni.
Creazione del nodo
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Inserimento
L'inserimento in una lista singolarmente concatenata può essere effettuato in diverse posizioni. In base alla posizione del nuovo nodo da inserire, l'inserimento viene classificato nelle seguenti categorie.
css testo in grassetto
| SN | Operazione | Descrizione |
|---|---|---|
| 1 | Inserimento all'inizio | Implica l'inserimento di qualsiasi elemento all'inizio dell'elenco. Abbiamo solo bisogno di alcune modifiche al collegamento per rendere il nuovo nodo come capo dell'elenco. |
| 2 | Inserimento a fine lista | Prevede l'inserimento all'ultimo della lista collegata. Il nuovo nodo può essere inserito come unico nodo nella lista oppure può essere inserito come ultimo. In ogni scenario vengono implementate logiche diverse. |
| 3 | Inserimento dopo il nodo specificato | Implica l'inserimento dopo il nodo specificato della lista concatenata. Dobbiamo saltare il numero desiderato di nodi per raggiungere il nodo dopo il quale verrà inserito il nuovo nodo. . |
Cancellazione e attraversamento
La Cancellazione di un nodo da una lista singolarmente concatenata può essere effettuata in diverse posizioni. In base alla posizione del nodo da eliminare, l'operazione viene classificata nelle seguenti categorie.
| SN | Operazione | Descrizione |
|---|---|---|
| 1 | Cancellazione all'inizio | Implica la cancellazione di un nodo dall'inizio della lista. Questa è l'operazione più semplice tra tutte. Sono necessarie solo alcune modifiche ai puntatori dei nodi. |
| 2 | Cancellazione alla fine dell'elenco | Implica l'eliminazione dell'ultimo nodo della lista. L'elenco può essere vuoto o pieno. Viene implementata una logica diversa per i diversi scenari. |
| 3 | Cancellazione dopo il nodo specificato | Implica l'eliminazione del nodo dopo il nodo specificato nell'elenco. dobbiamo saltare il numero desiderato di nodi per raggiungere il nodo dopo il quale il nodo verrà eliminato. Ciò richiede l'attraversamento dell'elenco. |
| 4 | Attraversamento | Nell'attraversamento, visitiamo semplicemente ciascun nodo della lista almeno una volta per eseguire qualche operazione specifica su di esso, ad esempio stampare parte dei dati di ciascun nodo presente nella lista. |
| 5 | Ricerca | Nella ricerca, abbiniamo ogni elemento dell'elenco all'elemento specificato. Se l'elemento si trova in una qualsiasi delle posizioni, viene restituita la posizione di quell'elemento, altrimenti viene restituito null. . |
Elenco collegato in C: programma guidato da menu
#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; } } } Produzione:
*********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