I stedet for å bruke array, kan vi også bruke koblet liste for å implementere stack. Koblet liste tildeler minnet dynamisk. Imidlertid er tidskompleksiteten i begge scenariene den samme for alle operasjonene, dvs. push, pop og kikk.

I lenket listeimplementering av stabel opprettholdes nodene ikke-sammenhengende i minnet. Hver node inneholder en peker til dens umiddelbare etterfølgernode i stabelen. Stack sies å bli overflyttet hvis plassen som er igjen i minnehaugen ikke er nok til å lage en node.

Den øverste noden i stabelen inneholder alltid null i adressefeltet. La oss diskutere måten hver operasjon utføres i koblet listeimplementering av stack.

Legge til en node i stabelen (Push-operasjon)

Å legge til en node i stabelen kalles trykk operasjon. Å skyve et element til en stabel i koblet listeimplementering er forskjellig fra en matriseimplementering. For å skyve et element på stabelen, er følgende trinn involvert.

1. Opprett en node først og alloker minne til den.
2. Hvis listen er tom, skal elementet skyves som startnoden til listen. Dette inkluderer å tilordne verdi til datadelen av noden og tilordne null til adressedelen av noden.
3. Hvis det allerede er noen noder i listen, må vi legge til det nye elementet i begynnelsen av listen (for ikke å krenke egenskapen til stabelen). For dette formålet, tilordne adressen til startelementet til adressefeltet til den nye noden og gjør den nye noden til startnoden på listen.

Tidskompleksitet: o(1)





C implementering:

 void push () { int val; struct node *ptr =(struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } 

Slette en node fra stabelen (POP-operasjon)

Å slette en node fra toppen av stabelen kalles pop operasjon. Å slette en node fra den koblede listeimplementeringen av stabelen er forskjellig fra den i arrayimplementeringen. For å hente et element fra stabelen, må vi følge følgende trinn:

Se etter underløpstilstanden:Underflyttilstanden oppstår når vi prøver å sprette fra en allerede tom stabel. Stabelen vil være tom hvis hodepekeren på listen peker på null.Juster hodepekeren tilsvarende:I stabelen blir elementene poppet bare fra den ene enden, derfor må verdien som er lagret i hodepekeren slettes og noden må frigjøres. Den neste noden til hodenoden blir nå hodenoden.

Tidskompleksitet: o(n)

C implementering

 void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } 

Vis nodene (Traversing)

Å vise alle nodene i en stabel må krysse alle nodene i den koblede listen organisert i form av stabel. For dette formålet må vi følge følgende trinn.

1. Kopier hodepekeren til en midlertidig peker.
2. Flytt den midlertidige pekeren gjennom alle nodene i listen og skriv ut verdifeltet som er knyttet til hver node.

Tidskompleksitet: o(n)

C Implementering

 void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } } 

Menydrevet program i C som implementerer alle stabeloperasjoner ved å bruke koblet liste:

 #include #include void push(); void pop(); void display(); struct node { int val; struct node *next; }; struct node *head; void main () { int choice=0; printf('
*********Stack operations using linked list*********
'); printf('
----------------------------------------------
'); while(choice != 4) { printf('

Chose one from the below options...
'); printf('
1.Push
2.Pop
3.Show
4.Exit'); printf('
 Enter your choice 
'); scanf('%d',&choice); switch(choice) { case 1: { push(); break; } case 2: { pop(); break; } case 3: { display(); break; } case 4: { printf('Exiting....'); break; } default: { printf('Please Enter valid choice '); } }; } } void push () { int val; struct node *ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('not able to push the element'); } else { printf('Enter the value'); scanf('%d',&val); if(head==NULL) { ptr->val = val; ptr -> next = NULL; head=ptr; } else { ptr->val = val; ptr->next = head; head=ptr; } printf('Item pushed'); } } void pop() { int item; struct node *ptr; if (head == NULL) { printf('Underflow'); } else { item = head->val; ptr = head; head = head->next; free(ptr); printf('Item popped'); } } void display() { int i; struct node *ptr; ptr=head; if(ptr == NULL) { printf('Stack is empty
'); } else { printf('Printing Stack elements 
'); while(ptr!=NULL) { printf('%d
',ptr->val); ptr = ptr->next; } } }