数组、链表、跳表基本实现和特性

Array(数组)

  • java,c++: int a[100];//初始化的时候先定义好容量
  • Python： list=[]//直接定义一个数组
  • JavaScript: let x=[1,2,3]

时间复杂度

方法 复杂度
prepend O(n)
append O(1)
lookup O(1)
insert O(n)
delete O(n)

链表

  1. 在链表中，每个元素都有两个属性,Value和Next 。它的每一个元素一般用class定义。Next指向下一个元素。

  2. 如果只有一个向后的指针时，这样的链表叫做单链表。

  3. 当有两个指针时，这样的链表就叫做双向链表。

  4. 头指针用Head表示，尾指针用Tail。最后一个指针它的Next指向空，因为没有Next指针了。Tail的Next指针也可以指回到Head来。这个就叫做循环链表。

1
2
3
4
5
6
7
8
class Node {
    int data;
    Node next;
}
class LinkedList {
	Node head; 
    Node (int d) { data = d;}
}

时间复杂度

方法 复杂度
prepend O(1)
append O(1)
lookup O(n)
insert O(1)
delete O(1)

跳表

跳表是为了优化或者是弥补链表的缺陷而设计的。

在原始链表上建立多级索引以提高速度，空间换时间

image-20200825111255912

复杂度分析

跳表查询的时间复杂度分析：

时间复杂度：

每次访问一个元素，需要遍历索引的高度，即log n，时间复杂度O(log n)

空间复杂度 ：

索引的节点数为 n/2、n/4、n/8… 整体不会超过n，空间复杂度为O(n)

应用

  1. LRU Cache - Linked list: LRU 缓存机制

  2. Redis - Skip LIst