• Linked List možno definovať ako kolekciu objektov tzv uzly ktoré sú náhodne uložené v pamäti.
• Uzol obsahuje dve polia, t. j. dáta uložené na tejto konkrétnej adrese a ukazovateľ, ktorý obsahuje adresu nasledujúceho uzla v pamäti.
• Posledný uzol zoznamu obsahuje ukazovateľ na nulu.

Použitie prepojeného zoznamu

• Nevyžaduje sa, aby bol zoznam súvisle prítomný v pamäti. Uzol sa môže nachádzať kdekoľvek v pamäti a môže byť prepojený, aby vytvoril zoznam. Tým sa dosiahne optimálne využitie priestoru.
• veľkosť zoznamu je obmedzená na veľkosť pamäte a nemusí byť deklarovaná vopred.
• Prázdny uzol nemôže byť prítomný v prepojenom zozname.
• V jednoducho prepojenom zozname môžeme ukladať hodnoty primitívnych typov alebo objektov.

Prečo používať prepojený zoznam cez pole?

Doteraz sme používali dátovú štruktúru poľa na usporiadanie skupiny prvkov, ktoré mali byť uložené jednotlivo v pamäti. Avšak Array má niekoľko výhod a nevýhod, ktoré musia byť známe, aby bolo možné rozhodnúť o dátovej štruktúre, ktorá sa bude používať v programe.

Pole obsahuje nasledujúce obmedzenia:

1. Veľkosť poľa musí byť známa vopred pred jeho použitím v programe.
2. Zväčšenie veľkosti poľa je časovo náročný proces. Je takmer nemožné rozšíriť veľkosť poľa za behu.
3. Všetky prvky v poli musia byť súvisle uložené v pamäti. Vloženie akéhokoľvek prvku do poľa vyžaduje posunutie všetkých jeho predchodcov.

Prepojený zoznam je dátová štruktúra, ktorá dokáže prekonať všetky obmedzenia poľa. Používanie prepojeného zoznamu je užitočné, pretože

reťazec na znak java

1. Dynamicky prideľuje pamäť. Všetky uzly prepojeného zoznamu sú nesúvisle uložené v pamäti a prepojené pomocou ukazovateľov.
2. Určenie veľkosti už nie je problém, pretože nemusíme definovať jej veľkosť v čase deklarácie. Zoznam rastie podľa požiadaviek programu a je obmedzený na dostupnú pamäť.

Jednosmerný zoznam alebo jednosmerný reťazec

Jednotlivo prepojený zoznam možno definovať ako kolekciu usporiadanej množiny prvkov. Počet prvkov sa môže meniť podľa potreby programu. Uzol v jednoducho prepojenom zozname pozostáva z dvoch častí: dátovej časti a prepojenej časti. Dátová časť uzla uchováva aktuálne informácie, ktoré má uzol reprezentovať, zatiaľ čo odkazová časť uzla ukladá adresu jeho bezprostredného nástupcu.

Jednosmerný reťazec alebo jednotlivo prepojený zoznam možno prechádzať iba jedným smerom. Inými slovami, môžeme povedať, že každý uzol obsahuje iba ďalší ukazovateľ, takže zoznam nemôžeme prechádzať v opačnom smere.

diagram modelu e-r

Uvažujme o príklade, kde sú známky získané študentom v troch predmetoch uložené v prepojenom zozname, ako je znázornené na obrázku.

Na obrázku vyššie šípka predstavuje prepojenia. Dátová časť každého uzla obsahuje známky, ktoré študent získal v inom predmete. Posledný uzol v zozname je identifikovaný nulovým ukazovateľom, ktorý sa nachádza v časti adresy posledného uzla. V dátovej časti zoznamu môžeme mať toľko prvkov, koľko požadujeme.

porovnať reťazec java

Zložitosť

Operácie na samostatne prepojenom zozname

Existujú rôzne operácie, ktoré možno vykonávať na jednotlivo prepojenom zozname. Zoznam všetkých takýchto operácií je uvedený nižšie.

Vytvorenie uzla

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

Vkladanie

Vkladanie do jednoducho prepojeného zoznamu sa môže vykonávať na rôznych pozíciách. Na základe polohy vkladaného nového uzla je vkladanie kategorizované do nasledujúcich kategórií.

Odstránenie a prechod

Vymazanie uzla z jednotlivo prepojeného zoznamu možno vykonať na rôznych pozíciách. Na základe polohy uzla, ktorý sa odstraňuje, je operácia kategorizovaná do nasledujúcich kategórií.

Prepojený zoznam v C: Program riadený 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; } } } 

Výkon:

 *********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