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

数组

数组常见写法：Java int a[100]

高级语言对数组元素的类型没有严格的要求，就是泛型。

数组底层硬件的实现（内存管理器）

申请数组的时候，计算机是在内存中开辟了一段连续的内存地址。每个地址可以通过内存管理器进行访问。



使用数组访问元素的时间复杂度是 O(1)

数组是如何噶咕的

添加和删除元素需要移动数组，时间复杂度是 O(n)

参考

• Java 源码分析（ArrayList）

  链表

参考

• Linked List 的标准实现代码
• Linked List 示例代码
• Java 源码分析（LinkedList）
• LRU Cache - Linked list： LRU 缓存机制

  跳表

参考

• Redis - Skip List：跳跃表、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？