link list-double link list的刪除某值

typedef struct Dnode {
   struct Dnode *prev;
   int val;
   struct Dnode *next;
}Dnode;

Dnode *Dhead = NULL;

// show doule linked list elements
void Dshow_list(void)
{
   Dnode *rush = Dhead;
   printf("\n The result is:\n");
   while (rush != NULL) {
      printf("%d ", rush->val);
      rush = rush->next;
   }
   puts("");
}

// delete a specified value from a double linked list
void Ddelete_specified_data(int val)
{
   Dnode *rush, *prev;
   rush = Dhead;
   // find out the value
   while (rush->val != val) {
      prev = rush;
      rush = rush->next;
   }
   // if there is no found or no data in the linked list
   if (rush == NULL) {
      printf("No found!/ No existing data!\n");
      return;
   }
   // now rush is the node which has the value
   // then delete rush
   // if 1st data is rush
   if (rush == Dhead) {
      rush->next->prev = NULL;
      Dhead = rush->next;
   }
   // or if rush is the tail
   else if (rush->next == NULL) {
      rush->prev->next = NULL;
      Dtail =rush->prev;
   }
   // else
   else {
      rush->prev->next = rush->next;
      rush->next->prev = rush->prev;
   }

   free(rush);
}

Dnode *Dtail = NULL;
// insert data to tail of the linked list
void Dinsert_in_tail(int val)
{
   // allocate memory for this new node
   Dnode *data = (Dnode*) malloc(sizeof(Dnode));
   data->val = val;
   data->next = NULL;

   // if there is no existing nodes in the list
   if (Dhead == NULL) {
      // then head = tail = node
      Dhead = Dtail = data;
      data->prev = NULL;
   }
   else {
      Dtail->next = data;
      data->prev = Dtail;
      Dtail = data;
   }

}

int main()
{
   int n;
   printf("Double linked list:\n");
   FILE *fin;
   fin = fopen("input", "r");
   while (fscanf(fin, "%d", &n) != EOF) {
      printf("%d ", n);
      Dinsert_in_tail(n);
   }
   Dshow_list();
   Ddelete_specified_data(5);
   Dshow_list();

   return 0;

}

單向的(也就是基本型態)linked list有個壞處就是不能反向移動。當然使用環狀的結構是可以繼續往下走然後找到自己想要的element，但如果資料過長，而你想要找的資料剛好是目前的正上方，這時候使用環狀結構反而是浪費了一堆時間。因此我們便多使用了一個儲存空間，使用了指標去指向目前node的上一個。

typedef struct Dnode {
   struct Dnode *prev;
   int val;
   struct Dnode *next;
}Dnode;

這樣便能夠反向搜尋我們所要的東西，不過缺點就是每個node都會增加一筆資料空間。而為了示範刪除某值，也必須先建立基本配備。首先我們使用了Dinsert_in_tail()的function，當然這個東西跟我們一般單向的insert_in_tail()邏輯上是大同小異，不再多做介紹，唯一不同之處在於head之前接的會是NULL，因為我們需要一個指標是用來標示尾端。而因為這是雙向的，所以頭也必須要和尾一樣接的是NULL，類似接地的功能。而Dshow_list()也是和show_list()是同樣的function，在此就不贅述了。

雙向linked list在刪除某值的時候，要注意的是我們要處理的工夫會多雙倍。原本的單向只需要把前一個node的next指向下一個node就可以刪除了。但在這邊，我們必須要注意很多地方。

首先是如果我們要刪除的資料是第一筆的話，也就是head，那麼head的前一個node是空指標。刪除掉head的時候必須把下一個node的prev指向空指標：

   if (rush == Dhead) {
      rush->next->prev = NULL;
      Dhead = rush->next;
   }

然後再重新指定head即可。

至於tail也會是類似的處理：

   else if (rush->next == NULL) {
      rush->prev->next = NULL;
      Dtail =rush->prev;
   }

而最後是一般情形，也就是想刪除的資料不是頭也不是尾而是中間。處理方法就是：
(1) 前一個node的next指向下一個node
(2) 下一個node的prev指向前一個node
要離開之前總得要把事情交辦的清清楚楚，前後所指向的指標都得有所依據這樣才不會指向沒有定義的記憶體區塊:

      rush->prev->next = rush->next;
      rush->next->prev = rush->prev;