链表
链表
链表与数组相似，也是一种线性数据结构。链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。
添加操作
对链表在给定的结点 prev 之后添加新结点 cur
将节点 cur 链接到 prev 的下一个结点 next
将节点 prev 段链接到 cur
与数组不同，不需要将所有元素移动到插入元素之后。因此，链表可以在 O(1) 时间复杂度中将新结点插入到链表中，非常高效。
删除操作
从单链表中删除现有结点 cur
先找到 cur 的上一个结点 prev 及其下一个结点 next ，接下来链接 prev 到 cur 的下一个节点 next
为找出 prev ，必须从头结点遍历链表，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除指定结点的时间复杂度将是 O(N)。而空间复杂度为 O(1)，因为只需要常量空间来存储指针。