A linkelt lista egyfajta lineáris dinamikus adatstruktúra, amelyet adatelemek tárolására használunk. A tömbök egyfajta lineáris adatszerkezet is, ahol az adatelemeket folyamatos memóriablokkban tárolják.
A tömböktől eltérően a csatolt listának nem kell adatelemeket tárolnia összefüggő memóriarégiókban vagy blokkokban.
java arraylist rendezés
A linkelt lista „Csomópontok” néven ismert elemekből áll, amelyek két részre oszlanak. Az első komponens az a rész, ahol a tényleges adatokat tároljuk, a második pedig az a rész, ahol a következő csomópontra mutató mutatót tároljuk. Ezt a fajta szerkezetet ' egyenként linkelt lista .'
Linkelt lista C++ nyelven
Ez az oktatóanyag részletesen áttekinti az egyedileg kapcsolódó listát.
Az alábbi diagramon egy egyedi hivatkozású lista felépítése látható
- Ahogy a fenti részben láttuk, a hivatkozott lista első csomópontja a „fej”, míg az utolsó csomópont a „farok” néven ismert. Ez azért van, mert az utolsó csomópontban nincs megadva memóriacím, a linkelt lista utolsó csomópontja null következő mutatóval rendelkezik.
- Mivel minden csomópont tartalmaz egy mutatót a következő csomópontra, a csatolt lista adatelemeit nem kell összefüggő helyeken megőrizni. A csomópontok szétszórva lehetnek a memóriában. Mivel minden csomópontnak az utána lévő címe van, bármikor elérhetjük a csomópontokat.
- Gyorsan felvehetünk és eltávolíthatunk adatelemeket a csatlakoztatott listából. Ennek eredményeként a linkelt lista dinamikusan növekedhet vagy szűkülhet. A hivatkozott listában nincs maximális adatelemmennyiség, amelyet tartalmazhat. Ennek eredményeként tetszőleges számú adatelemet adhatunk a linkelt listához, amíg van rendelkezésre álló RAM.
- Mivel nem kell előre megadnunk, hogy hány elemre van szükségünk a hivatkozott listában, a hivatkozott lista amellett, hogy egyszerűen beszúrható és törölhető, memóriaterületet takarít meg. A csatolt listák egyetlen helye a következő csomópontra mutató mutató tárolása, ami némi költséggel jár.
Ezt követően egy linkelt listán áttekintjük a különféle műveleteket, amelyek végrehajthatók.
1) Beillesztés
A hivatkozott lista a hozzá való hozzáadással bővül. Bár egyszerűnek tűnik, a hivatkozott lista szerkezetét tekintve tudjuk, hogy minden alkalommal, amikor egy adatelemet adunk hozzá, módosítanunk kell a hozzáadott új elem előző és következő csomópontjának következő mutatóit.
A második szempont, hogy hová kerüljön az új adatelem.
Három helyen lehet adatelemet hozzáadni a hivatkozott listához.
a. Kezdve a linkelt listával
Az alábbiakban a 2->4->6->8->10 számok összekapcsolt listája látható. A 2. csomópontra mutató fej most az 1. csomópontra fog mutatni, és az 1. csomópont következő mutatója a 2. csomópont memóriacímével fog rendelkezni, ahogy az alábbi ábrán is látható, ha a lista első csomópontjaként hozzáadunk egy új 1-es csomópontot. .
Ennek eredményeként az új linkelt lista 1->2->4->6->8->10.
b. Az adott Node után
Ebben az esetben kapunk egy csomópontot, és hozzá kell adnunk egy új csomópontot mögé. A hivatkozott lista a következőképpen fog kinézni, ha az f csomópontot hozzáadjuk az a->b->c->d->e hivatkozási listához a c csomópont után:
Ezért ellenőrizzük, hogy a megadott csomópont jelen van-e a fenti diagramon. Ha jelen van, egy új f csomópont jön létre. Ezt követően a c csomópont következő mutatóját a vadonatúj f csomópontra mutatjuk. Az f csomópont következő mutatója most a d csomópontra mutat.
c. A linkelt lista utolsó eleme
A harmadik esetben egy új csomópont kerül a csatolt lista végére. Vegye figyelembe az alábbi linkelt listát: a->b->c->d->e, az f csomópont hozzáadásával a végén. A csomópont hozzáadása után a linkelt lista így fog megjelenni.
Ennek eredményeként létrehozunk egy új f csomópontot. A nullára vezető farokmutató ezután f-re, az f csomópont következő mutatója pedig nullára mutat. Az alábbi programozási nyelvben mindhárom típusú beszúrási függvényt generáltunk.
A linkelt lista deklarálható struktúraként vagy osztályként a C++ nyelven. A struktúraként deklarált linkelt lista klasszikus C-stílusú utasítás. A linkelt listát osztályként használják a modern C++-ban, főleg a szabványos sablonkönyvtár használatakor.
A következő alkalmazásban a struktúrát használtuk egy csatolt lista deklarálására és létrehozására. Tagjai adatok és a következő elemre mutató mutató lesznek.
C++ program:
#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) Törlés
Hasonlóan a beszúráshoz, egy csomópont törléséhez egy csatolt listáról sok olyan pontra van szükség, ahonnan a csomópont kikerülhet. A hivatkozott lista első, utolsó vagy k-adik csomópontját véletlenszerűen eltávolíthatjuk. Megfelelően frissítenünk kell a következő mutatót és az összes többi hivatkozott listamutatót, hogy a törlés után is megmaradjon a hivatkozott lista.
A következő C++ implementációban két törlési módszerünk van: a lista kezdeti csomópontjának törlése és a lista utolsó csomópontjának törlése. Kezdjük azzal, hogy csomópontokat adunk a lista fejéhez. A lista tartalma ezután minden egyes hozzáadás és törlés után megjelenik.
C++ program:
#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> Csomópontszám
A hivatkozott lista bejárása közben végrehajtható a csomópontok számának számlálása. Az előző megközelítésben azt láttuk, hogy ha egy csomópontot kell beszúrnunk/törölnünk, vagy meg kell jelenítenünk a hivatkozott lista tartalmát, akkor az elejétől kezdve végig kell járnunk a hivatkozott listán.
A számláló beállítása és a növelés, valamint az egyes csomópontok bejárása megadja a csomópontok számát a hivatkozott listában.
A tömb és a linkelt lista közötti különbségek:
| Sor | Linkelt lista |
|---|---|
| A tömbök meghatározott méretűek. | A linkelt lista mérete változó. |
| Új elem beillesztése nehézkes. | A beillesztés és törlés egyszerűbb. |
| A hozzáférés véletlenszerűen engedélyezett. | Véletlenszerű hozzáférés nem lehetséges. |
| Az elemek viszonylag közel vannak egymáshoz. | Az elemek nem egybefüggőek. |
| A következő mutatóhoz nincs szükség további helyiségre. | A következő mutató további memóriát igényel. |
Funkcionalitás
Mivel a csatolt listák és tömbök egyaránt lineáris adatstruktúrák, amelyek objektumokat tartalmaznak, az alkalmazások többségében hasonló módon használhatók.
Íme néhány példa a linkelt listás alkalmazásokra:
- A veremeket és a sorokat összekapcsolt listák segítségével lehet megvalósítani.
- Ha a gráfokat szomszédsági listákként kell kifejeznünk, akkor egy linkelt listát használhatunk azok megvalósításához.
- Használhatunk linkelt listát is matematikai polinomok tárolására.
- Kivonatolás esetén összekapcsolt listákat használnak a gyűjtők végrehajtására.
- Amikor egy program dinamikus memóriafoglalást igényel, használhatunk egy csatolt listát, mert a hivatkozott listák ebben az esetben hatékonyabbak.
Következtetés
A linkelt listák olyan adatstruktúrák, amelyek az adatelemek lineáris, de nem összefüggő formában történő tárolására szolgálnak. A linkelt lista két-két összetevőt tartalmazó csomópontokból áll. Az első komponens adatokból áll, míg a második felében egy mutató található, amely a lista következő tagjának memóriacímét tárolja.
hegyesszög
Annak jeleként, hogy a hivatkozott lista véget ért, a lista utolsó elemének következő mutatója NULL-ra van állítva. A fej az első elem a listán. A hivatkozott lista számos műveletet tesz lehetővé, például beszúrást, törlést, bejárást stb. A dinamikus memóriafoglaláshoz a linkelt listákat előnyben részesítik a tömbökkel szemben.
A linkelt listákat nehéz kinyomtatni vagy bejárni, mert nem tudjuk véletlenszerűen elérni az elemeket, mint a tömböket. A tömbökhöz képest a beillesztési-törlési eljárások olcsóbbak.
Ebben az oktatóanyagban mindent megtudtunk, amit a lineárisan összekapcsolt listákról tudni lehet. A linkelt listák lehetnek duplán összekapcsoltak vagy kör alakúak is. Következő oktatóanyagainkban részletesen végigmegyünk ezeken a listákon.