А зв'язаний список це свого роду лінійна динамічна структура даних, яку ми використовуємо для зберігання елементів даних. Масиви також є типом лінійної структури даних, де елементи даних зберігаються в безперервних блоках пам’яті.
На відміну від масивів, зв’язаному списку не потрібно зберігати елементи даних у безперервних областях чи блоках пам’яті.
А зв'язаний список складається з елементів, відомих як «Вузли», які розділені на дві частини. Перший компонент — це частина, де ми зберігаємо фактичні дані, а друга — частина, де ми зберігаємо покажчик на наступний вузол. Цей тип структури відомий як однозв'язаний список .'
Зв'язаний список у C++
У цьому підручнику буде детально розглянуто однозв’язаний список.
масив структури мовою c
Структуру однозв’язаного списку показано на схемі нижче
- Як ми бачили у наведеній вище частині, перший вузол пов’язаного списку відомий як «голова», тоді як останній вузол називається «хвостом». Оскільки в останньому вузлі не вказано адресу пам’яті, останній вузол пов’язаного списку матиме нульовий наступний покажчик.
- Оскільки кожен вузол містить покажчик на наступний вузол, елементи даних у зв’язаному списку не потрібно зберігати в безперервних розташуваннях. Вузли можуть бути розосереджені по пам'яті. Оскільки кожен вузол має адресу наступного за ним, ми можемо отримати доступ до вузлів, коли забажаємо.
- Ми можемо швидко додавати та видаляти елементи даних із підключеного списку. У результаті пов’язаний список може динамічно збільшуватися або звужуватися. Зв’язаний список не має максимальної кількості елементів даних, які він може містити. У результаті ми можемо додавати скільки завгодно елементів даних до пов’язаного списку, якщо є доступна оперативна пам’ять.
- Оскільки нам не потрібно заздалегідь вказувати, скільки елементів нам потрібно у зв’язаному списку, зв’язаний список економить місце в пам’яті, а його просто вставляти та видаляти. Єдиний простір, який використовується зв’язаним списком, — це зберігання покажчика на наступний вузол, що додає певних витрат.
Після цього ми розглянемо різні операції, які можна виконувати у зв’язаному списку.
1) Вставка
Зв’язаний список розширюється шляхом додавання до нього. Хоча це здається простим, враховуючи структуру пов’язаного списку, ми знаємо, що кожного разу, коли додається елемент даних, ми повинні змінити наступні покажчики попереднього та наступного вузлів нового елемента, який ми додали.
Де буде вставлено новий елемент даних, це другий аспект, про який слід подумати.
Є три місця, де елемент даних можна додати до пов’язаного списку.
a. Починаючи зі зв'язаного списку
Нижче наведено пов’язаний список чисел 2->4->6->8->10. Голова, яка вказує на вузол 2, тепер вказуватиме на вузол 1, а наступний покажчик вузла 1 матиме адресу пам’яті вузла 2, як показано на ілюстрації нижче, якщо ми додамо новий вузол 1 як перший вузол у списку .
python зберегти json у файл
У результаті новий пов’язаний список має вигляд 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 у кінці. Після додавання вузла пов’язаний список відобразиться таким чином.
питання співбесіди мовою java
У результаті будуємо новий вузол 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++:
скільки нулів в 1 мільярді
#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> Кількість вузлів
Під час обходу пов’язаного списку можна виконати процес підрахунку кількості вузлів. У попередньому підході ми побачили, що якщо нам потрібно вставити/видалити вузол або відобразити вміст зв’язаного списку, нам потрібно було пройти пов’язаний список із самого початку.
Встановлення лічильника та збільшення, а також проходження кожного вузла дадуть нам кількість вузлів у зв’язаному списку.
Відмінності між масивом і зв'язаним списком:
| Масив | Зв'язаний список |
|---|---|
| Масиви мають визначений розмір. | Розмір зв'язаного списку є змінним. |
| Вставити новий елемент складно. | Вставлення та видалення простіше. |
| Доступ дозволено випадковим чином. | Випадковий доступ неможливий. |
| Елементи знаходяться відносно близько або суміжно. | Елементи не є суміжними. |
| Для наступного вказівника додаткова кімната не потрібна. | Для наступного покажчика потрібна додаткова пам'ять. |
Функціональність
Оскільки пов’язані списки та масиви є лінійними структурами даних, які містять об’єкти, їх можна використовувати подібним чином для більшості програм.
Нижче наведено кілька прикладів додатків зі зв’язаним списком:
- Стеки та черги можна реалізувати за допомогою пов’язаних списків.
- Коли нам потрібно виразити графіки як списки суміжності, ми можемо використовувати зв’язаний список для їх реалізації.
- Ми також можемо використовувати пов’язаний список, щоб містити математичний поліном.
- У разі хешування зв’язані списки використовуються для реалізації сегментів.
- Коли програмі потрібен динамічний розподіл пам’яті, ми можемо використовувати зв’язаний список, оскільки зв’язані списки в цьому випадку більш ефективні.
Висновок
Зв’язані списки — це структури даних, які використовуються для зберігання елементів даних у лінійній, але несуміжній формі. Зв’язаний список складається з вузлів з двома компонентами кожен. Перший компонент складається з даних, а друга половина має покажчик, який зберігає адресу пам’яті наступного члена списку.
rdbms
Як ознака того, що пов’язаний список закінчився, для останнього елемента списку наступний вказівник має значення NULL. Голова - перший пункт у списку. Зв’язаний список дозволяє виконувати різні дії, такі як вставка, видалення, обхід тощо. Для динамічного розподілу пам’яті зв’язані списки мають перевагу над масивами.
Зв’язані списки важко надрукувати або пройти, оскільки ми не можемо отримати довільний доступ до елементів, як до масивів. У порівнянні з масивами процедури вставки-видалення менш дорогі.
У цьому підручнику ми дізналися все, що потрібно знати про лінійні пов’язані списки. Зв’язані списки також можуть бути подвійними або кільцевими. У наших наступних посібниках ми детально розглянемо ці списки.