TechCodeview

• Gekoppelde lijst kan worden gedefinieerd als een verzameling objecten die wordt genoemd knooppunten die willekeurig in het geheugen worden opgeslagen.
• Een knooppunt bevat twee velden, d.w.z. gegevens die op dat specifieke adres zijn opgeslagen en de aanwijzer die het adres van het volgende knooppunt in het geheugen bevat.
• Het laatste knooppunt van de lijst bevat een verwijzing naar de nul.

Gebruik van gekoppelde lijst

• De lijst hoeft niet aaneengesloten in het geheugen aanwezig te zijn. Het knooppunt kan zich overal in het geheugen bevinden en aan elkaar worden gekoppeld om een ​​lijst te maken. Hierdoor wordt een geoptimaliseerd ruimtegebruik bereikt.
• De lijstgrootte is beperkt tot de geheugengrootte en hoeft niet vooraf te worden aangegeven.
• Een leeg knooppunt mag niet aanwezig zijn in de gekoppelde lijst.
• We kunnen waarden van primitieve typen of objecten opslaan in de enkelvoudig gekoppelde lijst.

Waarom een ​​gekoppelde lijst gebruiken in plaats van een array?

Tot nu toe gebruikten we de array-datastructuur om de groep elementen te organiseren die afzonderlijk in het geheugen moesten worden opgeslagen. Array heeft echter verschillende voor- en nadelen die bekend moeten zijn om te kunnen beslissen over de datastructuur die in het hele programma zal worden gebruikt.

Array bevat de volgende beperkingen:

1. De grootte van de array moet vooraf bekend zijn voordat u deze in het programma kunt gebruiken.
2. Het vergroten van de omvang van de array is een tijdrovend proces. Het is bijna onmogelijk om de omvang van de array tijdens runtime uit te breiden.
3. Alle elementen in de array moeten aaneengesloten in het geheugen worden opgeslagen. Als u een element in de array invoegt, moeten al zijn voorgangers worden verschoven.

Gekoppelde lijst is de gegevensstructuur die alle beperkingen van een array kan overwinnen. Het gebruik van een gekoppelde lijst is nuttig omdat:

Junit-testgevallen

1. Het wijst het geheugen dynamisch toe. Alle knooppunten van de gekoppelde lijst worden niet aaneengesloten in het geheugen opgeslagen en met elkaar verbonden met behulp van pointers.
2. De maatvoering is niet langer een probleem, omdat we de omvang ervan niet hoeven te definiëren op het moment van de aangifte. De lijst groeit afhankelijk van de vraag van het programma en is beperkt tot de beschikbare geheugenruimte.

Enkelvoudig gekoppelde lijst of eenrichtingsketen

Een enkelvoudig gekoppelde lijst kan worden gedefinieerd als de verzameling geordende reeks elementen. Het aantal elementen kan variëren afhankelijk van de behoefte van het programma. Een knooppunt in de enkelvoudig gekoppelde lijst bestaat uit twee delen: het datadeel en het linkdeel. Het gegevensgedeelte van het knooppunt slaat feitelijke informatie op die door het knooppunt moet worden weergegeven, terwijl het verbindingsgedeelte van het knooppunt het adres van zijn onmiddellijke opvolger opslaat.

Eenrichtingsketen of een enkelvoudig gekoppelde lijst kan slechts in één richting worden doorlopen. Met andere woorden, we kunnen zeggen dat elk knooppunt alleen de volgende aanwijzer bevat, en daarom kunnen we de lijst niet in de omgekeerde richting doorlopen.

is gelijk aan methode Java

Beschouw een voorbeeld waarbij de cijfers die de student voor drie vakken heeft behaald, worden opgeslagen in een gekoppelde lijst, zoals weergegeven in de afbeelding.

In de bovenstaande afbeelding vertegenwoordigt de pijl de koppelingen. Het datagedeelte van elk knooppunt bevat de cijfers die de student voor het betreffende onderwerp heeft behaald. Het laatste knooppunt in de lijst wordt geïdentificeerd door de nulaanwijzer die aanwezig is in het adresgedeelte van het laatste knooppunt. We kunnen zoveel elementen bevatten als we nodig hebben in het gegevensgedeelte van de lijst.

Java-sorteerreeksen

Complexiteit

Bewerkingen op een enkelvoudig gekoppelde lijst

Er zijn verschillende bewerkingen die kunnen worden uitgevoerd op een afzonderlijk gekoppelde lijst. Hieronder vindt u een lijst met al dergelijke bewerkingen.

Knooppunt creatie

 struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); 

Plaatsing

Het invoegen in een enkelvoudig gekoppelde lijst kan op verschillende posities worden uitgevoerd. Op basis van de positie van het nieuwe knooppunt dat wordt ingevoegd, wordt de invoeging in de volgende categorieën onderverdeeld.

Verwijderen en doorlopen

Het verwijderen van een knooppunt uit een enkelvoudig gekoppelde lijst kan op verschillende posities worden uitgevoerd. Op basis van de positie van het knooppunt dat wordt verwijderd, wordt de bewerking in de volgende categorieën onderverdeeld.

Gekoppelde lijst in C: menugestuurd programma

 #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; } } } 

Uitgang:

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