A saistītais saraksts ir lineāra dinamiska datu struktūra, ko izmantojam datu elementu glabāšanai. Masīvi ir arī lineāras datu struktūras veids, kurā datu vienumi tiek glabāti nepārtrauktos atmiņas blokos.

Atšķirībā no masīviem saistītajam sarakstam nav jāuzglabā datu elementi blakus esošajos atmiņas reģionos vai blokos.

A saistītais saraksts sastāv no elementiem, kas pazīstami kā “mezgli”, kas ir sadalīti divās daļās. Pirmais komponents ir daļa, kurā mēs glabājam faktiskos datus, un otrā ir daļa, kurā mēs saglabājam rādītāju uz nākamo mezglu. Šāda veida struktūra ir pazīstama kā ' atsevišķi saistītais saraksts .'

Saistītais saraksts programmā C++

Šajā apmācībā tiks padziļināti apskatīts atsevišķi saistītais saraksts.

pandu sērijas iezīmes

Atsevišķi saistītā saraksta struktūra ir parādīta zemāk esošajā diagrammā

• Kā mēs redzējām iepriekš minētajā daļā, pirmais saistītā saraksta mezgls ir pazīstams kā 'galva', bet pēdējais mezgls tiek saukts par 'asti'. Tas ir tāpēc, ka pēdējā mezglā nav norādīta atmiņas adrese, saistītā saraksta gala mezglam nākamajam rādītājam būs nulle.
• Tā kā katrā mezglā ir rādītājs uz nākamo mezglu, datu elementi saistītajā sarakstā nav jāsaglabā blakus esošās vietās. Mezgli var būt izkliedēti visā atmiņā. Tā kā katram mezglam ir aiz tā esošā adrese, mēs varam piekļūt mezgliem, kad vien vēlamies.
• Mēs varam ātri pievienot un noņemt datu vienumus no savienotā saraksta. Rezultātā saistītais saraksts var dinamiski palielināties vai sarukt. Saistītajā sarakstā nav maksimālā datu vienumu daudzuma, ko tas var saturēt. Rezultātā saistītajam sarakstam varam pievienot tik daudz datu vienumu, cik vēlamies, ja vien ir pieejama RAM.
• Tā kā mums nav iepriekš jānorāda, cik vienumu mums ir nepieciešams saistītajā sarakstā, saistītais saraksts ietaupa vietu atmiņā, turklāt to ir viegli ievietot un dzēst. Vienīgā vieta, ko izmanto saistītais saraksts, ir saglabāt rādītāju uz nākamo mezglu, kas palielina izmaksas.

Pēc tam mēs apskatīsim dažādas darbības, kuras var veikt saistītā sarakstā.

1) ievietošana

Saistītais saraksts tiek paplašināts, to papildinot. Lai gan tas varētu šķist vienkārši, ņemot vērā saistītā saraksta struktūru, mēs zinām, ka katru reizi, kad tiek pievienots datu vienums, mums ir jāmaina nākamā pievienotā vienuma iepriekšējā un nākamā mezgla norādes.

Otrais aspekts, par ko jādomā, ir vieta, kur tiks ievietots jaunais datu vienums.

Ir trīs vietas, kur saistītajam sarakstam var pievienot datu vienumu.

a. Sākot ar saistīto sarakstu

Zemāk ir savienots skaitļu 2->4->6->8->10 saraksts. Galva, kas norāda uz 2. mezglu, tagad norādīs uz 1. mezglu, un nākamajam mezgla 1 rādītājam būs 2. mezgla atmiņas adrese, kā parādīts attēlā zemāk, ja mēs pievienosim jaunu mezglu 1 kā pirmo mezglu sarakstā. .

Rezultātā jaunais saistītais saraksts ir 1->2->4->6->8->10.

b. Pēc dotā mezgla

Šajā gadījumā mums tiek piešķirts mezgls, un aiz tā ir jāpievieno jauns mezgls. Saistītais saraksts izskatīsies šādi, ja mezgls f tiek pievienots saistītajam sarakstam a->b->c->d->e aiz mezgla c:

