• Зв'язаний список можна визначити як сукупність об'єктів, що викликаються вузлів які довільно зберігаються в пам’яті.
• Вузол містить два поля, тобто дані, що зберігаються за цією адресою, і покажчик, який містить адресу наступного вузла в пам’яті.
• Останній вузол списку містить покажчик на нуль.

Використання пов’язаного списку

• Список не обов’язково повинен постійно бути присутнім у пам’яті. Вузол може розташовуватися в будь-якій точці пам’яті та бути зв’язаним разом, щоб створити список. Таким чином досягається оптимальне використання простору.
• розмір списку обмежений розміром пам'яті, і його не потрібно оголошувати заздалегідь.
• Порожній вузол не може бути присутнім у зв'язаному списку.
• Ми можемо зберігати значення примітивних типів або об’єктів у однозв’язаному списку.

Навіщо використовувати пов’язаний список поверх масиву?

Дотепер ми використовували структуру даних масиву, щоб організувати групу елементів, які окремо зберігатимуться в пам’яті. Однак Array має кілька переваг і недоліків, які необхідно знати, щоб визначити структуру даних, яка використовуватиметься в програмі.

Масив містить такі обмеження:

1. Розмір масиву необхідно знати заздалегідь, перш ніж використовувати його в програмі.
2. Збільшення розміру масиву займає багато часу. Розширити розмір масиву під час виконання практично неможливо.
3. Усі елементи масиву необхідно зберігати в пам’яті безперервно. Вставка будь-якого елемента в масив потребує зсуву всіх його попередників.

Зв’язаний список — це структура даних, яка може подолати всі обмеження масиву. Використання пов’язаного списку корисне, оскільки

ascii в java

1. Він динамічно розподіляє пам'ять. Усі вузли зв’язаного списку несуміжно зберігаються в пам’яті та зв’язуються між собою за допомогою покажчиків.
2. Розмір більше не є проблемою, оскільки нам не потрібно визначати його розмір під час декларації. Список збільшується відповідно до вимог програми та обмежується доступним простором пам’яті.

Однозв’язаний список або односторонній ланцюг

Однозв’язаний список можна визначити як сукупність упорядкованого набору елементів. Кількість елементів може змінюватись залежно від потреб програми. Вузол у однозв’язаному списку складається з двох частин: частини даних і частини зв’язку. Частина даних вузла зберігає фактичну інформацію, яка має бути представлена ​​вузлом, тоді як частина зв’язку вузла зберігає адресу свого безпосереднього наступника.

Односторонній ланцюжок або однозв’язаний список можна пройти лише в одному напрямку. Іншими словами, ми можемо сказати, що кожен вузол містить лише наступний покажчик, тому ми не можемо пройти список у зворотному напрямку.

Розглянемо приклад, коли оцінки, отримані учнем із трьох предметів, зберігаються у зв’язаному списку, як показано на малюнку.

як відсортувати список масивів у java

На наведеному вище малюнку стрілка позначає посилання. Частина даних кожного вузла містить оцінки, отримані студентом з іншого предмета. Останній вузол у списку ідентифікується нульовим покажчиком, який присутній в адресній частині останнього вузла. Ми можемо мати скільки завгодно елементів у частині даних списку.

Складність

Операції над однозв’язаним списком

Існують різні операції, які можна виконувати над однозв’язаним списком. Список усіх таких операцій наведено нижче.

Створення вузла

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

Вставка

Вставлення в однозв’язаний список можна виконувати в різних позиціях. Залежно від положення нового вузла, який вставляється, вставлення класифікується на такі категорії.

рядок java для char

Видалення та обхід

Видалення вузла з однозв’язаного списку можна виконувати в різних позиціях. Залежно від положення вузла, який видаляється, операція поділяється на такі категорії.

Зв’язаний список у 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