1.2 链表

链表（Linked list）是一种物理存储单元上非连续的数据结构，数据元素的逻辑顺序是通过链表中的指针实现的。由于不必按顺序存储，链表在插入的时候可以达到O(1)的复杂度，但链表查找的时候由于不能通过索引查找，所以查找的时间复杂度是O(n)。常见的链表有单向链表、双向链表，以及环形链表。

1. 单向链表

单向链表是一种最简单的链表，一般只包含存储的数据和指针（注意这里的指针并不是C语言中的地址指针，它是下一个节点的引用），每个指针指向下一个节点，最后一个节点的指针指向空，如图1-10所示。

•图1-10

2. 双向链表

双向链表的每个节点都有两个指针，一个指向前一个节点，一个指向后一个节点，头节点的前一个节点为空，尾节点的后一个节点也为空，如图1-11所示，在Java中可以参考LinkedList。

•图1-11

3. 环形链表

环形链表是一种首尾相连的链表，环形链表分为单向环形链表和双向环形链表。在Java中可以参考LinkedHashMap。

4. 链表和数组的区别

•数组静态分配内存，链表动态分配内存；

•数组在内存中连续，链表不连续；

•数组利用下标访问，时间复杂度为O(1)，链表访问元素时间复杂度为O(n)；

•数组插入或删除元素的时间复杂度为O(n)，链表插入或删除的时间复杂度为O(1)，前提是要知道插入和删除的位置。

5. 跳表

链表虽然插入和删除效率比较高，但也有缺点，即使链表节点是有序的，还是需要从前往后一个个查找，这样显然很慢，这个时候我们可以使用跳表，跳表就是多层链表，最下面一层是原始链表，从下往上节点个数逐渐减少，如图1-12所示。

•图1-12

查询的时候先从最上面一层索引开始查，如果查找值在两个节点之间，就到下一级索引继续查，比如要查找8，查找过程如图1-13所示，在图中已经用粗线标出。

•图1-13