在雙向連結串列開頭插入節點

在雙向連結串列中每個節點都包含兩個指標，因此與單連結串列相比，在雙連結串列中儲存有更多的指標。

將任何元素插入雙向連結串列有兩種情況。 連結串列為空或包含至少一個元素。 執行以下步驟以在雙向連結串列的開頭插入節點。

• 在記憶體中為新節點分配空間。這將通過使用以下語句來完成。

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

• 檢查連結串列是否為空。 如果條件head == NULL成立，則連結串列為空。 在這種情況下，節點將作為連結串列的唯一節點插入，因此節點的prev和next指標將指向NULL，並且頭指標將指向此節點。

  ptr->next = NULL;  
  ptr->prev=NULL;  
  ptr->data=item;  
  head=ptr;
  

• 在第二種情況下，條件head == NULL變為false，節點將在開頭插入。 節點的下一個指標將指向節點的現有頭指標。 現有head的prev指標將指向要插入的新節點。這將通過使用以下語句來完成。

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

因為，插入的節點是連結串列的第一個節點，因此它的prev指標指向NULL。 因此，為其前一部分指定null並使頭指向此節點。

ptr->prev = NULL;  
head = ptr;

演算法

第1步：IF ptr = NULL
   提示 「OVERFLOW」 資訊
  轉到第9步
  [結束]

第2步：設定 NEW_NODE = ptr
第3步：SET ptr = ptr - > NEXT
第4步：設定 NEW_NODE - > DATA = VAL
第5步：設定 NEW_NODE - > PREV = NULL
第6步：設定 NEW_NODE - > NEXT = START
第7步：SET head - > PREV = NEW_NODE
第8步：SET head = NEW_NODE
第9步：退出

示意圖

C語言實現範例 -

#include<stdio.h>  
#include<stdlib.h>  
void insertbeginning(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);
        insertbeginning(item);
        printf("Press 0 to insert more ?\n");
        scanf("%d", &choice);
    } while (choice == 0);
}
void insertbeginning(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;
        }
    }

}

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

Enter the item which you want to insert?
12

Press 0 to insert more ?
0

Enter the item which you want to insert?
23

Press 0 to insert more ?
2