双链表

结构

在单链表基础上增加向前的指针，使我们能够知道该结点的前后结点的信息

操作

插入操作

时间复杂度O(1)

直接把当前结点的prev指向前驱，next指向后继；再将前驱的next和后继的prev指向当前结点，插入操作结束！

删除操作

时间复杂度O(1)

将指向当前结点的next指针指向当前结点的后继；

cur.next.prev = cur.prev;

将指向当前结点的prev指针指向当前结点的前驱；

cur.prev.next = cur.next;