A połączona lista to rodzaj liniowej dynamicznej struktury danych, której używamy do przechowywania elementów danych. Tablice są także rodzajem liniowej struktury danych, w której elementy danych są przechowywane w ciągłych blokach pamięci.
W przeciwieństwie do tablic, lista połączona nie musi przechowywać elementów danych w sąsiadujących obszarach lub blokach pamięci.
A połączona lista składa się z elementów zwanych „węzłami”, które są podzielone na dwie części. Pierwszy komponent to część, w której przechowujemy rzeczywiste dane, a drugi to część, w której przechowujemy wskaźnik do następnego węzła. Ten typ konstrukcji nazywany jest „ pojedynczo połączona lista .'
Połączona lista w C++
W tym samouczku szczegółowo omówimy listę pojedynczo połączoną.
Strukturę listy pojedynczo połączonej przedstawiono na poniższym diagramie
- Jak widzieliśmy w powyższej części, pierwszy węzeł połączonej listy nazywany jest „głową”, natomiast ostatni węzeł nazywany jest „ogonem”. Dzieje się tak, ponieważ w ostatnim węźle nie określono adresu pamięci, końcowy węzeł połączonej listy będzie miał zerowy wskaźnik następnego.
- Ponieważ każdy węzeł zawiera wskaźnik do następnego węzła, elementy danych na połączonej liście nie muszą być przechowywane w sąsiadujących lokalizacjach. Węzły mogą być rozproszone w całej pamięci. Ponieważ każdy węzeł ma adres następnego, możemy uzyskać do niego dostęp, kiedy tylko chcemy.
- Możemy szybko dodawać i usuwać elementy danych z połączonej listy. W rezultacie połączona lista może dynamicznie się zwiększać lub kurczyć. Połączona lista nie ma maksymalnej liczby elementów danych, jakie może zawierać. W rezultacie możemy dodać dowolną liczbę elementów danych do połączonej listy, o ile dostępna jest pamięć RAM.
- Ponieważ nie musimy z góry określać, ile elementów potrzebujemy na liście połączonej, lista połączona oszczędza miejsce w pamięci, a ponadto jest łatwa do wstawiania i usuwania. Jedynym miejscem używanym przez połączoną listę jest przechowywanie wskaźnika do następnego węzła, co wiąże się z pewnymi kosztami.
Następnie omówimy różne operacje, które można wykonać na połączonej liście.
1) Wstawienie
Połączona lista rozwija się poprzez operację dodania do niej. Choć wydawałoby się to proste, biorąc pod uwagę strukturę listy połączonej, wiemy, że za każdym razem, gdy dodawany jest element danych, musimy zmienić kolejne wskaźniki poprzedniego i następnego węzła nowo dodanego elementu.
Drugim aspektem, o którym należy pomyśleć, jest miejsce, w którym zostanie wstawiony nowy element danych.
Multiplekser 2 do 1
Istnieją trzy miejsca, w których można dodać element danych do połączonej listy.
A. Zacznij od połączonej listy
Poniżej znajduje się połączona lista liczb 2->4->6->8->10. Głowa wskazująca na węzeł 2 będzie teraz wskazywać na węzeł 1, a następny wskaźnik węzła 1 będzie miał adres pamięci węzła 2, jak pokazano na poniższej ilustracji, jeśli dodamy nowy węzeł 1 jako pierwszy węzeł na liście .
W rezultacie nowa lista połączona to 1->2->4->6->8->10.
B. Po danym Node
W tym przypadku otrzymujemy węzeł i musimy za nim dodać nowy węzeł. Połączona lista będzie wyglądać następująco, jeśli węzeł f zostanie dodany do połączonej listy a->b->c->d->e po węźle c:
Dlatego sprawdzamy, czy określony węzeł występuje na powyższym schemacie. Jeśli jest obecny, tworzony jest nowy węzeł f. Następnie wskazujemy następny wskaźnik węzła c na zupełnie nowy węzeł f. Następny wskaźnik węzła f wskazuje teraz na węzeł d.
C. Ostatni element listy połączonej
W trzecim przypadku na końcu połączonej listy dodawany jest nowy węzeł. Weź pod uwagę powiązaną listę poniżej: a->b->c->d->e, z dodatkiem węzła f na końcu. Po dodaniu węzła połączona lista będzie wyglądać następująco.
usuń plik w Javie
W rezultacie konstruujemy nowy węzeł f. Wskaźnik końcowy prowadzący do wartości null jest następnie wskazywany na f, a następny wskaźnik węzła f jest wskazywany na wartość null. W poniższym języku programowania wygenerowaliśmy wszystkie trzy typy funkcji wstawiania.
Połączoną listę można zadeklarować jako strukturę lub klasę w C++. Połączona lista zadeklarowana jako struktura jest klasyczną instrukcją w stylu C. Połączona lista jest używana jako klasa we współczesnym C++, głównie podczas korzystania ze standardowej biblioteki szablonów.
Struktura została wykorzystana w poniższej aplikacji do zadeklarowania i wygenerowania połączonej listy. Jej członkami będą dane i wskaźnik do kolejnego elementu.
Program w C++:
bash, jeśli warunek
#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) Usunięcie
Podobnie jak w przypadku wstawiania, usunięcie węzła z połączonej listy wymaga wielu punktów, z których można wyeliminować węzeł. Możemy losowo usunąć pierwszy, ostatni lub k-ty węzeł połączonej listy. Musimy poprawnie zaktualizować następny wskaźnik i wszystkie inne powiązane wskaźniki list, aby zachować połączoną listę po usunięciu.
W poniższej implementacji C++ mamy dwie metody usuwania: usunięcie początkowego węzła listy i usunięcie ostatniego węzła listy. Zaczynamy od dodania węzłów na początku listy. Zawartość listy jest następnie wyświetlana po każdym dodaniu i usunięciu.
Program w C++:
#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> Liczba węzłów
Podczas przechodzenia przez listę połączoną można wykonać proces zliczania liczby węzłów. W poprzednim podejściu widzieliśmy, że jeśli musieliśmy wstawić/usunąć węzeł lub wyświetlić zawartość połączonej listy, musieliśmy przejść przez połączoną listę od początku.
Ustawienie licznika i inkrementacja oraz przechodzenie przez każdy węzeł zapewni nam liczbę węzłów na połączonej liście.
Różnice między tablicą a listą połączoną:
| Szyk | Połączona lista |
|---|---|
| Tablice mają określony rozmiar. | Rozmiar połączonej listy jest zmienny. |
| Wstawienie nowego elementu jest trudne. | Wstawianie i usuwanie jest prostsze. |
| Dostęp jest dozwolony losowo. | Nie ma możliwości dostępu losowego. |
| Elementy znajdują się stosunkowo blisko siebie lub sąsiadują ze sobą. | Elementy nie sąsiadują ze sobą. |
| Dla następującego wskaźnika nie jest wymagane żadne dodatkowe miejsce. | Poniższy wskaźnik wymaga dodatkowej pamięci. |
Funkcjonalność
Ponieważ połączone listy i tablice są liniowymi strukturami danych przechowującymi obiekty, można je wykorzystywać w podobny sposób w większości zastosowań.
Poniżej przedstawiono kilka przykładów zastosowań list połączonych:
- Stosy i kolejki można implementować za pomocą list połączonych.
- Kiedy potrzebujemy wyrazić wykresy jako listy sąsiedztwa, możemy użyć listy połączonej, aby je zaimplementować.
- Listy połączonej można także używać do przechowywania wielomianu matematycznego.
- W przypadku mieszania do implementacji segmentów wykorzystywane są listy połączone.
- Gdy program wymaga dynamicznej alokacji pamięci, możemy skorzystać z listy połączonej, ponieważ w tym przypadku listy połączone są bardziej wydajne.
Wniosek
Listy połączone to struktury danych używane do przechowywania elementów danych w formie liniowej, ale nieciągłej. Połączona lista składa się z węzłów, z których każdy składa się z dwóch komponentów. Pierwszy komponent składa się z danych, natomiast druga połowa zawiera wskaźnik przechowujący adres pamięci kolejnego elementu listy.
Na znak, że połączona lista się zakończyła, ostatni element na liście ma swój następny wskaźnik ustawiony na NULL. Głowa jest pierwszą pozycją na liście. Połączona lista umożliwia różnorodne działania, takie jak wstawianie, usuwanie, przeglądanie i tak dalej. Listy połączone są preferowane w stosunku do tablic w przypadku dynamicznej alokacji pamięci.
Listy połączone są trudne do wydrukowania lub przeglądania, ponieważ nie możemy uzyskać dostępu do elementów losowo, jak tablice. W porównaniu z tablicami procedury wstawiania i usuwania są tańsze.
W tym samouczku dowiedzieliśmy się wszystkiego, co trzeba wiedzieć o listach połączonych liniowo. Połączone listy mogą być również podwójnie połączone lub okrągłe. W naszych nadchodzących tutorialach szczegółowo omówimy te listy.