1、数组（Array）查询操作：每个数组对应一系列连续的内存地址，每个元素对应这一系列连续的地址中的一个地址。这些地址由内存管理器（Memorycontroller）管理。因此，访问任意元素的时间复杂度为O(1)，而数组的空间复杂度为O(n)。对于下标位置之后的所有元素，第二步在指定下标位置插入元素，时间复杂度为O(n)。如果插入到最后一个元素，不需要再移动其他元素，时间复杂度为O(1)；如果插入到第一个位置，需要移动所有元素，时间复杂度为O(n)。所以总的时间复杂度是O(n)。删除操作：与插入操作相同，分两步，先删除指定元素，再向前移动后面的元素。需要注意的是，向前移动后，原来的最后一个元素的位置被设置为空，可以调用垃圾回收机制或者重新调整数组的大小。2.链表（LinkedList）链表由Head、Tail和中间节点组成。每个节点（包括Head和Tial）由value和Next指针组成，Next指向下一个节点。如果每个节点都包含指向前一个节点的Prev/Previous，则该链表为双向链表，如果不包含Prev，则该链表为单向链表。如果Tail的Next指向None，则链表为普通链表；如果Tail的Next指向Head，那么这个链表就是循环链表。随机访问链表节点的时间复杂度为O(n)添加节点的操作：之前一个节点的Next指向新的Node，新Node的Next指向原来指向的Node前一个节点Next，时间复杂度为O(1)。删除节点操作：删除上一个节点的Next，需要删除。上一个节点的节点，上一个节点的Next指向被删除节点的下一个节点，时间复杂度为O(1)区分和数组的增删操作：时间复杂度的原因数组是O(n)是元素需要移动，链表复杂度是O(1)的原因是不需要移动元素，只需要改变节点的指向节点指针。3.跳表跳表匹配平衡树（AVLTree）和二分查找。是一种插入、删除、查找复杂度为O(logn)的数据结构。使用跳表的前提条件：必须是元素有序的链表，也就是说，跳表必须是有序的。最大优点：原理简单，易于实现，易于扩展，效率更高。在一些流行的项目中用于替代平衡树，如Redis、LevelDB等。跳表搜索相对于原链表的优化思路：增加维度，以空间换时间。在一维的基础上，根据需要添加一维或多维的搜索索引。例如：要在链表中查找数字5，首先比较1-7，数字小于7，然后在下一个索引中比较1-4，大于4，小于7，因此查找5在下一个索引中。跳表查询时间复杂度分析：n/2、n/4、n/8，k级索引节点个数为n/(2^k)，假设索引有h级，最高索引有2节点。n/(2^h)=2，所以h=log2(n)-1。在跳表中查询任意数据的时间复杂度为O(logn)。现实中，跳表的索引并不是完全整齐的，每次节点的增删改查都会引起跳表索引的更新，维护成本很高，时间复杂度为O(logn)。跳表空间复杂度分析：原链表大小为n，每2个节点选一个，每个索引层的节点数：n/2,n/4,n/8,...,8,4,2原链表的大小为n，每3个节点一个，每层索引的节点数：n/3,n/9,n/27,...,9,3,1,所以空间复杂度为O(n)总结：跳表优化了原来链表查询操作的时间复杂度，从O(n)降到了O(logn)，但是由于加入了multi-级索引，跳表的空间复杂度仍然是O(n)），没有优化。
