集合

链表底层数据结构

❒ 单向链表

链表中的某个节点为B，B的下一个节点为C
表示:B.next == C

✔ 只有在查询头节点的时候不需要遍历链表，时间复杂度是0(1)
✔ 查询其他结点需要遍历链表，时间复杂度是O(n)

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

❒ 双向链表

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

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

first prev next last

✔ 查询（增删）头尾结点的时间复杂度是O(1)
✔ 平均（增删）的查询时间复杂度是O(n)
✔ 给定节点找前驱（增删）节点的时间复杂度为O(1)

❒ 单向链表和双向链表的区别是什么
✔ 单向链表只有一个方向，结点只有一个后继指针next。
✔ 双向链表它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点
❒ 链表操作数据的时间复杂度是多少
❒   查询           新增删除
✔ 单向链表   头0(1),其他0(n)
✔ 双向链表   头尾0(1),其他O(n),给定节点0(1)