双向链表的实现

简介

双向链表是单链表的升级版，在双向链表中可以在O(1)的时间内访问到节点的前驱，这在单链表中需要重新开始遍历，双向链表无疑让链表的插入和删除操作更加简便，仅使用一个已知的指针就可以完成操作。但是每个节点需要消耗额外的指针空间来存放节点的前驱信息，典型的空间换时间的例子。

不带头结点的双向链表

链表定义（head.h）:

#include <iostream>
using namespace std;
struct Node {
    int value;
    Node* pre;
    Node* next;
    Node(int num) :value(num), pre(NULL), next(NULL) {};
    Node() {};
};
/*不带头结点的双向链表*/
class DoublyLinkList {
public:
    void create();           //初始化
    void insertHead(Node*);  //头插法
    void insertByIndex(Node*,int);
    Node* findByValue(int);  //根据值查找节点，并返回节点的指针
    Node* findByIndex(int);  //根据索引查找节点，并返回节点的指针
    void deleteByValueOnce(int); //根据节点值删除第一个节点
    void deleteByValueAll(int);//根据节点值删除所有节点
    void print();
    //void reverse();
private:
    Node* head;        //第一个节点指针
};

链表实现（DoublyLinkList.cpp）:

#include "head.h"
void DoublyLinkList::create() {
    head = NULL;
}
void DoublyLinkList::insertHead(Node* p) {
    p->next = head;
    if (head != NULL)
        head->pre = p;
    head = p;
    p->pre = NULL;
}
void DoublyLinkList::print() {
    for (Node* p = head;p;p = p->next)
        cout << p->value << " ";
    cout << endl;
}
Node* DoublyLinkList::findByValue(int value) {
    for (Node *p = head;p;p = p->next) {
        if (p->value == value)
            return p;
    }
    return NULL;
}
Node* DoublyLinkList::findByIndex(int index) {
    if (index <= 0) {
        cout << "索引非法！" << endl;
        return NULL;
    }
    else {
        Node* p = head;
        for (int i = 1;p;p = p->next,i++) {
            if (i == index)
                return p;
        }
        cout << "索引非法！" << endl;
        return NULL;
    }
}
void DoublyLinkList::deleteByValueOnce(int value) {
    Node* deleteNode = findByValue(value);  //先查找该点是否存在
    if (!deleteNode)
        cout << "你想删除的节点不存在！" << endl;
    else {
        if (deleteNode->pre != NULL)  //判断前驱是否为空
            deleteNode->pre->next = deleteNode->next;
        else
            head = deleteNode->next;
        if (deleteNode->next != NULL) //判断后驱是否为空，如果后驱为空，就不用考虑后驱的前驱链接问题
            deleteNode->next->pre = deleteNode->pre;
        delete deleteNode;
    }
}
void DoublyLinkList::deleteByValueAll(int value) {
    Node* p = head;
    while (p) {
        if (p->value == value) {  //相等的时候处理情况
            Node* deleteNode = p;
            if (deleteNode->pre != NULL)
                deleteNode->pre->next = deleteNode->next;
            else
                head = deleteNode->next;
            if (deleteNode->next != NULL)
                deleteNode->next->pre = deleteNode->pre;
            p = p->next;
            delete deleteNode;
        }
        else  //不相等处理情况
            p = p->next;
    }
}

void DoublyLinkList::insertByIndex(Node* insertNode, int index) {
    Node* p = findByIndex(index);
    if (p) {
        if (p->pre != NULL) {
            p->pre->next = insertNode;
            insertNode->pre = p->pre;
        }
        else
            head = insertNode;
        insertNode->next = p;
        p->pre = insertNode;
    }
}

测试函数（main.cpp）你也可以自行编写测试函数：

#include "head.h"
int main() {
    int n,num;
    DoublyLinkList dll;
    dll.create();
    cout << "请输入节点个数：";
    cin >> n;
    while (n--) {
        cin >> num;
        dll.insertHead(new Node(num));
    }
    cout << "头插法结果：";
    dll.print();
    cout << "输入你想删除的节点值：";
    cin >> num;
    dll.deleteByValueOnce(num);
    cout << "删除后的结果：";
    dll.print();

    cout << "输入你想删除的节点值：";
    cin >> num;
    dll.deleteByValueAll(num);
    cout << "删除后的结果：";
    dll.print();
    cout << "输入你想插入的数值，和位置：";
    cin >> n >> num;
    dll.insertByIndex(new Node(n), num);
    dll.print();
}

带头结点的双向循环列表

不知道你注意到没：
1.在insertHead函数中，每次插入都需要判断head是否为空，降低程序效率
2.在deleteByValueOnce函数中，需要每次删除时都需要判断待删节点的前驱和后继是不是为空，然后才能使用前驱和后继所指向的内存数据。
以上如果我们能忽视表头和表尾处的边界条件，代码会更加简单。

所以引入头结点并使链表首尾呼应，即可摆脱边界处理，因为我们已经把节点当做了链表中的一部分。
带头结点的双向循环链表的定义：

#include <iostream>
using namespace std;
struct Node {
    int value;
    Node* pre;
    Node* next;
    Node(int num) :value(num), pre(NULL), next(NULL) {};
    Node() {};
};
/*带头结点的双向循环链表*/
class DoublyLinkList {
public:
    void create();           //初始化
    void insertHead(Node*);  //头插法
    Node* findByValue(int);  //根据值查找节点，并返回节点的指针
    void deleteByValueOnce(int); //根据节点值删除第一个节点
    void print();
    //void reverse();
private:
    Node* head;/*头结点*/
};

DoublyLinkList 的实现代码：

#include "head.h"
void DoublyLinkList::create() {
    head = new Node(0);/*让头结点的数值域初始为0*/
    head->next = head;
    head->pre = head;
}
void DoublyLinkList::insertHead(Node* p) {
    p->next = head->next;
    head->next->pre = p;
    p->pre = head;
    head->next = p;
}
void DoublyLinkList::print() {
    for (Node* p = head->next;p!=head;p = p->next)
        cout << p->value << " ";
    cout << endl;
}
Node* DoublyLinkList::findByValue(int value) {
    for (Node *p = head->next;p!=head;p = p->next) {
        if (p->value == value)
            return p;
    }
    return NULL;
}
void DoublyLinkList::deleteByValueOnce(int value) {
    Node* deleteNode = findByValue(value);  //先查找该点是否存在
    if (!deleteNode)
        cout << "你想删除的节点不存在！" << endl;
    else {
        deleteNode->pre->next = deleteNode->next;
        deleteNode->next->pre = deleteNode->pre;
        delete deleteNode;
    }
}

findByValue函数的进一步优化

在上面的带头结点的双向循环链表中查询函数中发现每次循环都要判断p!=head，如何在每次循环中省略对怕p！=head的检查呢？

思路：充分运用我们的头结点，之前定义的头结点的数据域我们默认给值为0，这里我们可以让其充当哨兵的作用（sentinel）,把要查询的值复制给head->value，在我们跳出循环中，再判断是否p!=head。因为能使循环中断的条件为p->value == value，只能有2种情况，一真的找到了；二重新遍历到头结点了。

优化后的代码：

Node* DoublyLinkList::findByValue(int value) {
    head->value = value;
    Node *p = head->next;
    while (p->value == value)
        p = p->next;
    if (p != head)
        return p;
    return NULL;

}