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项目实战

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×