链表中的每个节点有两个指针,一个指向前驱,一个指向后继,这种链表称为双向链表。
下图是双向链表,把这个图形记牢了,后续的删除等操作都需要去画一画才能更好的理解。

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