• Propojený seznam lze definovat jako kolekci nazvaných objektů uzly které jsou náhodně uloženy v paměti.
• Uzel obsahuje dvě pole, tj. data uložená na této konkrétní adrese a ukazatel, který obsahuje adresu dalšího uzlu v paměti.
• Poslední uzel seznamu obsahuje ukazatel na hodnotu null.

Použití propojeného seznamu

• Seznam nemusí být souvisle přítomen v paměti. Uzel může být umístěn kdekoli v paměti a může být propojen, aby vytvořil seznam. Tím je dosaženo optimálního využití prostoru.
• velikost seznamu je omezena na velikost paměti a není třeba ji deklarovat předem.
• V propojeném seznamu nemůže být prázdný uzel.
• Hodnoty primitivních typů nebo objektů můžeme ukládat do jednoduše propojeného seznamu.

Proč používat propojený seznam přes pole?

Doposud jsme používali datovou strukturu pole k uspořádání skupiny prvků, které mají být jednotlivě uloženy v paměti. Pole má však několik výhod a nevýhod, které je třeba znát, aby bylo možné rozhodnout o struktuře dat, která bude v programu použita.

Pole obsahuje následující omezení:

1. Před použitím v programu musí být velikost pole známa předem.
2. Zvětšení velikosti pole je časově náročný proces. Je téměř nemožné rozšířit velikost pole za běhu.
3. Všechny prvky v poli musí být souvisle uloženy v paměti. Vložení libovolného prvku do pole vyžaduje posunutí všech jeho předchůdců.

Linked list je datová struktura, která dokáže překonat všechna omezení pole. Použití propojeného seznamu je užitečné, protože

nerovná se mysql

1. Dynamicky přiděluje paměť. Všechny uzly propojeného seznamu jsou nesouvisle uloženy v paměti a propojeny pomocí ukazatelů.
2. Velikost již není problém, protože nepotřebujeme definovat její velikost v době deklarace. Seznam roste podle požadavků programu a je omezen na dostupnou paměť.

Jednosměrný seznam nebo jednosměrný řetězec

Jednotlivě propojený seznam lze definovat jako kolekci uspořádané sady prvků. Počet prvků se může lišit podle potřeby programu. Uzel v jednoduše propojeném seznamu se skládá ze dvou částí: datové části a odkazové části. Datová část uzlu uchovává aktuální informace, které má uzel reprezentovat, zatímco linková část uzlu ukládá adresu jeho bezprostředního nástupce.

mb vs gb

Jednosměrný řetězec nebo jednotlivě propojený seznam lze procházet pouze jedním směrem. Jinými slovy, můžeme říci, že každý uzel obsahuje pouze další ukazatel, proto nemůžeme seznam procházet v opačném směru.

Zvažte příklad, kdy jsou známky získané studentem ve třech předmětech uloženy v propojeném seznamu, jak je znázorněno na obrázku.

Na obrázku výše šipka představuje odkazy. Datová část každého uzlu obsahuje známky získané studentem v jiném předmětu. Poslední uzel v seznamu je identifikován nulovým ukazatelem, který je přítomen v adresové části posledního uzlu. V datové části seznamu můžeme mít tolik prvků, kolik potřebujeme.

Složitost

Operace na Jednotně propojeném seznamu

Existují různé operace, které lze provádět na jednotlivě propojeném seznamu. Seznam všech takových operací je uveden níže.

vytvoření pole řetězců v jazyce Java

Vytvoření uzlu

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

Vložení

Vložení do jednoduše propojeného seznamu může být provedeno na různých pozicích. Na základě pozice vkládaného nového uzlu je vkládání kategorizováno do následujících kategorií.

Mazání a procházení

Odstranění uzlu z jednoduše propojeného seznamu lze provést na různých pozicích. Na základě pozice mazaného uzlu je operace kategorizována do následujících kategorií.

Propojený seznam v C: Program řízený 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ýstup:

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