阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/jsumh/
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段
通过这种方式，单链表将所有结点按顺序组织起来
与数组不同，无法在常量时间内O(1)访问单链表中的随机元素，如果想要获得第 i 个元素，必须从头结点逐个遍历(next)
按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度
阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/j47r3/
与数组不同，不需要 将 所有元素 移动到 插入元素之后。因此，可以在 O(1) 时间复杂度中 将新结点插入到链表中，这非常高效
Collection接口的add操作入参是元素E，List接口的add操作入参是int index和元素E
如果index=数组列表长度size，则是直接插入到末尾，对于LinkedList来说时间复杂度是O(1)；否则就要先循环找到index对应的元素节点，此时对于LinkedList来说时间复杂度是O(N)，N最大是size - 2
而对于ArrayList，如果是Collection接口的add，则直接插入到数组末尾，时间复杂度是O(1)；如果是List接口的add，则需要移动数组元素，说时间复杂度是O(N)，N最大是数组大小size
阅读参考
阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/j1wom/
如果想从单链表中删除现有结点 cur，可以分两步完成
在第一步中，需要找出 prev 和 next，使用 cur 的参考字段很容易找出 next，但是，必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)
空间复杂度为 O(1)，因为只需要常量空间来存储指针
Collection接口的remove操作入参是元素E，List接口的remove操作入参是int index
ArrayList 实现Collection接口的remove需要先遍历找到=E的节点，然后删除后再移动剩余元素，所以时间复杂度是O(N)，省略了前面的2；实现List接口的remove直接删除然后移动剩余元素，时间复杂度是O(N)
LinkedList 实现Collection接口的remove需要先遍历找到=E的节点，然后再删除元素，由于LinkedList是双向链表，不需要再循环一次找到prev节点，所以查找+删除时间复杂度是O(N)；实现List接口的remove也需要先遍历拿到index对应的节点，时间复杂度也是O(N)
阅读参考
两种使用双指针技巧的情景：
对于单链表，因为只能在一个方向上遍历链表，所以第一种情景可能无法工作。然而，第二种情景，也被称为慢指针和快指针技巧，是非常有用的
阅读参考：
快慢指针用于判断链表中是否存有环，这两个指针的适当速度应该是多少？
一个安全的选择是 每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针
阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/fpr8s/
双链表以类似的方式工作，但还有一个引用字段，称为“prev”字段。有了这个额外的字段，就能够知道当前结点的前一个结点
阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/fm9td/
添加操作的时间和空间复杂度都是 O(1)
阅读参考：https://leetcode-cn.com/leetbook/read/linked-list/fahuh/
与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点，因为 不再需要 遍历链表 来获取 前一个结点，所以时间和空间复杂度都是O(1)，但是感觉找到要删除的节点也需要时间O(N)的吧？
https://leetcode-cn.com/leetbook/read/linked-list/f217m/，这里有链表 和 其他数据结构 在访问、搜索、插入、删除元素上时间复杂度的不同