1.1头插入、尾插入、中间某个位置插入
时间复杂度为O(1)，空间复杂度为O(n)
时间复杂度为O(1),空间复杂度为O(n)
时间复杂度为
O
(
n
2
)
=
O
(
n
)
O(\frac{n}{2})=O(n)
O(2n)=O(n),空间复杂度为O(n)
综上所述，插入的时间复杂度为O(n),空间复杂度为O(n)
1.2 头删除、尾删除、中间某个位置删除
删除头节点要移动n-1个节点，时间复杂度为O(n),空间复杂度为O(n)
时间复杂度为O(1),空间复杂度为O(n)
删除中间某个节点的空间复杂度为
O
(
n
2
)
=
O
(
n
)
O(\frac{n}{2})=O(n)
O(2n)=O(n),空间复杂度为O(n)
1.3查找
假如是根据下标进行查找的话的时间复杂度为O(1),假如是进行遍历查找某个值的话时间复杂度为O(n),空间复杂度都为O(n)
2.1头插入、尾插入、中间某个位置插入
时间复杂度为O(1),假设每个节点所占空间的大小为1，则空间复杂度为O(n)
时间复杂度为O(1),假设每个节点所占空间的大小为1，则空间复杂度为O(n)
插入的话会执行两个操作，插入的节点指向要插入位置的节点，要插入位置的前节点指向插入节点，时间复杂度为O(2),即O(1),假设每个节点所占空间的大小为1，则空间复杂度为O(n)
综上所述链表表删除的时间复杂度为O(1),空间复杂度为O(n)
2.2 头删除、尾删除、中间某个位置删除
时间复杂度为O(1),假设每个节点所占空间的大小为1,空间复杂度为O(n).
时间复杂度为O(1),假设每个节点所占空间的大小为1,空间复杂度为O(n).
删除中间某个节点只有一步操作，删除节点的前驱节点指向被删除节点的后驱节点，故时间复杂度为O(1),假设每个节点所占空间的大小为1,空间复杂度为O(n).
综上所诉删除节点的时间复杂度为O(1),假设每个节点所占空间的大小为1,空间复杂度为O(n).
2.3查找
查找的时间复杂度为O(n),假设每个节点所占空间的大小为1,空间复杂度为O(n).
3.1原始链表图
上图的查询的时间复杂度为O(n)，要怎么进行优化呢，这时候就要用到升维的思想，即以空间换时间，这个思想也贯穿整个数学界和物理学界。
3.2跳表图
第一层索引节点n/2,第二层索引节点n/4,第三层索引节点n/8,以此类推第n层节点
n
2
h
\frac{n}{2^h}
2hn，假设最高级索引的节点数为2，则2=
n
2
h
\frac{n}{2^h}
2hn,得到h=logn - 1。
由上图可以知道，当我们要找到8号这个节点的时候，我们在k级索引发现5<8<9，故我们要到k-1索引下找，但是发现7<8<9,故我们要到原始链表找，且k索引层最多遍历1，5，9三个节点，k-1最多遍历5，7，9三个节点，故跳表的时间复杂度为O(3logn)=O(logn),索引节点总数为：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n
1
2
(
1
−
1
2
n
)
1
−
1
2
\frac{\frac12(1-\frac12^n)}{1-\frac12}
1−2121(1−21n)=n(1-
1
2
n
\frac12^n
21n)=n，故空间复杂度为O(n)
