• Linkitetty lista voidaan määritellä kutsuttujen objektien kokoelmaksi solmut jotka tallentuvat satunnaisesti muistiin.
• Solmu sisältää kaksi kenttää eli kyseiseen osoitteeseen tallennetun datan ja osoittimen, joka sisältää seuraavan muistissa olevan solmun osoitteen.
• Listan viimeinen solmu sisältää osoittimen nollakohtaan.

Linkitetyn luettelon käyttötavat

• Listan ei tarvitse olla jatkuvasti läsnä muistissa. Solmu voi sijaita missä tahansa muistissa ja linkitetty yhteen luettelon muodostamiseksi. Tällä saavutetaan optimaalinen tilankäyttö.
• listan koko on rajoitettu muistin kokoon, eikä sitä tarvitse ilmoittaa etukäteen.
• Tyhjä solmu ei voi olla linkitetyssä luettelossa.
• Voimme tallentaa primitiivityyppien tai objektien arvot yksittäin linkitettyyn luetteloon.

Miksi käyttää linkitettyä listaa taulukon yli?

Tähän asti olemme käyttäneet taulukkotietorakennetta järjestämään elementtiryhmää, joka tallennetaan yksitellen muistiin. Arraylla on kuitenkin useita etuja ja haittoja, jotka on tiedettävä, jotta voidaan päättää koko ohjelmassa käytettävä tietorakenne.

Array sisältää seuraavat rajoitukset:

1. Taulukon koko on tiedettävä etukäteen ennen sen käyttöä ohjelmassa.
2. Matriisin koon kasvattaminen on aikaa vievä prosessi. On lähes mahdotonta laajentaa taulukon kokoa ajon aikana.
3. Kaikki taulukon elementit on tallennettava peräkkäin muistiin. Minkä tahansa elementin lisääminen taulukkoon vaatii kaikkien edeltäjiensä siirtämistä.

Linkitetty lista on tietorakenne, joka voi voittaa kaikki taulukon rajoitukset. Linkitetyn luettelon käyttäminen on hyödyllistä, koska

in.seuraava java

1. Se varaa muistin dynaamisesti. Kaikki linkitetyn listan solmut tallennetaan ei-peräkkäin muistiin ja linkitetään yhteen osoittimien avulla.
2. Mitoitus ei ole enää ongelma, koska meidän ei tarvitse määritellä sen kokoa ilmoitushetkellä. Lista kasvaa ohjelman tarpeen mukaan ja rajoitetaan käytettävissä olevaan muistitilaan.

Yksittäin linkitetty luettelo tai yksisuuntainen ketju

Yksittäin linkitetty lista voidaan määritellä kokoelmaksi järjestettyjä elementtejä. Elementtien määrä voi vaihdella ohjelman tarpeen mukaan. Yksittäin linkitetyn luettelon solmu koostuu kahdesta osasta: dataosasta ja linkkiosasta. Solmun dataosa tallentaa todellisen tiedon, jota solmun tulee edustaa, kun taas solmun linkkiosa tallentaa välittömän seuraajansa osoitteen.

Yksisuuntaisen ketjun tai yksitellen linkitetty luettelo voidaan kulkea vain yhteen suuntaan. Toisin sanoen voidaan sanoa, että jokainen solmu sisältää vain seuraavan osoittimen, joten emme voi kulkea listaa päinvastaiseen suuntaan.

Tarkastellaan esimerkkiä, jossa opiskelijan kolmessa aineessa saamat arvosanat on tallennettu linkitettyyn listaan ​​kuvan osoittamalla tavalla.

knn

Yllä olevassa kuvassa nuoli edustaa linkkejä. Jokaisen solmun dataosassa on opiskelijan eri aineesta saamat arvosanat. Listan viimeinen solmu tunnistetaan nollaosoittimella, joka on viimeisen solmun osoiteosassa. Meillä voi olla niin monta elementtiä kuin tarvitsemme luettelon dataosassa.

Monimutkaisuus

Toiminnot yksittäin linkitetyssä luettelossa

On olemassa useita toimintoja, jotka voidaan suorittaa yksittäin linkitetyllä luettelolla. Alla on luettelo kaikista tällaisista toiminnoista.

Solmun luominen

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

Lisäys

Lisäys yksittäin linkitettyyn luetteloon voidaan suorittaa eri kohdissa. Lisättävän uuden solmun sijainnin perusteella lisäys luokitellaan seuraaviin luokkiin.

git lisää kaikki

Poistaminen ja läpikulku

Solmun poistaminen erikseen linkitetystä luettelosta voidaan suorittaa eri paikoissa. Poistettavan solmun sijainnin perusteella toiminta luokitellaan seuraaviin luokkiin.

Linkitetty luettelo C:ssä: Menu Driven 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; } } } 

Lähtö:

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