• Koblet liste kan defineres som en samling av objekter som kalles noder som er tilfeldig lagret i minnet.
• En node inneholder to felt, dvs. data lagret på den spesielle adressen og pekeren som inneholder adressen til neste node i minnet.
• Den siste noden på listen inneholder pekeren til null.

Bruk av koblet liste

• Listen er ikke nødvendig å være sammenhengende tilstede i minnet. Noden kan ligge hvor som helst i minnet og kobles sammen for å lage en liste. Dette gir en optimal utnyttelse av plassen.
• listestørrelsen er begrenset til minnestørrelsen og trenger ikke deklareres på forhånd.
• Tom node kan ikke være til stede i den koblede listen.
• Vi kan lagre verdier av primitive typer eller objekter i den enkeltlenkede listen.

Hvorfor bruke koblet liste over array?

Til nå har vi brukt array-datastruktur for å organisere gruppen av elementer som skal lagres individuelt i minnet. Array har imidlertid flere fordeler og ulemper som må være kjent for å bestemme datastrukturen som skal brukes gjennom hele programmet.

Array inneholder følgende begrensninger:

1. Størrelsen på matrisen må være kjent på forhånd før du bruker den i programmet.
2. Å øke størrelsen på matrisen er en prosess som tar tid. Det er nesten umulig å utvide størrelsen på matrisen under kjøring.
3. Alle elementene i matrisen må lagres sammenhengende i minnet. Å sette inn et hvilket som helst element i matrisen må skiftes av alle forgjengerne.

Koblet liste er datastrukturen som kan overvinne alle begrensningene til en matrise. Å bruke koblet liste er nyttig fordi,

slf4j vs log4j

1. Den tildeler minnet dynamisk. Alle nodene til koblet liste er ikke-sammenhengende lagret i minnet og koblet sammen ved hjelp av pekere.
2. Dimensjonering er ikke lenger et problem siden vi ikke trenger å definere størrelsen på deklarasjonstidspunktet. Listen vokser i henhold til programmets etterspørsel og begrenset til tilgjengelig minneplass.

Enkeltkoblet liste eller enveis kjede

Enkeltlenket liste kan defineres som samlingen av ordnede sett med elementer. Antall elementer kan variere i henhold til programmets behov. En node i den enkeltlenkede listen består av to deler: datadel og linkdel. Datadelen av noden lagrer faktisk informasjon som skal representeres av noden mens linkdelen av noden lagrer adressen til dens umiddelbare etterfølger.

java oops konsepter

Enveis kjede eller enkeltlenket liste kan bare krysses i én retning. Med andre ord kan vi si at hver node bare inneholder neste peker, derfor kan vi ikke krysse listen i motsatt retning.

Tenk på et eksempel hvor karakterene som studenten har oppnådd i tre fag er lagret i en lenket liste som vist i figuren.

I figuren ovenfor representerer pilen koblingene. Datadelen av hver node inneholder karakterene som studenten har oppnådd i det forskjellige faget. Den siste noden i listen identifiseres av null-pekeren som er tilstede i adressedelen til den siste noden. Vi kan ha så mange elementer vi trenger, i datadelen av listen.

Kompleksitet

Operasjoner på enkeltlenket liste

Det er forskjellige operasjoner som kan utføres på en enkelt koblet liste. En liste over alle slike operasjoner er gitt nedenfor.

siste nøkkelord i java

Nodeoppretting

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

Innsetting

Innsetting i en enkeltlenket liste kan utføres på forskjellige posisjoner. Basert på posisjonen til den nye noden som settes inn, er innsettingen kategorisert i følgende kategorier.

Sletting og kryssing

Sletting av en node fra en enkeltlenket liste kan utføres på forskjellige posisjoner. Basert på plasseringen til noden som slettes, er operasjonen kategorisert i følgende kategorier.

Koblet liste i C: Menydrevet 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; } } } 

Produksjon:

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