定义和相关概念

在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

链表分类:

• 单向链表：每个元素只知道它的下一个元素是谁。
• 双向链表：每一个元素知道它的上一个元素也知道它的下一个元素。
• 循环链表：通常的链表尾节点tail指向的都是null，而循环链表的tail指向的头节点head。

链接节点：

• 数据节点：用于真实存储数据。
• 哨兵节点（Sentinel）：不存储数据，通常用作链表的头尾，用于简化判断。有的时候也叫哑元节点（Dummy）。

性能

随机访问

根据index查找，时间复杂度是O(n)

插入或者删除

• 起始位置：O(1)
• 结束位置：如果已知tail尾节点是O(1)，不知道tail尾节点是O(n)
• 中间位置：根据index查找时间 + O(1)