刪除雙連結串列末尾節點

刪除雙向連結串列中的最後一個節點需要遍歷連結串列以便到達連結串列的最後一個節點，然後在該位置進行指標調整。

要刪除連結串列的最後一個節點，需要按照以下步驟操作。

• 如果連結串列已經為空，則條件head == NULL將變為true，因此無法繼續操作。
• 如果連結串列中只有一個節點，則條件head->next == NULL變為true。 在這種情況下，只需要將連結串列的頭部分配為NULL並釋放頭部，以便完全刪除列表。
• 否則，只需遍歷連結串列即可到達連結串列的最後一個節點。這將通過使用以下語句來完成。

  ptr = head;   
  if(ptr->next != NULL)  
  {  
    ptr = ptr -> next;   
  }
  

• ptr將指向for迴圈結束時連結串列的最後一個節點。 只需將ptr的上一個節點的next指標設為NULL即可。

  ptr -> prev -> next = NULL;
  

將要刪除的節點的指標釋放。

free(ptr);

演算法步驟

第1步：IF HEAD = NULL
  提示：記憶體溢位
  轉到第7步
[IF結束]

第2步：設定TEMP = HEAD
第3步：重複第4步，TEMP-> NEXT！= NULL
第4步：設定TEMP = TEMP-> NEXT
[迴圈結束]

第5步：SET TEMP - > PREV-> NEXT = NULL
第6步：釋放TEMP
第7步：退出

示意圖

C語言實現的範例程式碼 -

#include<stdio.h>  
#include<stdlib.h>  
void create(int);
void last_delete();
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
struct node *head;
void main()
{
    int choice, item;
    do
    {
        printf("1.Append List\n");
        printf("2.Delete node from end\n");
        printf("3.Exit\n");
        printf("4.Enter your choice ? ");
        scanf("%d", &choice);
        switch (choice)
        {
        case 1:
            printf("Enter the item\n");
            scanf("%d", &item);
            create(item);
            break;
        case 2:
            last_delete();
            break;
        case 3:
            exit(0);
            break;
        default:
            printf("Please enter valid choice\n");
        }

    } while (choice != 3);
}
void create(int item)
{
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    if (ptr == NULL)
    {
        printf("OVERFLOW\n");
    }
    else
    {
        if (head == NULL)
        {
            ptr->next = NULL;
            ptr->prev = NULL;
            ptr->data = item;
            head = ptr;
        }
        else
        {
            ptr->data = item;
            ptr->prev = NULL;
            ptr->next = head;
            head->prev = ptr;
            head = ptr;
        }
        printf("Node Inserted\n");
    }

}
void last_delete()
{
    struct node *ptr;
    if (head == NULL)
    {
        printf("UNDERFLOW\n");
    }
    else if (head->next == NULL)
    {
        head = NULL;
        free(head);
        printf("Node Deleted\n");
    }
    else
    {
        ptr = head;
        if (ptr->next != NULL)
        {
            ptr = ptr->next;
        }
        ptr->prev->next = NULL;
        free(ptr);
        printf("Node Deleted\n");
    }
}

執行上面範例程式碼，得到以下結果 -

1.Append List
2.Delete node from end
3.Exit
4.Enter your choice?1

Enter the item
12

Node Inserted
1.Append List
2.Delete node from end
3.Exit
4.Enter your choice?1

Enter the item
90

Node Inserted
1.Append List
2.Delete node from end
3.Exit
4.Enter your choice?2

Node Deleted