链表

  • A+
所属分类:算法与数据结构

链表

不需要申请连续的内存空间。

单向链表,循环链表,双向链表。

插入 删除的时间复杂度为O(1) 随机访问的时间复杂度为O(n)

删除操作:

删除给定值的结点:需要查找此节点,查找+删除复杂度O(1)

删除给定指向的结点:需要找到前驱结点,单链表O(n) 双向链表O(1)

对链表频繁的插入删除操作,导致频繁的内存申请和释放,容易造成内存碎片。

ArrayList动态扩容数组在没有空闲时,会申请更大的空间,将数据拷贝过去。

编写链表代码的技巧:

  1. 理解指针或引用的含义
  2. 注意边界条件的处理
    1. 链表为空,能否正常工作
    2. 链表只有一个结点,能否正常工作
    3. 链表有两个结点,能否正常工作
    4. 代码逻辑在处理头结点和尾结点的时候,能否正常工作
  3. 注意内存溢出和指针丢失问题
  4. 使用哨兵(带头链表)简化实现难度
  5. 举例画图

练习:

  1. 单链表反转(leetcode 206)
  2. 链表中环的检测(141)
  3. 两个有序的链表合并(21)
  4. 删除链表倒数第n个结点(19)
  5. 求链表的中间结点(876)
  6. 回文链表
许龙涛
  • 版权声明:本站原创文章,于2019年5月19日15:46:58,由 发表,共 404 字。
  • 转载请注明:链表 | AICSDN

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: