Meny

Länkad listdatastruktur i C ++ med illustration

  • Huvud
  • Övrig
  • Länkad listdatastruktur i C ++ med illustration

linked list data structure c with illustration

Prova Vårt Instrument För Att Eliminera Problem

En detaljerad studie av länkad lista i C ++.

En länkad lista är en linjär dynamisk datastruktur för att lagra dataobjekt. Vi har redan sett arrayer i våra tidigare ämnen om grundläggande C ++. Vi vet också att matriser är en linjär datastruktur som lagrar dataobjekt i angränsande platser.

Till skillnad från matriser lagras inte den länkade listan dataobjekt i angränsande minnesplatser.

En länkad lista består av objekt som kallas 'Noder' som innehåller två delar. Den första delen lagrar faktiska data och den andra delen har en pekare som pekar på nästa nod. Denna struktur kallas vanligtvis ”Singly linked list”.

=> Kolla in de bästa C ++ träningsövningarna här.

LÄNKAD LISTA

Vad du kommer att lära dig:

Länkad lista i C ++

Vi tar en titt på den enskilt länkade listan i detalj i denna handledning.

Följande diagram visar strukturen för en enstaka länkad lista.

struktur för en enstaka länkad lista

Som visas ovan kallas den första noden i den länkade listan 'huvud' medan den sista noden kallas 'Tail'. Som vi ser kommer den sista noden i den länkade listan att ha sin nästa pekare som noll eftersom den inte kommer att ha någon minnesadress pekad på.

Eftersom varje nod har en pekare till nästa nod behöver dataobjekt i den länkade listan inte lagras på angränsande platser. Noderna kan spridas i minnet. Vi kan komma åt noder när som helst eftersom varje nod kommer att ha en adress till nästa nod.

bästa verktyget för borttagning av skadlig programvara för Windows 10

Vi kan lägga till dataobjekt i den länkade listan samt ta bort objekt från listan enkelt. Det är således möjligt att växa eller krympa den länkade listan dynamiskt. Det finns ingen övre gräns för hur många dataobjekt som kan finnas där i den länkade listan. Så länge som minne är tillgängligt kan vi lägga till så många dataobjekt i den länkade listan.

Förutom enkel insättning och radering slösar inte den länkade listan också minnesutrymme eftersom vi inte behöver ange i förväg hur många objekt vi behöver i den länkade listan. Det enda utrymmet som tas av den länkade listan är för att lagra pekaren till nästa nod som lägger till lite overhead.

Därefter kommer vi att diskutera de olika operationerna som kan utföras på en länkad lista.

Operationer

Precis som de andra datastrukturerna kan vi också utföra olika operationer för den länkade listan. Men till skillnad från matriser, där vi kan komma åt elementet med hjälp av prenumeration direkt även om det finns någonstans däremellan, kan vi inte göra samma slumpmässiga åtkomst med en länkad lista.

För att komma åt vilken nod som helst måste vi gå igenom den länkade listan från början och först då kan vi komma åt önskad nod. Därför visar det sig vara dyrt att få tillgång till data slumpmässigt från den länkade listan.

Vi kan utföra olika operationer på en länkad lista enligt nedan:

# 1) Insättning

Insättning av länkad lista lägger till ett objekt i den länkade listan. Även om det kan låta enkelt, med tanke på strukturen för den länkade listan, vet vi att när ett dataobjekt läggs till i den länkade listan, måste vi ändra nästa pekare i föregående och nästa noder för det nya objektet som vi har lagt in.

Det andra som vi måste tänka på är den plats där det nya dataobjektet ska läggas till.

Det finns tre positioner i den länkade listan där ett dataobjekt kan läggas till.

# 1) I början av den länkade listan

En länkad lista visas nedan 2-> 4-> 6-> 8-> 10. Om vi ​​vill lägga till en ny nod 1, som den första noden i listan, kommer huvudet som pekar på nod 2 nu att peka på 1 och nästa pekare på nod 1 kommer att ha en minnesadress för nod 2 som visas nedan figur.

Insättning i början

Således blir den nya länkade listan 1-> 2-> 4-> 6-> 8-> 10.

# 2) Efter den givna noden

Här ges en nod och vi måste lägga till en ny nod efter den angivna noden. I listan nedan länkad a-> b-> c-> d -> e, om vi vill lägga till en nod f efter nod c kommer den länkade listan att se ut så här:

Insättning efter en given nod

Således kontrollerar vi i ovanstående diagram om den angivna noden är närvarande. Om den är närvarande skapar vi en ny nod f. Sedan pekar vi nästa pekare på nod c för att peka på den nya noden f. Nästa pekare på noden f pekar nu på nod d.

# 3) I slutet av den länkade listan

I det tredje fallet lägger vi till en ny nod i slutet av den länkade listan. Tänk på att vi har samma länkade lista a-> b-> c-> d-> e och vi måste lägga till en nod f i slutet av listan. Den länkade listan ser ut som visas nedan efter att ha lagt till noden.

Insättning i slutet av den länkade listan

Således skapar vi en ny nod f. Därefter pekas svanspekaren som pekar mot noll mot f och nästa pekare av nod f pekas mot noll. Vi har implementerat alla tre typer av infogningsfunktioner i nedanstående C ++ - program.

