雙向鏈表基本操作

雙向鏈表的情況與單鏈表類似，只是增加了一個前置鏈（即指向前一結點的指針域）
算法等，與單鏈表很相似。只是需要安置好前向指針域。

注意點：在寫關於鏈表的插入刪除操作時，一定要注意該結點是不是最後一個結點，以免出現 p->next == NULL，p->next->next 未定義的情況，從而導致程序在特定條件下（比如你刪除最後一個節點）出錯。
也就是需要注意，最後一個節點和其他節點的操作不同，需要分開寫。

以下是代碼：

#include <iostream>

using namespace std;

typedef struct BNode{
    int data;
    struct BNode *pre,*next;
}BListNode;

/**雙鏈表創建*/
BListNode * Create_BList(int n)
{
    int i = 1;
    int elem;
    BListNode *head, *temp, *curr;
    /**curr：代表一個當前節點，它的下一節點是你正要創建的。*/
    /**temp：代表你正要創建的節點。*/
    head = new BListNode;
    head->data = n;
    head->pre = NULL;
    head->next = NULL;
    curr = head;

    while(i <= n)
    {
        cout << "Please input one elem" << endl;
        cin >> elem;
        temp = new BListNode;
        temp->data = elem;
        temp->pre = curr;
        temp->next = NULL;
        curr->next = temp;
        curr = temp;

        i++;
    }

    return head;
}

/**雙鏈表輸出*/
void Output_BList(BListNode *head)
{
    BListNode *temp;
    temp = head->next;
    if(NULL == temp)
        cout << "The BList is NULL" << endl;

    cout << "The BList is" << endl;
    while(NULL != temp)
    {
        cout << temp->data << ' ';
        temp = temp->next;
    }
    cout << endl;
}

/**刪除元素i，不知道它是第幾個結點*/
BListNode * Delete_node(BListNode *head,int i)
{
    BListNode *pre_temp, *temp;
    temp = head->next;
    pre_temp = head;   /**這一步必須要有，防止刪除的節點是第一個節點*/
    if(NULL == temp)
        cout << "The BList is NULL" << endl;
    while(NULL != temp)
    {
        if(temp->data != i)
        {
            pre_temp = temp;
            temp = temp->next;
        }
        else{
                if(NULL == temp->next)  /**如果刪除的元素是最後一個，需要加這一步，不然按下面寫，temp->next->pre會沒有定義，從而出錯*/
                {
                    pre_temp->next = NULL;
                    delete temp;
                    break;
                }
                pre_temp->next = temp->next;
                temp->next->pre = temp->pre;
                delete temp;
                break;
        }
    }
    if(NULL == temp)
        cout << "There is no i to be delete" << endl;

    return head;
}

/**插入一個節點：在第i個節點後，插入elem*/
BListNode * Insert_node(BListNode *head,int i,int elem)
{
    int j = 0;
    BListNode *temp, *p;
    temp = head;         /**這裡講temp = head 並且 j = 0，保證了節點可以插入在第一個節點前*/
    while(NULL != temp)
    {
        if(j >= i)
            break;       /**指針停留在第i個節點前*/
        j++;
        temp = temp->next;
    }
    if(NULL == temp->next)   /**當第i個節點是最後一個節點時*/
    {
        p = new BListNode;
        p->data = elem;
        p->next = NULL;
        p->pre = temp;
        temp->next = p;

        return head;
    }
    p = new BListNode;
    p->data = elem;
    p->next = temp->next;
    p->pre = temp->next->pre;
    temp->next->pre = p;
    temp->next = p;

    return head;
}

int main()
{
    BListNode *p;
    p = Create_BList(5);
    Output_BList(p);

    Delete_node(p,2);   /**注意可以這樣寫，和 p = Delete_node(p,2);效果相同*/
    cout << "刪除結點後" << endl;
    Output_BList(p);

    Insert_node(p,0,6);
    cout << "插入結點後" << endl;
    Output_BList(p);

    return 0;
}

結果如下：