数据结构:3 数组、链表、跳表原理和实现

数组、链表、跳表原理和实现

数组链表跳表

数组

底层实现： 每当申请数组时，计算机在内存中开辟了一串连续的地址。每个地址通过内存管理器访问。 ArrayList增删改查的时间复杂度 操作时间复杂度PrependO(1)AppendO(1)LookupO(1)InsertO(n)DeleteO(n)

链表

LinkedList的标准实现代码: https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/

LinkedList增删改查的时间复杂度

操作时间复杂度PrependO(1)AppendO(1)LookupO(n)InsertO(1)DeleteO(1)

如何给链表加速

以空间换时间

工程中的应用

LRU Cache

LeetCode 题目：https://leetcode-cn.com/problems/lru-cache/

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。 它应该支持以下操作： 获取数据 get 和 写入数据 put 。 1 获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。 2 写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值； 如果关键字不存在，则插入该组「关键字/值」。 当缓存容量达到上限时， 它应该在写入新数据之前删除最久未使用的数据值， 从而为新的数据值留出空间。 进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作？ A 先说下，以前我在项目工程中如何处理这类缓存，时间复杂度应该是没有O(1); 设置一个HashMap<数据，时间戳>，用来存储数据；一个过期时间，用来比较数据是否过期；容量，超过容量后清理HashMap。这样就导致时间复杂度不可能是O(1) B 官方题解1 哈希表 + 双向链表 - key，value 则需要哈希表 - 哈希表 可以实现O(1)的访问速度 - 涉及到插入，删除顺序，则联想到 栈、队列、链表 - 访问完一个数据后，将数据插到头部 - 久未使用的数据据，容量满后，删除尾部的数据，这里就涉及到双向链表 - 删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1) 总结： 哈希表快速找到key值，链表可以快速删除和插入数据 import java.util.HashMap; import java.util.Map; public class LRUCache { class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; public DLinkedNode() { } public DLinkedNode(int key, int value) { this.key = key; this.value = value; } } private Map<Integer,DLinkedNode> cache = new HashMap<Integer, DLinkedNode>(); private int size ; private int capacity; private DLinkedNode head,tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } /** * 时间复杂度O(1) * 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity + 1 * @param key * @return */ public int get(int key){ DLinkedNode node = cache.get(key) ; if ( node == null ){ return -1; } // 如果 key存在，先通过哈希表定位，再移到头部 moveToHead(node); return node.value; } /** * 时间复杂度O(1) * 空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity + 1 * @param key * @param value */ public void put(int key,int value) { DLinkedNode node = cache.get(key); if ( node == null) { DLinkedNode newNode = new DLinkedNode(key,value); cache.put(key,newNode); addToHead(newNode); ++size; //超出容量，删除双向链表的尾部节点 if (size > capacity){ DLinkedNode tail = removeTail(); cache.remove(tail.key); --size; } }else { node.value = value; moveToHead(node); } } /** * 删除尾部节点 * @return */ private DLinkedNode removeTail() { DLinkedNode node = tail.prev; removeNode(node); return node; } /** * 移动到头部 * @param node */ private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } /** * 添加到头部 * @param node */ private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; head.next.prev = node; head.next = node ; } /** * 删除节点 * @param node */ private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; } public static void main(String[] args) { LRUCache cache = new LRUCache(2); cache.put(1,1); cache.put(2,2); //节点1移到头 System.out.println(cache.get(1)); //节点2被删除，3移到头 cache.put(3,3); System.out.println(cache.get(2)); } }

跳表

跳跃表(skiplist)是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,达到快速访问其他节点的目的

增加索引的方式，进行查询元素

n/2,n/4,n/8,第k级索引节点的个数就是 n/(2^k)

假设索引有h级，最高级的索引有2个节点。n/(2^h) = 2，则 h =log_2⁡n – 1

索引的高度：log_2⁡n;

查询任意数据的时间复杂度：0(logn)

Redis中跳跃表的实现图，暂时没有读懂，后续更新