I C ++ kan vi förklara en länkad lista som en struktur eller som en klass. Att deklarera länkad lista som en struktur är en traditionell C-stildeklaration. En länkad lista som klass används i modern C ++, mestadels när man använder standardmallbiblioteket.

I följande program har vi använt struktur för att deklarera och skapa en länkad lista. Det kommer att ha data och peka på nästa element som sina medlemmar.

hur man tar bort ett objekt från en array-Java
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout

Produktion:

Slutlig länkad lista:

30–> 20–> 50–> 10–> 40–> null

Därefter implementerar vi den länkade listinsättningsoperationen i Java. På Java-språk implementeras den länkade listan som en klass. Programmet nedan liknar C ++ - programmet logiskt, den enda skillnaden är att vi använder en klass för den länkade listan.

class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String() args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println(' Final linked list: '); lList. displayList (); } }

Produktion:

Slutlig länkad lista:

10–> 20–> 30–> 40–> 50–> null

I både programmet ovan, C ++ såväl som Java, har vi separata funktioner för att lägga till en nod framför listan, slutet av listan och mellan listorna i en nod. I slutändan skriver vi ut innehållet i listan som skapats med alla de tre metoderna.

# 2) Radering

Precis som införandet innebär att radera en nod från en länkad lista också olika positioner där noden kan raderas. Vi kan ta bort den första noden, den sista noden eller en slumpmässig kth-nod från den länkade listan. Efter radering måste vi justera nästa pekare och andra pekare i den länkade listan på lämpligt sätt för att hålla den länkade listan intakt.

I följande C ++ -implementering har vi gett två raderingsmetoder, dvs. att ta bort den första noden i listan och ta bort den sista noden i listan. Vi skapar först en lista genom att lägga till noder i huvudet. Sedan visar vi innehållet i listan efter infogning och varje radering.

#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created '

Produktion:

Länkad lista skapad

10–> 8–> 6–> 4–> 2–
> NULL

Länkad lista efter borttagning av huvudnod

8–> 6–> 4–> 2–
> NULL

Länkad lista efter raderad sista nod

8–> 6–> 4–> NULL

Nästa är Java-implementeringen för att radera noder från den länkade listan. Implementeringslogiken är densamma som används i C ++ - programmet. Den enda skillnaden är att den länkade listan deklareras som en klass.

class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args()) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }

Produktion:

Länkad lista skapad:

9–> 7–> 5–> 3–> 1–
> null

Länkad lista efter radering av huvudnod:

7–> 5–> 3–> 1–
> null

vad är det bästa gratisregistret

Länkad lista efter radering av sista nod:

7–> 5–> 3–> null

Räkna antalet noder

Åtgärden för att räkna antalet noder kan utföras medan du går igenom den länkade listan. Vi har redan sett i implementeringen ovan att när vi behöver infoga / ta bort en nod eller visa innehåll i den länkade listan, måste vi gå igenom den länkade listan från början.

Att hålla en räknare och öka den när vi korsar varje nod ger oss räkningen av antalet noder som finns i den länkade listan. Vi lämnar det här programmet för läsarna att implementera.

Arrayer och länkade listor

Efter att ha sett operationerna och implementeringen av den länkade listan, låt oss jämföra hur arrays och länkad lista är rättvisa i jämförelse med varandra.

ArrayerLänkade listor
Arrayer har fast storlekLänkad liststorlek är dynamisk
Införande av nytt element är dyrtInsättning / radering är lättare
Slumpmässig åtkomst är tillåtenSlumpmässig åtkomst är inte möjlig
Elementen ligger angränsandeElement har inte sammanhängande plats
Inget extra utrymme krävs för nästa pekareExtra minne krävs för nästa pekare

Applikationer

Eftersom matriser och länkade listor båda används för att lagra objekt och är linjära datastrukturer kan båda dessa strukturer användas på liknande sätt för de flesta applikationer.

Några av ansökningarna för länkade listor är som följer:

  • En länkad lista kan användas för att implementera stackar och köer.
  • En länkad lista kan också användas för att implementera grafer när vi måste representera grafer som angränsande listor.
  • En matematisk polynom kan lagras som en länkad lista.
  • När det gäller hashteknik implementeras skoporna som används i hashing med hjälp av de länkade listorna.
  • När ett program kräver dynamisk tilldelning av minne kan vi använda en länkad lista eftersom länkade listor fungerar mer effektivt i det här fallet.

Slutsats

Länkade listor är datastrukturerna som används för att lagra dataobjekt på ett linjärt sätt men inte sammanhängande platser. En länkad lista är en samling noder som innehåller en datadel och en nästa pekare som innehåller minnesadressen för nästa element i listan.

Det sista elementet i listan har sin nästa pekare inställd på NULL, vilket visar slutet på listan. Det första elementet i listan kallas huvudet. Den länkade listan stöder olika operationer som insättning, radering, traversal, etc. Vid dynamisk minnesallokering är länkade listor att föredra framför matriser.

Länkade listor är dyra när det gäller deras genomgång eftersom vi inte slumpmässigt kan komma åt elementen som arrays. Insättnings-borttagningsoperationer är dock billigare jämfört med matriser.

Vi har lärt oss allt om linjära länkade listor i denna handledning. Länkade listor kan också vara cirkulära eller dubbelt. Vi kommer att ta en djupgående titt på dessa listor i våra kommande handledning.

=> Kontrollera här för fullständig C ++ träningsserie.

Rekommenderad läsning

^