- Povezani seznam je mogoče definirati kot zbirko objektov, imenovanih vozlišča ki so naključno shranjeni v pomnilniku.
- Vozlišče vsebuje dve polji, tj. podatke, shranjene na določenem naslovu, in kazalec, ki vsebuje naslov naslednjega vozlišča v pomnilniku.
- Zadnje vozlišče seznama vsebuje kazalec na nič.
Uporaba povezanega seznama
- Ni potrebno, da je seznam stalno prisoten v pomnilniku. Vozlišče se lahko nahaja kjer koli v pomnilniku in je med seboj povezano v seznam. S tem dosežemo optimalen izkoristek prostora.
- velikost seznama je omejena na velikost pomnilnika in je ni treba navesti vnaprej.
- Prazno vozlišče ne more biti prisotno na povezanem seznamu.
- V enojno povezan seznam lahko shranimo vrednosti primitivnih tipov ali objektov.
Zakaj uporabljati povezani seznam prek polja?
Do sedaj smo uporabljali matrično podatkovno strukturo za organiziranje skupine elementov, ki naj bodo posamezno shranjeni v pomnilniku. Vendar ima Array številne prednosti in slabosti, ki jih je treba poznati, da se odločimo za podatkovno strukturo, ki bo uporabljena v celotnem programu.
Matrika vsebuje naslednje omejitve:
- Velikost matrike je treba poznati vnaprej, preden jo uporabimo v programu.
- Povečanje velikosti niza je dolgotrajen proces. Med izvajanjem je skoraj nemogoče povečati velikost matrike.
- Vsi elementi v nizu morajo biti neprekinjeno shranjeni v pomnilniku. Vstavljanje katerega koli elementa v matriko zahteva premik vseh njegovih predhodnikov.
Povezan seznam je podatkovna struktura, ki lahko premaga vse omejitve matrike. Uporaba povezanega seznama je koristna, ker
objektivna java
- Pomnilnik dodeljuje dinamično. Vsa vozlišča povezanega seznama so neprekinjeno shranjena v pomnilniku in med seboj povezana s pomočjo kazalcev.
- Dimenzioniranje ni več problem, saj nam velikosti ni treba določiti ob deklaraciji. Seznam raste glede na zahteve programa in je omejen na razpoložljivi pomnilniški prostor.
Posamezno povezan seznam ali enosmerna veriga
Posamezno povezan seznam lahko definiramo kot zbirko urejenih nizov elementov. Število elementov se lahko razlikuje glede na potrebe programa. Vozlišče na enojno povezanem seznamu je sestavljeno iz dveh delov: podatkovnega dela in povezovalnega dela. Podatkovni del vozlišča shranjuje dejanske informacije, ki naj bi jih vozlišče predstavljalo, medtem ko povezovalni del vozlišča shranjuje naslov svojega neposrednega naslednika.
Enosmerno verigo ali enosmerno povezan seznam je mogoče prehoditi samo v eno smer. Z drugimi besedami, lahko rečemo, da vsako vozlišče vsebuje samo naslednji kazalec, zato ne moremo prečkati seznama v obratni smeri.
Razmislite o primeru, kjer so ocene, ki jih je študent dosegel pri treh predmetih, shranjene na povezanem seznamu, kot je prikazano na sliki.
python oz
Na zgornji sliki puščica predstavlja povezave. Podatkovni del vsakega vozlišča vsebuje ocene, ki jih je dijak dosegel pri posameznem predmetu. Zadnje vozlišče na seznamu je označeno z ničelnim kazalcem, ki je prisoten v naslovnem delu zadnjega vozlišča. V podatkovnem delu seznama imamo lahko poljubno število elementov.
Kompleksnost
| Struktura podatkov | Časovna zapletenost | Prostor Compleity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Povprečje | Najslabše | Najslabše | |||||||
| Dostop | Iskanje | Vstavljanje | Izbris | Dostop | Iskanje | Vstavljanje | Izbris | ||
| Posamezno povezan seznam | jaz (n) | jaz (n) | i(1) | i(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
Operacije na posamično povezanem seznamu
Obstajajo različne operacije, ki jih je mogoče izvesti na enojno povezanem seznamu. Spodaj je naveden seznam vseh takih operacij.
Ustvarjanje vozlišča
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Vstavljanje
Vstavljanje v enojno povezan seznam je mogoče izvesti na različnih mestih. Glede na položaj novega vozlišča, ki ga vstavljate, je vstavljanje kategorizirano v naslednje kategorije.
prenesite medijski predvajalnik youtube vlc
| SN | Delovanje | Opis |
|---|---|---|
| 1 | Vstavljanje na začetku | Vključuje vstavljanje katerega koli elementa na začetek seznama. Potrebujemo le nekaj prilagoditev povezave, da bo novo vozlišče postalo glava seznama. |
| 2 | Vnos na koncu seznama | Vključuje vstavljanje na zadnji strani povezanega seznama. Novo vozlišče se lahko vstavi kot edino vozlišče na seznamu ali pa kot zadnje. V vsakem scenariju se izvajajo različne logike. |
| 3 | Vstavljanje po določenem vozlišču | Vključuje vstavljanje za navedenim vozliščem povezanega seznama. Preskočiti moramo želeno število vozlišč, da dosežemo vozlišče, po katerem bo vstavljeno novo vozlišče. . |
Brisanje in prečkanje
Brisanje vozlišča iz enojno povezanega seznama je mogoče izvesti na različnih mestih. Glede na položaj vozlišča, ki se briše, je operacija razvrščena v naslednje kategorije.
| SN | Delovanje | Opis |
|---|---|---|
| 1 | Izbris na začetku | Vključuje izbris vozlišča z začetka seznama. To je najpreprostejša operacija med vsemi. Potrebuje le nekaj prilagoditev v kazalcih vozlišč. |
| 2 | Izbris na koncu seznama | Vključuje brisanje zadnjega vozlišča seznama. Seznam je lahko prazen ali poln. Za različne scenarije se izvaja različna logika. |
| 3 | Izbris po določenem vozlišču | Vključuje brisanje vozlišča za navedenim vozliščem na seznamu. preskočiti moramo želeno število vozlišč, da dosežemo vozlišče, po katerem bo vozlišče izbrisano. To zahteva premikanje po seznamu. |
| 4 | Prečenje | Pri prečkanju preprosto obiščemo vsako vozlišče seznama vsaj enkrat, da na njem izvedemo določeno operacijo, na primer tiskanje podatkovnega dela vsakega vozlišča, ki je prisotno na seznamu. |
| 5 | Iskanje | Pri iskanju povežemo vsak element seznama z danim elementom. Če je element najden na kateri koli lokaciji, je vrnjena lokacija tega elementa, sicer je vrnjena vrednost null. . |
Povezani seznam v C: Program, ki ga poganja meni
#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; } } } Izhod:
*********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