在迴圈雙向鏈表末尾插入節點

在迴圈雙向鏈表的末尾插入節點有兩種情況。 鏈表為空或鏈表中包含多個元素。

使用以下語句為新節點ptr分配記憶體空間。

ptr = (struct node *)malloc(sizeof(struct node));

在第一種情況下，條件head == NULL變為true，因此該節點將被添加為鏈表中的第一個節點。 此新添加節點的下一個(next)和上一個(prev)指針將僅指向自身。 這可以通過使用以下語句來完成。

head = ptr;
ptr -> next = head;
ptr -> prev = head;

在第二種情況下，條件head == NULL變為false，因此節點將被添加為鏈表中的最後一個節點。 為此，需要在鏈表末尾進行一些指針調整。 因為，新節點將包含鏈表的第一個節點的地址，因此需要使最後一個節點的next指針指向鏈表的頭(head)節點。 類似地，(head)節點的prev指針也將指向鏈表的新的最後一個節點。

head -> prev = ptr;
ptr -> next = head;

現在，還需要使鏈表的最後一個節點的next指針指向鏈表的新的最後一個節點，類似地，新的最後一個節點也將指向temp的先前指針。 這將通過使用以下語句來完成。

temp->next = ptr;
ptr ->prev=temp;

這樣，新節點ptr已作為鏈表的最後一個節點插入。 該演算法及其C語言實現描述如下。

演算法

第1步：IF PTR = NULL
    提示 記憶體溢出

    轉到第12步

[IF結束]

第2步：設置NEW_NODE = PTR
第3步：SET PTR = PTR - > NEXT
第4步：設置NEW_NODE - > DATA = VAL
第5步：設置NEW_NODE - > NEXT = HEAD
第6步：設置TEMP = HEAD
第7步：在TEMP - > NEXT！= HEAD時重複第8步

第8步：SET TEMP = TEMP - > NEXT
[迴圈結束]

第9步：設置TEMP - > NEXT = NEW_NODE
第10步：設置NEW_NODE - > PREV = TEMP
第11步：SET HEAD - > PREV = NEW_NODE
第12步：退出

示意圖

C語言實現的示例代碼 -

#include<stdio.h>
#include<stdlib.h>
void insertion_last(int);
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
struct node *head;
void main()
{
    int choice, item;
    do
    {
        printf("Enter the item which you want to insert?\n");
        scanf("%d", &item);
        insertion_last(item);
        printf("Press 0 to insert more ?\n");
        scanf("%d", &choice);
    } while (choice == 0);
}
void insertion_last(int item)
{
    struct node *ptr = (struct node *) malloc(sizeof(struct node));
    struct node *temp;
    if (ptr == NULL)
    {
        printf("OVERFLOW");
    }else
    {
        ptr->data = item;
        if (head == NULL)
        {
            head = ptr;
            ptr->next = head;
            ptr->prev = head;
        }
        else
        {
            temp = head;
            while (temp->next != head)
            {
                temp = temp->next;
            }
            temp->next = ptr;
            ptr->prev = temp;
            head->prev = ptr;
            ptr->next = head;
        }
    }
    printf("Node Inserted\n");
}

執行上面示例代碼，得到以下結果 -

Enter the item which you want to insert?
123

Node Inserted

Press 0 to insert more ?
12