1. 数组 Array
数组其实是一个相对来说比较简单的数据结构，数组中元素的存储有先后顺序，定义一个数组之后，会在内存中开辟一个连续的内存空间，通过内存管理器访问任意的位置其事件复杂度都为O(1)。对于Python本身而言，并没有内置的数组结构，可以是使用numpy这样的库，对于一维数组而言，通常用列表 (list)来代替。在数组中存放的数据必须是相同类型的，但是列表中则没有要求。
在对数组或者列表进行操作时，元素的插入和删除在内存中都会涉及到大量复制操作，时间复杂度较大，通常为O(n)。
2. 链表 Linked List
链表是一种线性表，但并不要求按照线性顺序存储数据。链表中的元素被称为结点(Node)，每个结点包含两个元素：结点的值(value)和指向下一个元素的指针(Next)。头结点称为head，尾结点称为tail。
单向链表 Singly Linked List
每个结点的next指针都只指向下一个结点，尾结点的指针指向null。
1
2
3
4
5#definition for a singly linked list
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
双向链表 Doubly Linked List
双向链表中的Node除了有next指针以外，还有一个指向前结点的previous指针。head的prev指针指向Null或者空列表，tail的next指针指向Null或者空列表。
循环链表 Circular Linked List
在循环链表中，tail的next指针指向head，这种方式在单链表和双向链表中都可以实现。也可把循环链表看作“无头无尾”的链表，这种模式有利于节约数据缓存。
在链表中插入新结点是，只需要将前结点的指针指向新元素，新元素的指针指向原来的下一个结点即可，总共需要操作两次，但都是常数级别的时间复杂度。删除操作即为增加操作的逆过程，也是常数时间复杂度。但是无果要访问链表中任意的元素，一般需要从头开始访问，平均而言时间复杂度为O(n)。
3. 跳表 Skip List
为了解决链表的查询时间复杂度较高的问题，跳表应运而生。 跳表中的元素必须是有序的 。跳表的插入，删除和搜索都是O(logn)。
对于一个一维的数据结构来说，要想减小对其操作的时间复杂度，一般来说有两个方法：升维和空间换时间 。当数据从一维升到二维的时候，多了一个维度，就多了一级信息，操作的时候自然也就快一点了。空间换时间的话就是牺牲内存来节省操作时间。
假设第一级索引在原始链表的基础上以步长2进行搜索，第二级也是如此。假设我们要查询value=8的元素，从最高级索引出发，知道元素链表为止。
时间复杂度分析：假设原始链表有n个结点，每一级索引都按照2的步长搜索，则第k级索引的结点数为$\frac{n}{2^k}$ , 假设一共有h级索引，最高级只有2个结点，则可计算出跳表的深度为$log_{2}(n)$，即跳表查询的时间复杂度为O(logn)。由于跳表是多维的结构，所以其增加和删除的时间复杂度都为O(logn)。
空间复杂度分析：无论是以多少为步长进行抽取，最终每一级索引的元素数量之和都是收敛到n的，所以空间复杂度为O(n)。
4. 时间复杂度比较
| prepend | append | lookup | insert | delete | |
|---|---|---|---|---|---|
| List | O(1) | O(1) | O(1) | O(n) | O(n) |
| Linked list | O(1) | O(1) | O(n) | O(1) | O(1) |
| Skip list | - | - | O(logn) | O(logn) | O(logn) |