双重链表
双链表是一种链表 。双向链表的节点有两个指向其他节点的指针，下一个和前一个。它被称为双链表，因为每个节点只有两个指向其他节点的指针。双向链表可以具有头部和/或尾部指针。
┌─────────┬─────────┬─────────┐ ┌─────────┬─────────┬─────────┐
null ◀──┤previous │ data │ next │◀──┤previous │ data │ next │
│"pointer"│ │"pointer"│──▶│"pointer"│ │"pointer"│──▶ null
└─────────┴─────────┴─────────┘ └─────────┴─────────┴─────────┘
▲ △ △
HEAD │ │ DOUBLE │
└──── REFERENCE ────┘
双链表比单链表更节省空间; 但是，对于某些操作，它们可以显着提高时间效率。一个简单的例子是 get 函数，对于带有头部和尾部引用的双向链表，它将从头部或尾部开始，具体取决于要获取的元素的索引。对于 n 元素列表，要获取 n/2 + i 索引元素，带有头/尾引用的单链表必须遍历 n/2 + i 节点，因为它不能从尾部返回。带有头/尾引用的双向链表只需要遍历 n/2 - i 节点，因为它可以从尾部返回，以相反的顺序遍历列表。