集合

链表底层数据结构

❒ 单向链表
✔ 只有在查询头节点的时候不需要遍历链表，时间复杂度是0(1)
✔ 查询其他结点需要遍历链表，时间复杂度是O(n)
✔ 只有在添加和删除头节点的时候不需要遍历链表，时间复杂度是O(1)
✔ 添加或删除其他结点需要遍历链表找到对应节点后，才能完成新增或删除节点，时间复杂度是O(n)

❒ 双向链表
✔ 而双向链表，顾名思义，它支持两个方向
✔ 每个结点不止有一个后继指针next指向后面的结点
✔ 有一个前驱指针prev指向前面的结点

❒ 双向链表 first prev next last 时间复杂度
✔ 查询（增删）头尾结点的时间复杂度是O(1)
✔ 平均（增删）的查询时间复杂度是O(n)
✔ 给定节点找前驱（增删）节点的时间复杂度为O(1)

❒ 双向链表对比单链表
✔ 双向链表需要额外的两个空间来存储后继结点和前驱结点的地址
✔ 支持双向遍历，这样也带来了双向链表操作的灵活性

❒ 单向链表和双向链表的区别是什么
✔ 单向链表只有一个方向，结点只有一个后继指针next。
✔ 双向链表它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。