C++数据结构与算法之双向链表

链表中的每个节点有两个指针，一个指向前驱，一个指向后继，这种链表称为双向链表。

下图是双向链表，把这个图形记牢了，后续的删除等操作都需要去画一画才能更好的理解。

genDLList.h

#ifndef STRUCTURE_GENDLLIST_H
#define STRUCTURE_GENDLLIST_H

template<class T>

class DLLNode {
public:
    DLLNode() {
        next = prev = 0;
    }

    /**
     *
     * @param el 元素
     * @param n 后继
     * @param p 前驱
     */
    DLLNode(const T &el, DLLNode *n = 0, DLLNode *p = 0) {
        info = el;
        next = n;
        prev = p;
    }

    T info;
    DLLNode *next, *prev;
};

template<class T>
class DoublyLinkedList {
public:
    DoublyLinkedList() {
        head = tail = 0;
    }

    void addToDLLTail(const T &);

    T deleteFromDLLTail();

protected:
    DLLNode<T> *head, *tail;
};

template<class T>
void DoublyLinkedList<T>::addToDLLTail(const T &el) {
    //如果有尾节点
    if (tail != 0) {
        //新建一个节点，后继为null，前驱为tail节点，同时tail指向新创建的节点
        tail = new DLLNode<T>(el, 0, tail);
        //再修改前驱节点的后继为新创建的节点
        tail->prev->next = tail;
    } else {
        head = tail = new DLLNode<T>(el, 0, 0);
    }
}

template<class T>
T DoublyLinkedList<T>::deleteFromDLLTail() {
    T el = tail->info;
    //如果链表只有一个节点
    if (head == tail) {
        delete head;
        head = tail = 0;
    } else {
        //1,tail指针指向前驱
        tail = tail->prev;
        //2,删除现在的tail的后趋，就是之前的尾节点
        delete tail->next;
        //3,把现在tail的后驱设置为null
        tail->next = 0;
    }
    return el;
}

#endif //STRUCTURE_GENDLLIST_H

微信扫描二维码，关注后回复，获取精华资料!

1、回复「书单」：免费获取百本「豆瓣」高分好书。
2、回复「赚钱」：领取实用的36个赚钱小项目。
3、回复「TED」：送你100场TED最受欢迎的演讲，感受最顶尖的思想。
4、回复「学习」：免费获赠英语7000单词速记法（价值200元，很好用），四六级轻松过；
5、回复「PPT」：送你500套好看又实用的PPT模板，让你的PPT颜值爆表]
6、回复「88」：java精品案例,微服务架构Springboot项目实战