Linked List

与数组并列的另一种最基础的线性数据结构

Singly Linked List
  • 有两种常用的链表：单向链表和双向链表
  • 没法在常数时间内获取一个链表中的一个随机元素，但链表的插入操作是常数时间，如果已经找到指定的操作位置后，删除操作也是O(1)
Two Pointer Technique
  • 链表常常是双指针技术中快慢指针的使用场景
  • 判断链表中是否有环这个经典的问题可以用哈希表来存储每个结点的指向，遍历结点，判断这个结点是否已经出现在哈希表中了，还可以用快慢双指针技术来解决，一般慢指针每次移动一步，快指针每次移动两步
  • 链表中双指针的使用，技巧性更强，更容易出错
Classic Problems
  • 翻转链表、判断链表是否回文等经典的题目做了一下并不是都能思路清晰
  • 链表的debug不是那么容易，用具体的例子试验可能更好
Doubly Linked List
  • 因为双向链表保留有前一个结点的指针，所以删除的操作前不需要O(N)时间复杂度的查找
  • 双向链表的每一个结点都有两个指针，所以对null情况的判断比单向链表变多了，变复杂了

总结：如果增删结点频繁，链表会是一个比较好的选择；如果总是想通过下标来获取一个元素，数组会更好。链表中的一些题目也还是有点难度，也还需要再做一遍。

赏

谢谢你请我喝咖啡

微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家