А свързан списък е вид линейна динамична структура от данни, която използваме за съхраняване на елементи от данни. Масивите също са вид линейна структура от данни, където елементите от данни се съхраняват в непрекъснати блокове памет.
За разлика от масивите, свързаният списък не трябва да съхранява елементи от данни в съседни региони или блокове на паметта.
А свързан списък се състои от елементи, известни като „възли“, които са разделени на две части. Първият компонент е частта, в която съхраняваме действителните данни, а втората е част, в която съхраняваме указателя към следващия възел. Този тип структура е известна като ' единично свързан списък .'
Свързан списък в C++
Този урок ще разгледа в дълбочина единично свързания списък.
стек java
Структурата на единично свързан списък е илюстрирана на диаграмата по-долу
- Както видяхме в горната част, първият възел на свързания списък е известен като „глава“, докато последният възел се нарича „опашка“. Тъй като в последния възел не е указан адрес на паметта, последният възел на свързания списък ще има нулев следващ указател.
- Тъй като всеки възел включва указател към следващия възел, елементите от данни в свързания списък не е необходимо да се запазват в съседни местоположения. Възлите могат да бъдат разпръснати в паметта. Тъй като всеки възел има адреса на този след него, можем да имаме достъп до възлите, когато пожелаем.
- Можем бързо да добавяме и премахваме елементи с данни от свързания списък. В резултат на това свързаният списък може да се увеличава или свива динамично. Свързаният списък няма максимално количество елементи от данни, които може да съдържа. В резултат на това можем да добавяме толкова елементи с данни, колкото желаем към свързания списък, стига да има налична RAM памет.
- Тъй като не е необходимо да указваме колко елемента са ни необходими в свързания списък предварително, свързаният списък спестява място в паметта, освен че е лесен за вмъкване и изтриване. Единственото пространство, използвано от свързан списък, е за съхраняване на указателя към следващия възел, което добавя известна цена.
След това ще разгледаме различните операции, които могат да бъдат извършени в свързан списък.
1) Вмъкване
Свързаният списък се разширява чрез действието на добавяне към него. Въпреки че изглежда просто, като се има предвид структурата на свързания списък, знаем, че всеки път, когато се добавя елемент от данни, трябва да променим следващите указатели на предишния и следващия възел на новия елемент, който сме добавили.
Къде ще бъде вмъкнат новият елемент от данни е вторият аспект, за който трябва да помислите.
Има три места, където може да се добави елемент от данни към свързания списък.
а. Започвайки със свързания списък
По-долу е свързан списък на числата 2->4->6->8->10. Главата, сочеща към възел 2, сега ще сочи към възел 1, а следващият указател на възел 1 ще има адреса на паметта на възел 2, както е показано на илюстрацията по-долу, ако добавим нов възел 1 като първи възел в списъка .
обръщане на низ в c
В резултат на това новият свързан списък е 1->2->4->6->8->10.
b. След дадения възел
В този случай ни е даден възел и трябва да добавим нов възел зад него. Свързаният списък ще изглежда както следва, ако възел f се добави към свързания списък a->b->c->d->e след възел c:
Затова проверяваме дали посоченият възел присъства в диаграмата по-горе. Ако е налице, се създава нов възел f. След това насочваме следващия указател на възел c към чисто новия възел f. Следващият указател на възел f сега сочи към възел d.
° С. Последният елемент от свързания списък
В третия случай в края на свързания списък се добавя нов възел. Вземете под внимание свързания списък по-долу: a->b->c->d->e, с добавяне на възел f в края. След добавяне на възела, свързаният списък ще изглежда така.
правене на shell скрипт изпълним
В резултат на това изграждаме нов възел f. Крайният указател, водещ до null, след това се насочва към f, а следващият указател на възел f се насочва към null. В езика за програмиране по-долу сме генерирали и трите типа функции за вмъкване.
Свързаният списък може да бъде деклариран като структура или като клас в C++. Свързаният списък, деклариран като структура, е класически оператор в стил C. Свързаният списък се използва като клас в съвременния C++, главно когато се използва стандартната библиотека с шаблони.
Структурата беше използвана в следното приложение за деклариране и генериране на свързан списък. Неговите членове ще бъдат данни и указател към следния елемент.
C++ програма:
#include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -> data = nodeData; newNode1 -> next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -> next; prevNode -> next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -> data = nodeData; newNode1 -> next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -> next != NULL ) last = last -> next; last -> next = newNode1; return; } void displayList ( struct Node *node ) { while ( node != NULL ) { cout <data <'; node="node" -> next; } if ( node== NULL) cout<next, 55 ); cout << 'final linked list: ' endl; displaylist (head); return 0; } < pre> <p> <strong>Output:</strong> </p> <pre> Final linked list: 35-->25-->55-->15-->45-->null </pre> <h3>2) Deletion</h3> <p>Similar to insertion, deleting a node from a linked list requires many points from which the node might be eliminated. We can remove the linked list's first, last, or kth node at random. We must correctly update the next pointer and all other linked list pointers in order to maintain the linked list after deletion.</p> <p>In the following C++ implementation, we have two deletion methods: deleting the list's initial node and deleting the list's last node. We begin by adding nodes to the head of the list. The list's contents are then shown following each addition and deletion.</p> <p> <strong>C++ Program:</strong> </p> <pre> #include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <'; if ( temp="=" null ) cout << 'null' endl; head="deletingFirstNode" (head); 'linked list after deleting node' < next <data cout<<'null'<<endl; last data 'null'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data></pre></next,></data></data> 2) Изтриване
Подобно на вмъкването, изтриването на възел от свързан списък изисква много точки, от които възелът може да бъде елиминиран. Можем произволно да премахнем първия, последния или k-тия възел на свързания списък. Трябва правилно да актуализираме следващия указател и всички други указатели на свързани списъци, за да поддържаме свързания списък след изтриване.
В следната реализация на C++ имаме два метода за изтриване: изтриване на началния възел на списъка и изтриване на последния възел на списъка. Започваме с добавяне на възли към началото на списъка. След това съдържанието на списъка се показва след всяко добавяне и изтриване.
C++ програма:
java коментари
#include using namespace std; struct Node { int data; struct Node* next; }; Node* deletingFirstNode ( struct Node* head ) { if ( head == NULL ) return NULL; Node* tempNode = head; head = head -> next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -> next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -> next -> next != NULL ) secondLast = secondLast->next; delete ( secondLast -> next ); secondLast -> next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -> data = newData; newNode1 -> next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &head, 25 ); push ( &head, 45 ); push ( &head, 65); push ( &head, 85 ); push ( &head, 95 ); Node* temp; cout << 'Linked list created ' < next ) cout <data <\'; if ( temp="=" null ) cout << \'null\' endl; head="deletingFirstNode" (head); \'linked list after deleting node\' < next <data cout<<\'null\'<<endl; last data \'null\'; return 0; } pre> <p> <strong>Output:</strong> </p> <pre> Linked list created 95-->85-->65-->45-->25-->NULL Linked list after deleting head node 85-->65-->45-->25-->NULL Linked list after deleting last node 85-->65-->45-->NULL </pre> <h3>Node Count</h3> <p>While traversing the linked list, the process of counting the number of nodes can be performed. In the preceding approach, we saw that if we needed to insert/delete a node or display the contents of the linked list, we had to traverse the linked list from the beginning.</p> <p>Setting a counter and incrementing as well as we traverse each node will provide us the number of nodes in the linked list.</p> <h3>Differences between Array and Linked list:</h3> <table class="table"> <tr> <th>Array</th> <th>Linked list</th> </tr> <tr> <td>Arrays have a defined size.</td> <td>The size of the linked list is variable.</td> </tr> <tr> <td>Inserting a new element is difficult.</td> <td>Insertion and deletion are simpler.</td> </tr> <tr> <td>Access is permitted at random.</td> <td>No random access is possible.</td> </tr> <tr> <td>Elements are in relatively close or contiguous.</td> <td>The elements are not contiguous.</td> </tr> <tr> <td>No additional room is required for the following pointer.</td> <td>The following pointer requires additional memory.</td> </tr> </table> <h3>Functionality</h3> <p>Since linked lists and arrays are both linear data structures that hold objects, they can be utilised in similar ways for the majority of applications.</p> <p>The following are some examples of linked list applications:</p> <ul> <li>Stacks and queues can be implemented using linked lists.</li> <li>When we need to express graphs as adjacency lists, we can use a linked list to implement them.</li> <li>We can also use a linked list to contain a mathematical polynomial.</li> <li>In the case of hashing, linked lists are employed to implement the buckets.</li> <li>When a programme requires dynamic memory allocation, we can utilize a linked list because linked lists are more efficient in this instance.</li> </ul> <h2>Conclusion</h2> <p>Linked lists are data structures used to hold data elements in a linear but non-contiguous form. A linked list is made up of nodes with two components each. The first component is made up of data, while the second half has a pointer that stores the memory address of the following member of the list.</p> <p>As a sign that the linked list has ended, the last item in the list has its next pointer set to NULL. The Head is the first item on the list. The linked list allows for a variety of actions such as insertion, deletion, traversal, and so on. Linked lists are favoured over arrays for dynamic memory allocation.</p> <p>Linked lists are hard to print or traverse because we can't access the elements randomly like arrays. When compared to arrays, insertion-deletion procedures are less expensive.</p> <p>In this tutorial, we learned everything there is to know about linear linked lists. Linked lists can also be doubly linked or circular. In our forthcoming tutorials, we will go through these lists in detail.</p> <hr></data> Брой възли
Докато обхождате свързания списък, може да се извърши процесът на преброяване на броя на възлите. В предходния подход видяхме, че ако трябва да вмъкнем/изтрием възел или да покажем съдържанието на свързания списък, трябваше да преминем през свързания списък от самото начало.
Задаването на брояч и увеличаването, както и преминаването през всеки възел, ще ни предостави броя на възлите в свързания списък.
Разлики между масив и свързан списък:
| Масив | Свързан списък |
|---|---|
| Масивите имат определен размер. | Размерът на свързания списък е променлив. |
| Вмъкването на нов елемент е трудно. | Вмъкването и изтриването са по-лесни. |
| Достъпът е разрешен на случаен принцип. | Не е възможен произволен достъп. |
| Елементите са относително близки или съседни. | Елементите не са съседни. |
| Не е необходимо допълнително място за следния показалец. | Следният указател изисква допълнителна памет. |
Функционалност
Тъй като свързаните списъци и масиви са линейни структури от данни, които съдържат обекти, те могат да се използват по подобен начин за повечето приложения.
Следват някои примери за свързани списъчни приложения:
- Стекове и опашки могат да бъдат реализирани с помощта на свързани списъци.
- Когато трябва да изразим графики като списъци със съседство, можем да използваме свързан списък, за да ги реализираме.
- Можем също да използваме свързан списък, за да съдържа математически полином.
- В случай на хеширане, свързани списъци се използват за внедряване на кофи.
- Когато една програма изисква динамично разпределение на паметта, можем да използваме свързан списък, защото свързаните списъци са по-ефективни в този случай.
Заключение
Свързаните списъци са структури от данни, използвани за съхраняване на елементи от данни в линейна, но несвързана форма. Свързаният списък се състои от възли с по два компонента. Първият компонент се състои от данни, докато втората половина има указател, който съхранява адреса на паметта на следващия член на списъка.
alter добави колона oracle
Като знак, че свързаният списък е приключил, следващият указател на последния елемент в списъка е зададен на NULL. Главата е първият елемент в списъка. Свързаният списък позволява различни действия като вмъкване, изтриване, обхождане и т.н. Свързаните списъци са предпочитани пред масивите за динамично разпределение на паметта.
Свързаните списъци са трудни за отпечатване или преминаване, защото не можем да имаме произволен достъп до елементите като масиви. В сравнение с масивите процедурите за вмъкване-изтриване са по-евтини.
В този урок научихме всичко, което трябва да знаем за линейните свързани списъци. Свързаните списъци също могат да бъдат двойно свързани или кръгови. В нашите предстоящи уроци ще разгледаме подробно тези списъци.