A länkad lista är en slags linjär dynamisk datastruktur som vi använder för att lagra dataelement. Arrayer är också en typ av linjär datastruktur där dataposterna lagras i kontinuerliga minnesblock.

Till skillnad från arrayer behöver den länkade listan inte lagra dataelement i angränsande minnesregioner eller -block.

ersätt allt java

A länkad lista består av element som kallas 'noder' som är uppdelade i två delar. Den första komponenten är den del där vi lagrar själva data, och den andra är en del där vi lagrar pekaren till nästa nod. Denna typ av struktur är känd som en enbart länkad lista .'

Länkad lista i C++

Denna handledning kommer att gå igenom listan med en länk på djupet.

En enskild länkad listas struktur illustreras i diagrammet nedan

• Som vi har sett i ovanstående del är den första noden i den länkade listan känd som 'huvudet', medan den sista noden kallas 'svansen'. Det är för att ingen minnesadress är specificerad i den sista noden, den sista noden i den länkade listan kommer att ha en noll nästa pekare.
• Eftersom varje nod inkluderar en pekare till nästa nod, behöver dataelement i den länkade listan inte behållas på sammanhängande platser. Noderna kan vara spridda i minnet. Eftersom varje nod har adressen till den efter sig, kan vi komma åt noderna när vi vill.
• Vi kan snabbt lägga till och ta bort dataobjekt från den anslutna listan. Som ett resultat kan den länkade listan öka eller dra ihop sig dynamiskt. Den länkade listan har ingen maximal mängd dataobjekt den kan innehålla. Som ett resultat kan vi lägga till så många dataobjekt som vi vill till den länkade listan så länge det finns RAM tillgängligt.
• Eftersom vi inte behöver specificera hur många objekt vi behöver i den länkade listan i förväg, sparar den länkade listan minnesutrymme förutom att den är enkel att infoga och radera. Det enda utrymmet som används av en länkad lista är att lagra pekaren till nästa nod, vilket medför en viss kostnad.

Efter det kommer vi att gå igenom de olika operationerna som kan utföras på en länkad lista.

1) Insättning

Den länkade listan utökas genom att lägga till den. Även om det verkar enkelt, med tanke på den länkade listans struktur, vet vi att varje gång ett dataobjekt läggs till måste vi ändra nästa pekare för föregående och nästa noder för det nya objektet som vi har lagt till.

Var den nya dataposten kommer att infogas är den andra aspekten att tänka på.

Det finns tre platser där en datapost kan läggas till den länkade listan.

powershell admin

a. Börjar med den länkade listan

Nedan finns en sammankopplad lista med siffrorna 2->4->6->8->10. Huvudet som pekar mot nod 2 kommer nu att peka på nod 1, och nästa pekare för nod 1 kommer att ha minnesadressen för nod 2, som visas i illustrationen nedan, om vi lägger till en ny nod 1 som första nod i listan .

Som ett resultat är den nya länkade listan 1->2->4->6->8->10.

b. Efter den givna noden

I det här fallet får vi en nod och måste lägga till en ny nod bakom den. Den länkade listan kommer att se ut som följer om nod f läggs till i den länkade listan a->b->c->d->e efter nod c:

Vi kontrollerar därför om den angivna noden finns i diagrammet ovan. Om den finns skapas en ny nod f. Därefter pekar vi nod c:s nästa pekare mot den helt nya noden f. Noden fs nästa pekare pekar nu på nod d.

c. Den länkade listans sista post

I det tredje fallet läggs en ny nod till i slutet av den länkade listan. Ta hänsyn till den länkade listan nedan: a->b->c->d->e, med tillägg av nod f i slutet. När du har lagt till noden kommer den länkade listan att visas så här.

Som ett resultat konstruerar vi en ny nod f. Svanspekaren som leder till noll pekas sedan mot f, och nod fs nästa pekare pekas mot noll. I programmeringsspråket nedan har vi genererat alla tre typerna av infogningsfunktioner.

En länkad lista kan deklareras som en struktur eller som en klass i C++. En länkad lista som deklareras som en struktur är ett klassiskt uttalande i C-stil. En länkad lista används som en klass i modern C++, främst när man använder standardmallbiblioteket.

typer av mjukvarutestning

Struktur användes i följande applikation för att deklarera och generera en länkad lista. Dess medlemmar kommer att vara data och en pekare till följande element.

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 -&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) Radering

I likhet med infogning kräver radering av en nod från en länkad lista många punkter från vilka noden kan elimineras. Vi kan ta bort den länkade listans första, sista eller k:te nod slumpmässigt. Vi måste uppdatera nästa pekare och alla andra länkade listpekare korrekt för att behålla den länkade listan efter raderingen.

I följande C++-implementering har vi två raderingsmetoder: ta bort listans initiala nod och ta bort listans sista nod. Vi börjar med att lägga till noder till listans huvud. Listans innehåll visas sedan efter varje tillägg och radering.

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 -&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>

Nodräkning

När du går igenom den länkade listan kan processen att räkna antalet noder utföras. I det föregående tillvägagångssättet såg vi att om vi behövde infoga/ta bort en nod eller visa innehållet i den länkade listan, var vi tvungna att gå igenom den länkade listan från början.

Att ställa in en räknare och öka så väl som vi korsar varje nod kommer att ge oss antalet noder i den länkade listan.

Skillnader mellan array och länkad lista:

Funktionalitet

Eftersom länkade listor och arrayer båda är linjära datastrukturer som innehåller objekt, kan de användas på liknande sätt för de flesta applikationer.

Följande är några exempel på länkade listapplikationer:

hur man skapar en array i java

• Stackar och köer kan implementeras med hjälp av länkade listor.
• När vi behöver uttrycka grafer som närliggande listor kan vi använda en länkad lista för att implementera dem.
• Vi kan också använda en länkad lista för att innehålla ett matematiskt polynom.
• Vid hashning används länkade listor för att implementera hinkarna.
• När ett program kräver dynamisk minnesallokering kan vi använda en länkad lista eftersom länkade listor är mer effektiva i det här fallet.

Slutsats

Länkade listor är datastrukturer som används för att hålla dataelement i en linjär men icke sammanhängande form. En länkad lista består av noder med två komponenter vardera. Den första komponenten består av data, medan den andra halvan har en pekare som lagrar minnesadressen för följande medlem i listan.

Som ett tecken på att den länkade listan har avslutats har det sista objektet i listan sin nästa pekare satt till NULL. Huvudet är det första objektet på listan. Den länkade listan tillåter en mängd olika åtgärder såsom infogning, radering, korsning och så vidare. Länkade listor gynnas framför arrayer för dynamisk minnesallokering.

Länkade listor är svåra att skriva ut eller gå igenom eftersom vi inte kan komma åt elementen slumpmässigt som arrayer. Jämfört med arrayer är procedurer för insättning och radering billigare.

I den här handledningen lärde vi oss allt som finns att veta om linjärt länkade listor. Länkade listor kan också vara dubbellänkade eller cirkulära. I våra kommande handledningar kommer vi att gå igenom dessa listor i detalj.