刪除雙鏈表末尾節點

刪除雙向鏈表中的最後一個節點需要遍曆鏈表以便到達鏈表的最後一個節點，然後在該位置進行指針調整。

要刪除鏈表的最後一個節點，需要按照以下步驟操作。

• 如果鏈表已經為空，則條件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