双向链表基本操作

双向链表基本操作

双向链表的情况与单链表类似，只是增加了一个前置链（即指向前一结点的指针域）
算法等，与单链表很相似。只是需要安置好前向指针域。

注意点：在写关于链表的插入删除操作时，一定要注意该结点是不是最后一个结点，以免出现 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;
}

结果如下：

本文永久更新链接地址：