- Sammenkædet liste kan defineres som en samling af objekter kaldet noder der er tilfældigt gemt i hukommelsen.
- En knude indeholder to felter, dvs. data, der er lagret på den pågældende adresse, og den markør, som indeholder adressen på den næste knude i hukommelsen.
- Den sidste node på listen indeholder pointer til nul.
Brug af linket liste
- Listen er ikke forpligtet til at være sammenhængende til stede i hukommelsen. Noden kan ligge hvor som helst i hukommelsen og kædes sammen for at lave en liste. Herved opnås en optimeret udnyttelse af pladsen.
- listestørrelsen er begrænset til hukommelsesstørrelsen og skal ikke angives på forhånd.
- Tom node kan ikke være til stede på den sammenkædede liste.
- Vi kan gemme værdier af primitive typer eller objekter i den enkeltforbundne liste.
Hvorfor bruge linket liste over array?
Indtil nu brugte vi array-datastruktur til at organisere gruppen af elementer, der skal lagres individuelt i hukommelsen. Array har dog flere fordele og ulemper, som skal kendes for at bestemme den datastruktur, der skal bruges i hele programmet.
Array indeholder følgende begrænsninger:
- Størrelsen af array skal være kendt på forhånd, før du bruger det i programmet.
- At øge størrelsen af arrayet er en tidskrævende proces. Det er næsten umuligt at udvide størrelsen af arrayet under kørsel.
- Alle elementer i arrayet skal lagres sammenhængende i hukommelsen. Indsættelse af et hvilket som helst element i arrayet skal flyttes fra alle dets forgængere.
Sammenkædet liste er datastrukturen, som kan overvinde alle begrænsningerne i et array. Det er nyttigt at bruge linket liste, fordi
slf4j vs log4j
- Den allokerer hukommelsen dynamisk. Alle knudepunkterne på den linkede liste er ikke-sammenhængende lagret i hukommelsen og kædet sammen ved hjælp af pointere.
- Dimensionering er ikke længere et problem, da vi ikke behøver at definere størrelsen på deklarationstidspunktet. Listen vokser i henhold til programmets efterspørgsel og begrænset til den tilgængelige hukommelsesplads.
Enkeltforbundet liste eller envejskæde
Enkeltforbundet liste kan defineres som samlingen af ordnede sæt af elementer. Antallet af elementer kan variere alt efter programmets behov. En node i den enkeltforbundne liste består af to dele: datadel og linkdel. Datadelen af noden gemmer faktisk information, der skal repræsenteres af noden, mens linkdelen af noden gemmer adressen på dens umiddelbare efterfølger.
java ups koncepter
Envejskæde eller enkeltforbundet liste kan kun krydses i én retning. Med andre ord kan vi sige, at hver node kun indeholder næste pointer, derfor kan vi ikke krydse listen i den modsatte retning.
Overvej et eksempel, hvor de karakterer, eleven har opnået i tre fag, er gemt i en sammenkædet liste som vist på figuren.
I ovenstående figur repræsenterer pilen linkene. Datadelen af hver node indeholder karaktererne opnået af den studerende i det forskellige fag. Den sidste knude på listen er identificeret af nul-markøren, som er til stede i adressedelen af den sidste knude. Vi kan have lige så mange elementer, vi har brug for, i datadelen af listen.
Kompleksitet
| Datastruktur | Tidskompleksitet | Rummets fuldstændighed | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Gennemsnit | Værst | Værst | |||||||
| Adgang | Søg | Indskud | Sletning | Adgang | Søg | Indskud | Sletning | ||
| Enkeltforbundet liste | i) | i) | i(1) | i(1) | På) | På) | O(1) | O(1) | På) |
Operationer på enkeltforbundet liste
Der er forskellige operationer, som kan udføres på en enkelt linket liste. En liste over alle sådanne operationer er givet nedenfor.
sidste søgeord i java
Node oprettelse
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Indskud
Indsættelsen i en enkelt linket liste kan udføres på forskellige positioner. Baseret på positionen af den nye knude, der indsættes, er indsættelsen kategoriseret i følgende kategorier.
| SN | Operation | Beskrivelse |
|---|---|---|
| 1 | Indsættelse i begyndelsen | Det involverer at indsætte et hvilket som helst element foran på listen. Vi mangler blot et par linkjusteringer for at gøre den nye node til listens hoved. |
| 2 | Indsættelse i slutningen af listen | Det involverer indsættelse på den sidste af den linkede liste. Den nye node kan indsættes som den eneste node på listen, eller den kan indsættes som den sidste. Forskellige logikker er implementeret i hvert scenarie. |
| 3 | Indsættelse efter specificeret node | Det involverer indsættelse efter den angivne node på den sammenkædede liste. Vi skal springe det ønskede antal noder over for at nå noden, hvorefter den nye node vil blive indsat. . |
Sletning og gennemkørsel
Sletningen af en node fra en enkelt linket liste kan udføres på forskellige positioner. Baseret på positionen af den node, der slettes, er operationen kategoriseret i følgende kategorier.
| SN | Operation | Beskrivelse |
|---|---|---|
| 1 | Sletning i begyndelsen | Det involverer sletning af en node fra begyndelsen af listen. Dette er den enkleste operation blandt alle. Det skal bare have et par justeringer i nodepointerne. |
| 2 | Sletning i slutningen af listen | Det involverer at slette den sidste node på listen. Listen kan enten være tom eller fuld. Forskellig logik er implementeret for de forskellige scenarier. |
| 3 | Sletning efter specificeret node | Det involverer at slette noden efter den angivne node på listen. vi skal springe det ønskede antal noder over for at nå noden, hvorefter noden vil blive slettet. Dette kræver gennemgang af listen. |
| 4 | Traversering | Når vi krydser, besøger vi blot hver node på listen mindst én gang for at udføre en specifik operation på den, for eksempel at udskrive datadel af hver node, der er til stede på listen. |
| 5 | Søger | Ved søgning matcher vi hvert element på listen med det givne element. Hvis elementet findes på en af placeringerne, returneres placeringen af det element, ellers returneres null. . |
Linket liste i C: Menudrevet 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