- Länkad lista kan definieras som en samling av objekt som anropas knutpunkter som är slumpmässigt lagrade i minnet.
- En nod innehåller två fält, dvs data lagrad på den specifika adressen och pekaren som innehåller adressen till nästa nod i minnet.
- Den sista noden i listan innehåller pekare till noll.
Användning av länkad lista
- Listan behöver inte finnas kontinuerligt i minnet. Noden kan finnas var som helst i minnet och länkas samman för att skapa en lista. Detta ger ett optimerat utnyttjande av utrymmet.
- liststorleken är begränsad till minnesstorleken och behöver inte deklareras i förväg.
- Tom nod kan inte finnas i den länkade listan.
- Vi kan lagra värden av primitiva typer eller objekt i den enskilt länkade listan.
Varför använda länkad lista över array?
Hittills har vi använt arraydatastruktur för att organisera gruppen av element som ska lagras individuellt i minnet. Array har dock flera fördelar och nackdelar som måste vara kända för att kunna bestämma vilken datastruktur som ska användas genom hela programmet.
Array innehåller följande begränsningar:
- Storleken på arrayen måste vara känd i förväg innan den används i programmet.
- Att öka storleken på arrayen är en process som tar tid. Det är nästan omöjligt att utöka storleken på arrayen under körning.
- Alla element i arrayen måste lagras kontinuerligt i minnet. För att infoga ett element i arrayen måste alla dess föregångare ändras.
Länkad lista är datastrukturen som kan övervinna alla begränsningar i en array. Att använda länkad lista är användbart eftersom,
mvc i fjäderram
- Den allokerar minnet dynamiskt. Alla noder i den länkade listan är icke-kontinuerligt lagrade i minnet och länkade samman med hjälp av pekare.
- Dimensionering är inte längre ett problem eftersom vi inte behöver definiera dess storlek vid deklarationstillfället. Listan växer enligt programmets efterfrågan och begränsad till det tillgängliga minnesutrymmet.
Enkelt länkad lista eller envägskedja
Enkellänkad lista kan definieras som samlingen av ordnad uppsättning element. Antalet element kan variera beroende på programmets behov. En nod i den enkellänkade listan består av två delar: datadel och länkdel. Datadelen av noden lagrar aktuell information som ska representeras av noden medan länkdelen av noden lagrar adressen till dess omedelbara efterträdare.
bryta java
Envägskedja eller enkellänkad lista kan bara korsas i en riktning. Med andra ord kan vi säga att varje nod endast innehåller nästa pekare, därför kan vi inte gå igenom listan i motsatt riktning.
Titta på ett exempel där betygen som studenten fått i tre ämnen lagras i en länkad lista som visas i figuren.
I figuren ovan representerar pilen länkarna. Datadelen av varje nod innehåller de betyg som studenten erhållit i det olika ämnet. Den sista noden i listan identifieras av nollpekaren som finns i adressdelen av den sista noden. Vi kan ha så många element vi behöver i datadelen av listan.
Komplexitet
| Datastruktur | Tidskomplexitet | Utrymmets fullständighet | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Genomsnitt | Värst | Värst | |||||||
| Tillgång | Sök | Införande | Radering | Tillgång | Sök | Införande | Radering | ||
| Enkelt länkad lista | i) | i) | i(1) | i(1) | På) | På) | O(1) | O(1) | På) |
Operations on Single Linked List
Det finns olika operationer som kan utföras på en länkad lista. En lista över alla sådana operationer ges nedan.
Sree Ramanujan
Skapande av noder
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Införande
Infogningen i en enkellänkad lista kan utföras på olika platser. Baserat på positionen för den nya noden som infogas, kategoriseras infogningen i följande kategorier.
| SN | Drift | Beskrivning |
|---|---|---|
| 1 | Insättning i början | Det innebär att infoga valfritt element längst fram i listan. Vi behöver bara några länkjusteringar för att göra den nya noden till listans huvud. |
| 2 | Infogning i slutet av listan | Det innebär infogning vid den sista av den länkade listan. Den nya noden kan infogas som den enda noden i listan eller den kan infogas som den sista. Olika logiker implementeras i varje scenario. |
| 3 | Insättning efter angiven nod | Det involverar infogning efter den angivna noden i den länkade listan. Vi måste hoppa över önskat antal noder för att nå noden varefter den nya noden kommer att infogas. . |
Radering och genomflyttning
Borttagning av en nod från en enkellänkad lista kan utföras på olika positioner. Baserat på positionen för noden som tas bort, kategoriseras operationen i följande kategorier.
| SN | Drift | Beskrivning |
|---|---|---|
| 1 | Radering i början | Det innebär radering av en nod från början av listan. Detta är den enklaste operationen av alla. Det behöver bara några justeringar i nodpekarna. |
| 2 | Radering i slutet av listan | Det innebär att den sista noden i listan tas bort. Listan kan antingen vara tom eller full. Olika logik implementeras för de olika scenarierna. |
| 3 | Radering efter angiven nod | Det innebär att noden tas bort efter den angivna noden i listan. vi måste hoppa över önskat antal noder för att nå noden varefter noden kommer att raderas. Detta kräver att du går igenom listan. |
| 4 | Att korsa | När vi korsar besöker vi helt enkelt varje nod i listan minst en gång för att utföra någon specifik operation på den, till exempel att skriva ut datadel av varje nod som finns i listan. |
| 5 | Sökande | När vi söker matchar vi varje element i listan med det givna elementet. Om elementet hittas på någon av platserna returneras platsen för det elementet annars returneras null. . |
Länkad lista i C: Menydrivet program
#include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
Enter the location of the node after which you want to perform deletion
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } Produktion:
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9