2.数组、链表、跳表的基本实现和特性(7天掌握算法面试必考知识点)

全文内容主要源于极客大学的算法课，仅作为笔记使用。

1、数组

数组：在内存中，占用连续内存空间的，有序的元素序列。
数组元素的类型没有要求，即为泛型。

底层原理

当申请数组时，内存管理器分配一个连续的内存地址。每一个地址可以直接通过内存管理器进行访问。
如下图所示，即为数组相应的内存地址：

直接访问的话，访问第一个元素和访问任意一个元素，时间复杂度都是一样的，为O(1)。

数组特性

访问速度快

访问数组时，其实是利用指针，即内存地址，直接访问对应内存地址中的数值，所以访问速度非常快。
访问数组的时间复杂度：常数复杂度 O(1)

删除和插入: O(n)

如下图所示：
当向数组中插入元素D时，首先要将E、F、G都向下挪动一个位置，然后将index=3的地址值赋值为D。
同理：

• 最慢的插入操作：插入位置为第一个元素位置，要挪动n个元素，时间复杂度为O(n)


• 最快的插入操作：插入位置为最后一个元素位置，不需要挪动元素，时间复杂度为O(1)


• 平均要挪动一半元素

Array各操作时间复杂度

prepend: O(n)，正常情况下是O(n)，但是可以进行特殊优化到O(1)。初始化时申请稍大一些的内存空间，然后在数组最开始预留一部分空间，然后prepend操作只需要把头下标千一一个位置即可。
append: O(1)
lookup: O(1)
insert: O(n)
delete: O(n)

2、链表（LinkedList）

概念

链表：元素由Value和next组成，next指向下一个元素，在内存中是非连续空间。链表元素一般由class定义。
单向链表：如果只有一个next指针，是单向链表。
双向链表：如果由两个指针，next指向下一个元素，先前指针prev或previous指向上一个元素。一般头叫做Head，尾叫做Tail。
循环链表：如果next指向Head，叫做循环链表。

LinkedList定义

最简单的链表定义：

class LinkedList {
Node head; // head of list
/* Linked List Node */
class Node {
int data;
Node next;
Node(int d) { data = d; }
}
}


插入和删除

增加节点

节点增加步骤：

• 插入位置前面的node.next指向new node


• new node的next指向插入位置后面的node 由于只有两步操作，所以时间复杂度为O(1)

删除节点

删除节点为增加节点的逆操作。

删除节点步骤：

• target_node.prev_node.next = target_node.next_node 只有一步操作，时间复杂度为O(1)。

由此可见，链表的增加和删除，没有引起整个链表的群移操作，也不需要复制元素。所以移动或修改链表的效率非常高，时间复杂度为O(1)。
但是，正因为链表的这种特性，当访问中间节点时，必须从Head Node一步一步往后找，时间复杂度为O(n)

链表各操作时间复杂度

3、跳表 Skiped List

科学家在数组和链表基础上，优化了新的数据结构，即 跳表。
主要关注：升维思想+空间换时间

跳表的特点

注意：只能用于元素有序的情况。
所以，跳表对标的是平衡树（VAL Tree）和二分查找，是一种插入/删除/查找 都是O(log n)的数据结构。
它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用于替代平衡树，如Redis、LevelDB等。

如何给有序的链表加速

有序一维数据结构加速理念：经常采用的方式就是升维，也就是说变成二维。
（1）加一级索引

第一级索引指向的是next.next
（2）加二级索引
二级索引next指向的是一级索引链表的next.next

（3）多级索引
以此类推，加多级索引如下图所示：

跳表查询的时间复杂度

n/2、n/4、n/8，第k级索引节点的个数就是n/(2k)
假设索引有h级，最高级的索引有2个结点。n / (2h) = 2，从而求得 h = log2(n) - 1

假设原始链表要查询1024次的话，那么跳表的时间复杂度是log2(n)，即10次就可以找到元素。

现实中的跳表

如下图所示，现实中的跳表，由于多次的增加和删除，导致有些索引并不是完全工整的，最后经过多次改动后，有些地方的索引会多跨几步，有些地方会少跨或只跨两步。
维护成本相对较高，比如增加或删除一个元素的话，索引要更新一遍，此时时间复杂度就变为Logn了。

空间复杂度

跳表的空间复杂度为O(n)，但是比原始链表要多很多。

4、更多

LRU缓存算法
跳表在Redis中的使用
跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？