在迴圈雙向連結串列末尾插入節點

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

使用以下語句為新節點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