C++怎么实现双向链表

这篇“c++怎么实现双向链表”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“C++怎么实现双向链表”文章吧。

前言:

前面文章分析了单向链表，并给出了python和C++实现：单链表从原理到实现，python和C++两个版本

本文介绍的双向链表是在单向链表基础上的一个改进，每个节点指向其直接前驱和直接后继节点。因此，从双向链表的任意位置开始，都能访问所有的节点。

一、双向链表优缺点

双向链表的缺点：

从节点的结构上可以看出，双向链表的所需的存储空间大于单向链表。同时，对于插入和删除等操作来说，双向链表的节点操作更加复杂，涉及到节点的前后两个节点。

双向链表的节点：

对于双向链表来说，它的每个节点要指向“直接前驱”和“直接后继”，所以节点类需要含有两个指针域。指向直接前驱的指针使用pre表示，指向后继的指针使用next表示。

二、C++实现分析

（1）节点类

双向链表的节点含有两个指针域，即直接前驱pre和直接后继next。节点类采用的是模板实现，这样其所存储的数据就不再依赖于特定类型。

template<class T>class node {public:    Node() {}    Node *pre;    Node *next;    // 由于data属性是私有的    // 所以采用get和set对data进行处理    void setData(T data) { this->data = data; }    T getData() { return this->data; }private:    T data;};

（2）链表类分析

链表类应该包含基本的增、改、删、查等操作，由于其各种功能的实现是很相似的，

所以下面给出了需要实现的典型函数：

• 构造函数：

• isEmpty()判断是否为空；

• size()返回链表长度；

• insert()头插、尾插、中间插入节点；

• delete()删除节点；

• getNode()获取节点；

• traversal()遍历链表；

链表类的定义如下：

template<class P>class DoubleLinkedList {public:    DoubleLinkedList();    bool isEmpty();    Node<P>  *getNode(int index);    int size();    void insert(int data, int index);    void traversal();    void remove(int index);private:    Node<P> *head;};

（3）链表类构造函数

初始化时需要创建头节点，作为头指针：

template<class P>DoubleLinkedList<P>::DoubleLinkedList() {    // 创建头结点    head = new Node<P>();    head->pre = NULL;    head->next = NULL;    head->setData(666);}

（4）isEmpty()判断是否为空

对于双向链表来说，判断是否为空只需要判断头指针是否指向其他Node节点：

template<class P>bool DoubleLinkedList<P>::isEmpty() {    if (head->next == NULL) {        return true;    }    else    {        return false;    }}

（5）size()获取链表长度

获取链表长度时需要判断链表是否为空，从而确定是否采用遍历的方式计算链表的长度。

由于采用的不是循环链表，所以循环的结束条件是判断是否指向空节点：

template<class P>int DoubleLinkedList<P>::size() {    if (isEmpty()) {        return 0;    }    else {        int count = 0;        Node<P> *current = head->next;            // 循环结束条件        while (current!=NULL)        {            current = current->next;            count++;        }        return count;    }}

（6）getNode()获取节点

在插入和删除等操作中，需要频繁的进行节点获取操作。

所以应该封装为单独的函数用于节点获取，如下：

template<class P>Node<P> *DoubleLinkedList<P>::getNode(int index) {     Node<P> *current = head;    int currentCount = 0;    // 循环结束条件    while (currentCount<=index)    {        current = current->next;        currentCount++;    }    return current;}

（7）insert()插入节点

插入节点依旧包含头插法，尾插法和任意位置的插入。插入操作与单向链表的最大区别在于节点的指针移动较为复杂，需要将插入位置前后两个节点与新节点均建立联系：

template<class P>void DoubleLinkedList<P>::insert(int data, int index) {    Node<P> *node = new Node<P>();    node->setData(data);    // 1、列表为空时    if (isEmpty()) {        head->next = node;        node->pre = head;        return;    }    // 2、头插法    if (index == 0) {        node->next = head->next;        head->next->pre = node;        node->pre = head;        head->next = node;    }    // 3、尾插法    else if (index >= this->size() - 1) {        // printf("index %d, size %d \n", index, this->size());        Node<P> *temp = this->getNode(this->size()-1);        temp->next = node;        node->pre = temp;    }    // 4、任意位置插入    else    {        Node<P> *pre = this->getNode(index);        Node<P> *next = pre->next;        node->next = pre->next;        node->pre = pre;        pre->next = node;        node->next->pre = node;    }}

（8）、remove()删除节点

前面已经定义了用于获取节点的getNode()函数，所以remove()函数只需要进行指针移动操作。

将所要删除的节点的直接前驱节点和直接后继节点相连：

template<class P>void DoubleLinkedList<P>::remove(int index) {    // 保证索引有意义    if ((index < (this->size()-1)) && (index>0)) {        Node<P> *node = this->getNode(index);        Node<P> *pre = node->pre;        Node<P> *next = node->next;        pre->next = next;        next->pre = pre;    }}

（9）traversal()遍历链表函数

虽然可以从双向链表的任一个节点开始遍历整个链表，但是下面的实现依旧是从头结点开始的，循环的结束依旧是指向空指针：

template<class P>void DoubleLinkedList<P>::traversal() {    if (!isEmpty()) {        Node<P> *current = head;        while (current)        {            cout << current->getData() << endl;            current = current->next;        }    }}

以上就是关于“C++怎么实现双向链表”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注编程网其他教程频道。