2022-08-11 ec8929bb4b138496a061aa12455cdd76 99+ 12 分钟 1.8 k0次访问

数据结构基础知识

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

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

假设索引有h级，最高级的索引有2个节点。n/(2^h) = 2,从而求得h = log2(n) - 1

跳表:

原始链表大小为n，每2个结点抽1个，每层索引的节点数： n/2，n/4，n/8，…，8，4，2
原始链表大小为n，每3个结点抽1个，每层索引的节点数： n/3，n/9，n/27，…，9，3，1
空间复杂度是O(n)

跳表查询的时间复杂度分析
第k级索引
第k - 1 级索引

索引的高度：logn，每层索引遍历的节点个数：3
在跳表中查询任意数据的时间复杂度就是O(logn)

解决问题
升级维度
空间换时间

LRU最近最少使用
基于多链表来实现的。

可以通过HashMap + 双向链表实现。
HashMap保证通过key访问数据的时间为O(1)，
双向链表则按照访问时间的顺序一次穿过每个数据。
之所以选择双向链表而不是单链表，是为了可以从中间任意节点修改链表结构，而不必从头结点开始遍历。

Stack 先进后出
添加删除数据时间复杂度是O(1)
查询数据时间复杂度是O(n)
1 boolean empty()
测试堆栈是否为空。
2 Object peek( )
查看堆栈顶部的对象，但不从堆栈中移除它。
3 Object pop( )
移除堆栈顶部的对象，并作为此函数的值返回该对象。
4 Object push(Object element)
把项压入堆栈顶部。
5 int search(Object element)
返回对象在堆栈中的位置，以 1 为基数。

Queue 先进先出
添加删除数据时间复杂度是O(1)
查询数据时间复杂度是O(n)
offer，add 区别：
一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
poll，remove 区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似，但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

Deque 两端可以进出的Queue. Deque - double ended queue
添加删除数据时间复杂度是O(1)
查询数据时间复杂度是O(n)
boolean add(E e)
将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
void addFirst(E e)
将指定元素插入此双端队列的开头（如果可以直接这样做而不违反容量限制）。
void addLast(E e)
将指定元素插入此双端队列的末尾（如果可以直接这样做而不违反容量限制）。
boolean contains(Object o)
如果此双端队列包含指定元素，则返回 true。
Iterator descendingIterator()
返回以逆向顺序在此双端队列的元素上进行迭代的迭代器。
E element()
获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。
E getFirst()
获取，但不移除此双端队列的第一个元素。
E getLast()
获取，但不移除此双端队列的最后一个元素。
Iterator iterator()
返回以恰当顺序在此双端队列的元素上进行迭代的迭代器。
boolean offer(E e)
将指定元素插入此双端队列所表示的队列（换句话说，此双端队列的尾部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用的空间，则返回 false。
boolean offerFirst(E e)
在不违反容量限制的情况下，将指定的元素插入此双端队列的开头。
boolean offerLast(E e)
在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾。
E peek()
获取，但不移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
E peekFirst()
获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
E peekLast()
获取，但不移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
E poll()
获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）；如果此双端队列为空，则返回 null。
E pollFirst()
获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。
E pollLast()
获取并移除此双端队列的最后一个元素；如果此双端队列为空，则返回 null。
E pop()
从此双端队列所表示的堆栈中弹出一个元素。
void push(E e)
将一个元素推入此双端队列所表示的堆栈（换句话说，此双端队列的头部），如果可以直接这样做而不违反容量限制的话；如果成功，则返回 true，如果当前没有可用空间，则抛出 IllegalStateException。
E remove()
获取并移除此双端队列所表示的队列的头部（换句话说，此双端队列的第一个元素）。
boolean remove(Object o)
从此双端队列中移除第一次出现的指定元素。
E removeFirst()
获取并移除此双端队列第一个元素。
boolean removeFirstOccurrence(Object o)
从此双端队列移除第一次出现的指定元素。
E removeLast()
获取并移除此双端队列的最后一个元素。
boolean removeLastOccurrence(Object o)
从此双端队列移除最后一次出现的指定元素。
int size()
返回此双端队列的元素数。