Tāpēc mēs pārbaudām, vai norādītais mezgls ir redzams iepriekš redzamajā diagrammā. Ja tas ir, tiek izveidots jauns mezgls f. Pēc tam mēs novirzām mezgla c nākamo rādītāju uz pilnīgi jauno mezglu f. Mezgla f nākamais rādītājs tagad norāda uz mezglu d.

c. Saistītā saraksta pēdējais vienums

Trešajā gadījumā saistītā saraksta beigās tiek pievienots jauns mezgls. Ņemiet vērā zemāk esošo saistīto sarakstu: a->b->c->d->e, beigās pievienojot mezglu f. Pēc mezgla pievienošanas saistītais saraksts parādīsies šādi.

Rezultātā mēs izveidojam jaunu mezglu f. Pēc tam astes rādītājs, kas ved uz nulli, tiek norādīts uz f, un mezgla f nākamais rādītājs ir norādīts uz nulli. Tālāk esošajā programmēšanas valodā esam ģenerējuši visus trīs ievietošanas funkciju veidus.

Saistīto sarakstu var deklarēt kā struktūru vai klasi C++ valodā. Saistīts saraksts, kas deklarēts kā struktūra, ir klasisks C stila paziņojums. Saistīts saraksts tiek izmantots kā klase mūsdienu C++, galvenokārt, ja tiek izmantota standarta veidņu bibliotēka.

Struktūra tika izmantota šajā lietojumprogrammā, lai deklarētu un ģenerētu saistīto sarakstu. Tās dalībnieki būs dati un rādītājs uz šādu elementu.

C++ programma:

 #include using namespace std; struct Node { int data; struct Node *next; }; void push ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = nodeData; newNode1 -&gt; next = (*head); (*head) = newNode1; } void insertAfter ( struct Node* prevNode, int nodeData ) { if ( prevNode == NULL ) { cout <data = nodedata; newnode1 -> next = prevNode -&gt; next; prevNode -&gt; next = newNode1; } void append ( struct Node** head, int nodeData ) { struct Node* newNode1 = new Node; struct Node *last = *head; newNode1 -&gt; data = nodeData; newNode1 -&gt; next = NULL; if ( *head == NULL ) { *head = newNode1; return; } while ( last -&gt; next != NULL ) last = last -&gt; next; last -&gt; 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--&gt;25--&gt;55--&gt;15--&gt;45--&gt;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&apos;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&apos;s initial node and deleting the list&apos;s last node. We begin by adding nodes to the head of the list. The list&apos;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 -&gt; next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -&gt; next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -&gt; next -&gt; next != NULL ) secondLast = secondLast-&gt;next; delete ( secondLast -&gt; next ); secondLast -&gt; next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = newData; newNode1 -&gt; next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &amp;head, 25 ); push ( &amp;head, 45 ); push ( &amp;head, 65); push ( &amp;head, 85 ); push ( &amp;head, 95 ); Node* temp; cout &lt;&lt; &apos;Linked list created &apos; &lt; 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--&gt;85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting head node 85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting last node 85--&gt;65--&gt;45--&gt;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&apos;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) Dzēšana

Līdzīgi kā ievietošanai, lai dzēstu mezglu no saistītā saraksta, ir nepieciešami daudzi punkti, no kuriem mezglu var noņemt. Mēs varam nejauši noņemt saistītā saraksta pirmo, pēdējo vai k-to mezglu. Mums ir pareizi jāatjaunina nākamais rādītājs un visi pārējie saistīto sarakstu rādītāji, lai saglabātu saistīto sarakstu pēc dzēšanas.

Šajā C++ implementācijā mums ir divas dzēšanas metodes: saraksta sākotnējā mezgla dzēšana un saraksta pēdējā mezgla dzēšana. Mēs sākam, pievienojot mezglus saraksta sākumā. Pēc katra pievienošanas un dzēšanas tiek parādīts saraksta saturs.

