宽屏模式

数据结构与算法之链表

缓存淘汰策略:

  • 先进先出策略FIFO
  • 最少使用策略LFU
  • 最近最少使用策略LRU

单链表:

  • 非连续存储
  • 指针串联
  • 结点:内存块
  • 后继指针next:记录下个结点地址的指针
  • 头结点:第一个结点
  • 尾结点:最后一个结点,指针指向空地址 NULL
  • 时间复杂度
    • 插入、删除O(1)
    • 查询O(n)

循环链表:

  • 特殊的单链表
  • 尾结点指针指向链表头结点
  • 适用于存储有循环特点的数据,如约瑟夫问题

双向链表:

  • 每个结点有两个指针: 后继指针next 和 前驱指针prev
  • 前驱指针prev:指向前面的结点
  • 首结点的 prev和尾结点的 next 都指向 NULL
  • 插入删除操作比单链表更高效

删除操作:

  • 删除结点中给定值的结点
    • 单链表和双链表都需要先遍历查找给定值结点O(n),在删除O(1),总时间复杂度O(n)
  • 删除给定指针指向的结点
    • 单链表删除结点需要知道前驱节点,需要在遍历一次O(n)
    • 双链表结点中已经保存有前驱节点指针无需从新遍历O(1)

指针(引用):

  • 将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,或者反过来说,指针中存储了这个变量的内存地址,指向了这个变量,通过指针就能找到这个变量

哨兵:

  • 针对链表的插入、删除操作,需要对插入头结点和尾结点的情况进行特殊处理,而引入的结点。
  • 不管链表是否为空,head 指针都会指向这个哨兵结点。
  • 哨兵结点不存储数据
  • 哨兵结点一直存在,所以插入、删除所有结点,都可以统一为相同的代码实现逻辑。

带头链表

  • 有哨兵结点的链表

###如何写出优雅的链表代码?

  • 深刻理解指针含义
  • 警惕指针丢失与内存泄漏
    P->next = x
    x->next = p->next
    
  • 巧用哨兵简化实现难度
  • 留意边界条件处理,注意但不限于以下情况代码是否正常工作:
    • 链表为空时
    • 链表只包含一个结点
    • 链表只包含2个结点
    • 代码逻辑在处理头结点和尾结点的时候
    • 不同场景可能还有不同的边界条件需考虑!
  • 举例画图,辅助思考
  • 多写多练,熟能生巧
    • 单链表反转
    • 链表中环的监测
    • 两个有序的链表合并
    • 删除链表中倒数第n个结点
    • 求链表的中间集结点

Larwas
请先登录后发表评论
  • latest comments
  • 总共0条评论