Deletion of Last Node in Linked List

Deletion of Last Node in Linked List – जब हमें किसी Linked List के अन्तिम Node को Delete करना होता है तब सबसे पहले हमें Traversing करके Linked List के कुल Nodes की संख्‍या n ज्ञात करनी पडती है ताकि हमें पता चल सके के Linked List में कुल Nodes की संख्‍या कितनी है।

जब हमें Traversing करके कुल Nodes की संख्‍या n पता चल जाती है उसके बाद हमें वापस से एक Loop को n-1 बार चलाना होता है ताकि हम अन्तिम Node से पिछली वाली Node तक पहुंच सकें। फिर हमें इस Node के LINK Part में NULL Assign करना होता है।

जैसे ही हम Second Last Node के LINK Part में NULL Assign करते हैं, Linked List का अन्तिम Node Free हो जाता है। अब इस Free Node के Space को AVAILABLESPACE Linked List को प्रदान करना होता है। इस पूरी प्रक्रिया का Algorithm हम निम्नानुसार लिख सकते हैं-

[code]
Last Node Deletion Algorithm
DELETE_LAST_NODE(LIST, INFO, LINK, START, AVAILABLESPACE, COUNTNODE)
SET PREPTR = START [ Initialize Address of START to PREPTR ]
SET PTR = START[LINK]
SET COUNTNODE = 0 [ Set Counter to 0 ]
IF PREPTR = NULL then
    PRINT “Underflow, LIST is Empty” and RETURN
    REPEAT WHILE PREPTR <> NULL [Traverse LIST until PREPTR <> NULL]
        PTR = PTR[LINK]
        PREPTR = PREPTR[LINK]
        COUNTNODE = COUNTNODE + 1
    SET PREPTR = START [ Initialize Address of START to PTR Again ]
    SET PTR = START[LINK]
    REPEAT FOR I = COUNTNODE To 1 STEP SIZE I = I - 1
    PREPTR = PREPTR[LINK]
    PTR = PTR[LINK]
    IF COUNTNODE = 1
        PREPTR[LINK] = PTR[LINK]
AVAILABLESPACE[LINK] = PTR[LINK]
EXIT
[/code]

इस Algorithm के आधार पर हम निम्नानुसार एक Function Create करके किसी Linked List के अन्तिम Node को Delete कर सकते हैं।

[code]
Last Node Deletion Function 
void DeleteLastNode(struct LIST **START)
{
      int COUNTNODE = 0;
      struct LIST *PTR, *PREPTR;
      PREPTR = *START;
      PTR = PREPTR->LINK;
      if(PREPTR==NULL)
      {
            printf("\nUnderflow, LIST is Empty");
            return;
      }
      while(PTR)
      {
        PTR = PTR->LINK;
        PREPTR = PREPTR->LINK;
        COUNTNODE = COUNTNODE + 1;
      }

        printf("\nTotal Nodes are %d ", COUNTNODE);
        PREPTR = *START;
        PTR = PREPTR->LINK;
        while(COUNTNODE != 1)
        {
                PTR = PTR->LINK;
                PREPTR = PREPTR->LINK;
                COUNTNODE = COUNTNODE - 1 ;
        }
        if(COUNTNODE == 1)
        {
                PREPTR->LINK = PTR->LINK;
                free(PTR);
        }

   PREPTR = *START;
   PTR = PREPTR->LINK;
   printf("\nAfter Deleting Node, LIST is as Follows \n");
   while(PTR)
   {
        printf("\n0x%x", PTR);
      printf("%d", PTR->INFO);
      PTR = PTR->LINK;
   }
}
[/code]