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