TechCodeview

• Повезана листа се може дефинисати као збирка објеката која се зове чворови који се насумично чувају у меморији.
• Чвор садржи два поља, односно податке који се чувају на тој одређеној адреси и показивач који садржи адресу следећег чвора у меморији.
• Последњи чвор листе садржи показивач на нулу.

Употреба повезане листе

• Није потребно да листа буде непрекидно присутна у меморији. Чвор може да се налази било где у меморији и да се повеже заједно да направи листу. Тиме се постиже оптимално коришћење простора.
• величина листе је ограничена на величину меморије и не мора бити декларисана унапред.
• Празан чвор не може бити присутан у повезаној листи.
• Можемо да складиштимо вредности примитивних типова или објеката у појединачно повезаној листи.

Зашто користити повезану листу преко низа?

До сада смо користили структуру података низа да организујемо групу елемената који се појединачно чувају у меморији. Међутим, Арраи има неколико предности и мана које морају бити познате да би се одлучила структура података која ће се користити у целом програму.

Низ садржи следећа ограничења:

1. Величина низа мора бити позната унапред пре него што га употребите у програму.
2. Повећање величине низа је процес који одузима много времена. Скоро је немогуће проширити величину низа током извршавања.
3. Сви елементи у низу морају бити непрекидно ускладиштени у меморији. Уметање било ког елемента у низ захтева померање свих његових претходника.

Повезана листа је структура података која може превазићи сва ограничења низа. Коришћење повезане листе је корисно јер,

учините схелл скрипту извршном

1. Динамички додељује меморију. Сви чворови повезане листе су неповезано ускладиштени у меморији и повезани заједно уз помоћ показивача.
2. Величина више није проблем јер не морамо да дефинишемо њену величину у тренутку декларисања. Листа расте према захтевима програма и ограничена је на расположиви меморијски простор.

Једносмерна листа или једносмерни ланац

Једноструко повезана листа може се дефинисати као колекција уређеног скупа елемената. Број елемената може варирати у зависности од потреба програма. Чвор у једноструко повезаној листи састоји се од два дела: дела података и дела везе. Део података чвора чува стварне информације које треба да представи чвор, док део везе чвора чува адресу његовог непосредног наследника.

Једносмерни ланац или једноструко повезана листа може се прећи само у једном правцу. Другим речима, можемо рећи да сваки чвор садржи само следећи показивач, стога не можемо прећи листу у обрнутом смеру.

питхон писати јсон у датотеку

Размотримо пример где су оцене које је ученик добио из три предмета ускладиштене на повезаној листи као што је приказано на слици.

На горњој слици, стрелица представља везе. Део података сваког чвора садржи оцене које је ученик добио из различитог предмета. Последњи чвор на листи је идентификован нултом показивачем који је присутан у адресном делу последњег чвора. Можемо имати онолико елемената који су нам потребни у делу листе са подацима.

иеармонтх

Сложеност

Операције на појединачно повезаној листи

Постоје различите операције које се могу извршити на појединачно повезаној листи. Списак свих таквих операција је дат у наставку.

Креирање чвора

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

Инсертион

Уметање у једноструко повезану листу може се извршити на различитим позицијама. На основу позиције новог чвора који се убацује, уметање је категорисано у следеће категорије.

Брисање и прелазак

Брисање чвора са једноструко повезане листе може се извршити на различитим позицијама. На основу позиције чвора који се брише, операција је категорисана у следеће категорије.

Повезана листа у Ц: Програм вођен менијем

 #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; } } } 

Излаз:

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