数组，链表，跳表（总结）

Array(数组)

image.png

1.优点：无论访问哪一个元素，时间复杂度都是 O(1);
2.缺点：删除，增加元素，时间复杂度高，需要遍历前后移动下标，所以是 O(n)的时间复杂度。删除时，调用垃圾回收机制size-1。

Linked List(链表)

image.png

时间复杂度

image.png

1.每个元素都有两个属性,Value和Next 。它的每一个元素一般用class定义。Next指向下一个元素。串在一起形成了一个链表。
2.如果只有一个指针就叫做单链表，
3.可以往前或者往后指，往前指它的先前指针就做（previous）这样就叫做双向链表。
4.头指针用Head表示，尾指针用Tail。最后一个指针它的Next指向空，因为没有Next指针了。Tail的Next指针也可以指回到Head来。这个就叫做循环链表。

添加删除操作

image.png

1.增加或删除节点的话，没有引起整个链表的群移操作，也不需要复制元素，挪动元素到新的位置，所以它移动的效率和修改的操作效率非常高，复杂度为O(1)
2.这个结构导致了访问链表中的任何一个位置，操作就不再简单了，复杂度为O(n)

Skip List(跳表)

特点

1.只能用于元素有序的情况。（跳表里的元素始终必须是有序的）不然没发用跳表。
所以，跳表（Skip List）对标的是平衡树（AVL Tree）和二分查找，是一种插入/删除/搜索都是 O(log n)的数据结构。1989年出现。
优点：原理简单，容易实现，方便扩展，效率更高。因此在一些热门的项目用来替代平衡树，如Redis，LevelDB 等。