亲宝软件园·资讯

展开

C++双向链表

机器学习入坑者 人气:3

前言:

前面文章分析了单向链表,并给出了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)链表类分析

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

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

链表类的定义如下:

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;
        }
    }
} 

加载全部内容

相关教程
猜你喜欢
用户评论