- Povezani popis može se definirati kao kolekcija objekata tzv čvorovi koji su nasumično pohranjeni u memoriji.
- Čvor sadrži dva polja, tj. podatke pohranjene na toj adresi i pokazivač koji sadrži adresu sljedećeg čvora u memoriji.
- Zadnji čvor liste sadrži pokazivač na nulu.
Upotreba povezanog popisa
- Popis ne mora biti kontinuirano prisutan u memoriji. Čvor se može nalaziti bilo gdje u memoriji i međusobno povezati kako bi napravio popis. Time se postiže optimalno iskorištenje prostora.
- veličina popisa je ograničena na veličinu memorije i ne treba je deklarirati unaprijed.
- Prazan čvor ne može biti prisutan na povezanom popisu.
- Vrijednosti primitivnih tipova ili objekata možemo pohraniti u jednostruko povezani popis.
Zašto koristiti povezani popis preko polja?
Do sada smo koristili strukturu podataka niza za organiziranje grupe elemenata koji će biti pojedinačno pohranjeni u memoriji. Međutim, Array ima nekoliko prednosti i nedostataka koji se moraju znati kako bi se odlučila struktura podataka koja će se koristiti u cijelom programu.
Niz sadrži sljedeća ograničenja:
- Veličina niza mora biti poznata unaprijed prije korištenja u programu.
- Povećanje veličine niza dugotrajan je proces. Gotovo je nemoguće proširiti veličinu niza tijekom izvođenja.
- Svi elementi u nizu trebaju biti kontinuirano pohranjeni u memoriji. Umetanje bilo kojeg elementa u niz zahtijeva pomicanje svih njegovih prethodnika.
Povezani popis je struktura podataka koja može prevladati sva ograničenja niza. Korištenje povezanog popisa je korisno jer,
java spojiti s mysql
- Dinamički dodjeljuje memoriju. Svi čvorovi povezane liste su neprekinuto pohranjeni u memoriju i međusobno povezani uz pomoć pokazivača.
- Veličina više nije problem jer ne moramo definirati veličinu prilikom deklaracije. Popis raste prema zahtjevima programa i ograničen je na raspoloživi memorijski prostor.
Pojedinačno povezana lista ili jednosmjerni lanac
Jednostruko povezana lista može se definirati kao zbirka uređenog skupa elemenata. Broj elemenata može varirati ovisno o potrebama programa. Čvor na pojedinačno povezanoj listi sastoji se od dva dijela: podatkovnog dijela i povezničkog dijela. Podatkovni dio čvora pohranjuje stvarne informacije koje čvor treba predstaviti, dok poveznički dio čvora pohranjuje adresu svog neposrednog nasljednika.
Jednosmjerni lanac ili jednostruko povezana lista mogu se proći samo u jednom smjeru. Drugim riječima, možemo reći da svaki čvor sadrži samo sljedeći pokazivač, stoga ne možemo preći popis u obrnutom smjeru.
java popis od
Razmotrimo primjer u kojem su ocjene koje je učenik postigao u tri predmeta pohranjene na povezanom popisu kao što je prikazano na slici.
Na gornjoj slici strelica predstavlja veze. Podatkovni dio svakog čvora sadrži ocjene koje je učenik postigao iz određenog predmeta. Posljednji čvor na popisu identificiran je nultim pokazivačem koji je prisutan u adresnom dijelu posljednjeg čvora. U podatkovnom dijelu liste možemo imati onoliko elemenata koliko nam je potrebno.
javascript komentar
Složenost
| Struktura podataka | Vremenska složenost | Kompletnost prostora | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Prosjek | Najgori | Najgori | |||||||
| Pristup | traži | Umetanje | Brisanje | Pristup | traži | Umetanje | Brisanje | ||
| Pojedinačno povezani popis | u) | u) | i(1) | i(1) | Na) | Na) | O(1) | O(1) | Na) |
Operacije na pojedinačno povezanom popisu
Postoje različite operacije koje se mogu izvesti na pojedinačno povezanom popisu. Popis svih takvih operacija dan je u nastavku.
Stvaranje čvora
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Umetanje
Umetanje u jednostruko povezani popis može se izvesti na različitim pozicijama. Na temelju položaja novog čvora koji se umeće, umetanje se kategorizira u sljedeće kategorije.
| S N | Operacija | Opis |
|---|---|---|
| 1 | Umetanje na početku | To uključuje umetanje bilo kojeg elementa na početku popisa. Trebamo napraviti samo nekoliko prilagodbi veze kako bi novi čvor postao glavni na popisu. |
| 2 | Umetanje na kraj popisa | To uključuje umetanje na zadnjem mjestu povezanog popisa. Novi čvor se može umetnuti kao jedini čvor na popisu ili se može umetnuti kao posljednji. U svakom scenariju implementirane su različite logike. |
| 3 | Umetanje nakon navedenog čvora | Uključuje umetanje nakon navedenog čvora povezanog popisa. Potrebno je preskočiti željeni broj čvorova kako bismo došli do čvora nakon kojeg će se umetnuti novi čvor. . |
Brisanje i prelaženje
Brisanje čvora s pojedinačno povezanog popisa može se izvesti na različitim pozicijama. Na temelju položaja čvora koji se briše, operacija je kategorizirana u sljedeće kategorije.
| S N | Operacija | Opis |
|---|---|---|
| 1 | Brisanje na početku | Uključuje brisanje čvora s početka popisa. Ovo je najjednostavnija operacija od svih. Potrebno je samo nekoliko prilagodbi u pokazivačima čvorova. |
| 2 | Brisanje na kraju popisa | To uključuje brisanje posljednjeg čvora popisa. Popis može biti prazan ili pun. Za različite scenarije implementirana je različita logika. |
| 3 | Brisanje nakon navedenog čvora | To uključuje brisanje čvora nakon navedenog čvora na popisu. trebamo preskočiti željeni broj čvorova da bismo došli do čvora nakon čega će čvor biti izbrisan. Ovo zahtijeva kretanje kroz popis. |
| 4 | Prelaženje | U obilasku jednostavno posjećujemo svaki čvor popisa barem jednom kako bismo na njemu izvršili neku specifičnu operaciju, na primjer, ispis podatkovnog dijela svakog čvora prisutnog na popisu. |
| 5 | Traženje | Prilikom pretraživanja spajamo svaki element popisa s danim elementom. Ako se element pronađe na bilo kojoj lokaciji, tada se vraća lokacija tog elementa, inače se vraća null. . |
Povezani popis u C: Program vođen izbornicima
#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; } } } Izlaz:
*********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