- Lista legată poate fi definită ca o colecție de obiecte numită noduri care sunt stocate aleatoriu în memorie.
- Un nod conține două câmpuri, adică date stocate la acea anumită adresă și indicatorul care conține adresa următorului nod din memorie.
- Ultimul nod al listei conține pointer către nul.
Utilizări ale listei conectate
- Nu este necesar ca lista să fie prezentă continuu în memorie. Nodul poate locui oriunde în memorie și poate fi legat împreună pentru a face o listă. Acest lucru realizează o utilizare optimizată a spațiului.
- Mărimea listei este limitată la dimensiunea memoriei și nu trebuie să fie declarată în prealabil.
- Nodul gol nu poate fi prezent în lista legată.
- Putem stoca valori ale tipurilor sau obiectelor primitive în lista legată individual.
De ce să folosiți lista legată peste matrice?
Până acum, am folosit structura de date matrice pentru a organiza grupul de elemente care urmează să fie stocate individual în memorie. Cu toate acestea, Array are mai multe avantaje și dezavantaje care trebuie cunoscute pentru a decide structura de date care va fi utilizată pe tot parcursul programului.
Array conține următoarele limitări:
- Mărimea matricei trebuie cunoscută în prealabil înainte de a o utiliza în program.
- Creșterea dimensiunii matricei este un proces care necesită timp. Este aproape imposibil să extinzi dimensiunea matricei în timpul rulării.
- Toate elementele din matrice trebuie să fie stocate contiguu în memorie. Inserarea oricărui element în matrice necesită schimbarea tuturor predecesorilor săi.
Lista legată este structura de date care poate depăși toate limitările unui tablou. Utilizarea listei conectate este utilă deoarece,
conectează java cu mysql
- Aloca memoria dinamic. Toate nodurile listei legate sunt stocate necontiguu în memorie și legate între ele cu ajutorul pointerilor.
- Dimensionarea nu mai este o problemă, deoarece nu este nevoie să definim dimensiunea acesteia în momentul declarării. Lista crește în funcție de cererea programului și este limitată la spațiul de memorie disponibil.
Listă cu legături individuale sau lanț unidirecțional
Lista legată individual poate fi definită ca o colecție de set ordonat de elemente. Numărul de elemente poate varia în funcție de necesitatea programului. Un nod din lista legată individual este format din două părți: partea de date și partea de legătură. Partea de date a nodului stochează informații reale care urmează să fie reprezentate de nod, în timp ce partea de legătură a nodului stochează adresa succesorului său imediat.
Lanțul unidirecțional sau lista cu legături unice pot fi parcurse doar într-o singură direcție. Cu alte cuvinte, putem spune că fiecare nod conține doar indicatorul următor, prin urmare nu putem parcurge lista în sens invers.
10 din 100
Luați în considerare un exemplu în care notele obținute de student la trei materii sunt stocate într-o listă legată, așa cum se arată în figură.
În figura de mai sus, săgeata reprezintă legăturile. Partea de date a fiecărui nod conține notele obținute de student la diferite discipline. Ultimul nod din listă este identificat prin indicatorul nul care este prezent în partea de adresă a ultimului nod. Putem avea câte elemente avem nevoie, în partea de date a listei.
matrice de inițializare java
Complexitate
| Structură de date | Complexitatea timpului | Completitudine spațială | |||||||
|---|---|---|---|---|---|---|---|---|---|
| In medie | Cel mai rău | Cel mai rău | |||||||
| Acces | Căutare | Inserare | Ștergere | Acces | Căutare | Inserare | Ștergere | ||
| Lista legată individual | în) | în) | i(1) | i(1) | Pe) | Pe) | O(1) | O(1) | Pe) |
Operațiuni pe lista cu legături individuale
Există diverse operații care pot fi efectuate pe o listă unică. O listă a tuturor acestor operațiuni este prezentată mai jos.
Crearea nodului
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Inserare
Inserarea într-o listă unică legată poate fi efectuată în diferite poziții. Pe baza poziției noului nod care este inserat, inserția este clasificată în următoarele categorii.
| SN | Operațiune | Descriere |
|---|---|---|
| 1 | Inserarea la început | Implică inserarea oricărui element în fruntea listei. Trebuie doar să facem câteva ajustări de link pentru a face noul nod în fruntea listei. |
| 2 | Inserarea la sfarsitul listei | Implică inserarea la ultima dintre listele legate. Noul nod poate fi inserat ca singur nod din listă sau poate fi inserat ca ultimul. În fiecare scenariu sunt implementate logici diferite. |
| 3 | Inserarea după nodul specificat | Implică inserarea după nodul specificat al listei legate. Trebuie să sărim peste numărul dorit de noduri pentru a ajunge la nodul după care va fi inserat noul nod. . |
Ștergere și traversare
Ștergerea unui nod dintr-o listă legată individual poate fi efectuată în diferite poziții. Pe baza poziției nodului care este șters, operația este clasificată în următoarele categorii.
| SN | Operațiune | Descriere |
|---|---|---|
| 1 | Ștergere la început | Implica ștergerea unui nod de la începutul listei. Aceasta este cea mai simplă operație dintre toate. Are nevoie doar de câteva ajustări în indicatorii nodului. |
| 2 | Ștergere la sfârșitul listei | Implica ștergerea ultimului nod al listei. Lista poate fi fie goală, fie plină. Este implementată o logică diferită pentru diferitele scenarii. |
| 3 | Ștergerea după nodul specificat | Implica ștergerea nodului după nodul specificat din listă. trebuie să sărim peste numărul dorit de noduri pentru a ajunge la nodul după care nodul va fi șters. Acest lucru necesită parcurgerea listei. |
| 4 | Traversând | În parcurgere, pur și simplu vizităm fiecare nod al listei cel puțin o dată pentru a efectua o operație specifică asupra acestuia, de exemplu, imprimarea unei părți a datelor din fiecare nod prezent în listă. |
| 5 | In cautarea | În căutare, potrivim fiecare element al listei cu elementul dat. Dacă elementul este găsit în oricare dintre locații, atunci locația acelui element este returnată, altfel este returnat null. . |
Lista legată în C: Program condus de meniu
#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; } } } Ieșire:
*********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