C++ programma:

 #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 -&gt; next; delete tempNode; return head; } Node* removingLastNode ( struct Node* head ) { if ( head == NULL ) return NULL; if ( head -&gt; next == NULL ) { delete head; return NULL; } Node* secondLast = head; while ( secondLast -&gt; next -&gt; next != NULL ) secondLast = secondLast-&gt;next; delete ( secondLast -&gt; next ); secondLast -&gt; next = NULL; return head; } void push ( struct Node** head, int newData ) { struct Node* newNode1 = new Node; newNode1 -&gt; data = newData; newNode1 -&gt; next = ( *head ); ( *head ) = newNode1; } int main() { Node* head = NULL; push ( &amp;head, 25 ); push ( &amp;head, 45 ); push ( &amp;head, 65); push ( &amp;head, 85 ); push ( &amp;head, 95 ); Node* temp; cout &lt;&lt; &apos;Linked list created &apos; &lt; 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--&gt;85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting head node 85--&gt;65--&gt;45--&gt;25--&gt;NULL Linked list after deleting last node 85--&gt;65--&gt;45--&gt;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&apos;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>

Mezglu skaits

Pārvietojot saistīto sarakstu, var veikt mezglu skaitīšanas procesu. Iepriekšējā pieejā mēs redzējām, ka, ja mums bija jāievieto/izdzēš mezgls vai jāparāda saistītā saraksta saturs, mums bija jāšķērso saistītais saraksts no sākuma.

Skaitītāja iestatīšana un palielināšana, kā arī katra mezgla šķērsošana, mēs nodrošināsim mezglu skaitu saistītajā sarakstā.

Atšķirības starp masīvu un saistīto sarakstu:

Funkcionalitāte

Tā kā saistītie saraksti un masīvi ir lineāras datu struktūras, kurās ir objekti, tos var izmantot līdzīgā veidā lielākajā daļā lietojumprogrammu.

Tālāk ir sniegti daži saistīto sarakstu lietojumprogrammu piemēri.

• Krātuves un rindas var ieviest, izmantojot saistītos sarakstus.
• Ja mums ir jāizsaka grafiki kā blakus saraksti, mēs varam izmantot saistīto sarakstu, lai tos ieviestu.
• Mēs varam izmantot arī saistīto sarakstu, lai ietvertu matemātisko polinomu.
• Jaukšanas gadījumā segmentu ieviešanai tiek izmantoti saistīti saraksti.
• Ja programmai ir nepieciešama dinamiska atmiņas piešķiršana, mēs varam izmantot saistīto sarakstu, jo šajā gadījumā saistītie saraksti ir efektīvāki.

Secinājums

Saistītie saraksti ir datu struktūras, ko izmanto datu elementu glabāšanai lineārā, bet nesaistītā formā. Saistīto sarakstu veido mezgli ar diviem komponentiem katrā. Pirmo komponentu veido dati, bet otrajā pusē ir rādītājs, kas saglabā nākamā saraksta dalībnieka atmiņas adresi.

Kā zīme, ka saistītais saraksts ir beidzies, saraksta pēdējam vienumam nākamais rādītājs ir iestatīts uz NULL. Galva ir pirmais vienums sarakstā. Saistītais saraksts ļauj veikt dažādas darbības, piemēram, ievietošanu, dzēšanu, šķērsošanu un tā tālāk. Saistītie saraksti tiek doti priekšroka salīdzinājumā ar masīviem dinamiskai atmiņas piešķiršanai.

Saistītos sarakstus ir grūti izdrukāt vai šķērsot, jo mēs nevaram piekļūt elementiem nejauši kā masīviem. Salīdzinot ar masīviem, ievietošanas un dzēšanas procedūras ir lētākas.

Šajā apmācībā mēs uzzinājām visu, kas jāzina par lineāri saistītajiem sarakstiem. Saistītie saraksti var būt arī dubultsaiti vai apļveida. Mūsu gaidāmajās apmācībās mēs detalizēti izskatīsim šos sarakstus.