TechCodeview

• Свързаният списък може да се дефинира като колекция от обекти, наречени възли които се съхраняват произволно в паметта.
• Възелът съдържа две полета, т.е. данни, съхранени на този конкретен адрес, и указателя, който съдържа адреса на следващия възел в паметта.
• Последният възел на списъка съдържа указател към нулата.

Използване на свързан списък

• Не е необходимо списъкът да присъства непрекъснато в паметта. Възелът може да се намира навсякъде в паметта и да бъде свързан заедно, за да направи списък. Така се постига оптимизирано оползотворяване на пространството.
• размерът на списъка е ограничен до размера на паметта и не е необходимо да се декларира предварително.
• Празният възел не може да присъства в свързания списък.
• Можем да съхраняваме стойности на примитивни типове или обекти в единично свързания списък.

Защо да използвате свързан списък върху масив?

Досега използвахме масивна структура от данни, за да организираме групата от елементи, които трябва да се съхраняват индивидуално в паметта. Въпреки това, Array има няколко предимства и недостатъци, които трябва да се знаят, за да се реши структурата на данните, която ще се използва в цялата програма.

Масивът съдържа следните ограничения:

1. Размерът на масива трябва да се знае предварително, преди да се използва в програмата.
2. Увеличаването на размера на масива е отнемащ време процес. Почти невъзможно е да се разшири размерът на масива по време на изпълнение.
3. Всички елементи в масива трябва да се съхраняват непрекъснато в паметта. Вмъкването на всеки елемент в масива изисква изместване на всички негови предшественици.

Свързаният списък е структурата от данни, която може да преодолее всички ограничения на масива. Използването на свързан списък е полезно, защото,

множество нули

1. Разпределя паметта динамично. Всички възли на свързания списък се съхраняват непоследователно в паметта и се свързват заедно с помощта на указатели.
2. Оразмеряването вече не е проблем, тъй като не е необходимо да определяме размера му в момента на деклариране. Списъкът расте според търсенето на програмата и е ограничен до наличното пространство в паметта.

Единично свързан списък или еднопосочна верига

Единично свързаният списък може да се дефинира като колекция от подреден набор от елементи. Броят на елементите може да варира според нуждите на програмата. Възелът в единично свързания списък се състои от две части: част с данни и част с връзка. Частта с данни на възела съхранява действителна информация, която трябва да бъде представена от възела, докато частта за връзка на възела съхранява адреса на неговия непосредствен наследник.

Еднопосочната верига или единично свързаният списък могат да бъдат преминавани само в една посока. С други думи, можем да кажем, че всеки възел съдържа само следващ указател, следователно не можем да преминем през списъка в обратна посока.

Помислете за пример, при който оценките, получени от ученика по три предмета, се съхраняват в свързан списък, както е показано на фигурата.

mamta kulkarni

В горната фигура стрелката представлява връзките. Частта с данни на всеки възел съдържа оценките, получени от ученика по различни предмети. Последният възел в списъка се идентифицира от нулевия указател, който присъства в адресната част на последния възел. Можем да имаме толкова елементи, които изискваме, в частта с данни на списъка.

Сложност

Операции върху единично свързан списък

Има различни операции, които могат да се извършват върху единично свързан списък. По-долу е даден списък на всички подобни операции.

Създаване на възел

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

Вмъкване

Вмъкването в единично свързан списък може да се извърши на различни позиции. Въз основа на позицията на новия възел, който се вмъква, вмъкването се категоризира в следните категории.

Шрея Гошал

Изтриване и преминаване

Изтриването на възел от единично свързан списък може да се извърши на различни позиции. Въз основа на позицията на възела, който се изтрива, операцията се категоризира в следните категории.

Свързан списък в C: Програма, управлявана от менюто

 #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