05链表(上)
文章目录
1.底层存储结构
数组: 内存空间连续，对内存空间要求高，即使现在有100M空间，但是不连续，当你申请一个100M的数组空间，会失败。
链表: 与数组相反，不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，上面的例子中，如果我们申请一个100M的链表空间，就不会有问题。
2.分类
可分为 单链表,双向链表,单项循环链表,双向循环链表等
2.1 单链表
2.1.1 概念
链表通过指针将一组零散的内存块串联在一起。把内存块称为 结点, 为了将所有的节点串起来，每个链表的结点除了存储数据之外，还需要记录链表的下一个结点的地址，称之为后继指针next
其中第一个结点称为 头结点，最后一个结点称为尾结点，头结点用来记录链表的基地址。尾结点next指向NULL,表示结束。
2.1.1 时间复杂度
- 删除&新增
- 最好 O(1)
- 新增在第一个
- 删除在最后
- 最坏 O(n)?O(1)
- 删除，如果在 在最后一个，则需要先找到当前结点的pre结点，复杂度为O(n),然后把这个pre结点.next=null.
- 新增：O(1)
- 平均O(1)
- 最好 O(1)
- 随机访问 O(n)
- 最好 O(1)
- 最坏 O(n)
- 平均 (1+2+3+…+n)/n = 1/2 + n/2 = O(n)
2.2 双向链表
2.2.1概念
2.2.2 复杂度
- 新增、删除：
- 最好 O(1)
- 最坏 O(1)
- 任何一个位置删除，由于记录了前后两个结点的指针，不需要再遍历查找到前一个指针，所以复杂度为O(1)
- 任何一个新增也是如此
- 随机访问：
- 最好 O(1)
- 最坏 O(n)
- 平均 (1+2+3+…+n)/n = 1/2 + n/2 = O(n)
2.2.3 单链表、双向链表优劣
插入&删除操作
对于删除：基本上就是以下两种操作：
- 删除结点中“值等于某个给定值”的结点
- 删除给定指针的结点
对于第一种情况，都需要遍历整个 单/双 链表，比较每个结点的值，复杂度都为 O(n)，
对于第二种情况，单链表需要先遍历一下链表，找到要删除结点的上一个结点，然后把其next设置为null.复杂度
为O(n). 而对于双链表，由于待删除结点已经包含了 prev/next的指针，因而能够直接找到上一个/下一个结点.复杂度为O(1).
对于 新增，也是如此。
这里涉及到一个重要概念 以空间换时间。双向链表比单向链表每个多了一个空间用于存储prev指针，增加了空间，提高了速度(Java中LinkedList为双向链表)。
2.3 循环链表
3.性能:链表 V.S. 数组
数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。” 这里的CPU缓存机制指的是什么？为什么就数组更好了？
CPU在从内存读取数据的时候，会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址，而是读取一个数据块(这个大小我不太确定。。)并保存到CPU缓存中，然后下次访问内存数据的时候就会先从CPU缓存开始查找，如果找到就不需要再从内存中取。这样就实现了比内存访问速度更快的机制，也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
4.基于链表的LRU缓存淘汰算法
4.1 思路
维护一个有序单向链表，越早访问的数据放入链表尾部。当访问一个数据时，遍历整个链表，如果数据存在，则删除这个数据，之后把他插入头结点；如果数据不存在
* 如果链表已满，则删除尾结点，然后插入该数据到头结点
* 如果链表未满，则直接插入头结点
4.2 实现
-
创建一个单链表
package com.desmond.codebase.algorithm.link; import java.util.LinkedList; /** * 单向链表. * 可以看到，add/remove操作的O(n)都是用于查找，如果简单add/remove,时间复杂度为 O(1). * @author presleyli * @date 2018/12/18 10:07 PM */ public class Link<E> { protected Node<E> head; // 头结点 protected Node<E> tail; // 尾结点 protected int size; /** * 最好：O(1) * 最坏：O(1) * 平均:O(1) * @param e * @return */ public boolean add(E e) { Node<E> node = new Node(e, null); if(this.head == null) { this.head = node; } if(this.tail == null) { this.tail = node; } else { Node l = this.tail; this.tail = node; l.next = node; } size ++; return true; } /** * O(n) * @param index * @param e */ public void add(int index, E e) { Node<E> curr = index(index); // O(n) Node<E> prev = index == 0 ? null : index(index - 1); // O(n) Node newCurr = new Node(e, curr); // O(1) if(prev != null) { prev.next = newCurr; } else { this.head = newCurr; } size ++; } /** * 最好: O(1) * 最坏: O(n) * 平均: (1+2+3+...+n)/n = (n+1)/2 -> O(n) * @param index * @return */ public Node<E> index(int index) { if(index < 0 || index >= size) { throw new RuntimeException("out-of-bound"); } if(this.head == null) { return null; } Node<E> curr = this.head; int idx = 0; while (curr != null) { //n if(idx == index) { return curr; } idx ++; curr = curr.next; } return null; } /** * O(n) * @param index * @return */ public E remove(int index) { Node<E> curr = index(index); // O(n) Node<E> prev = index == 0 ? null : index(index - 1); // O(n) if(curr == null) { return null; } // O(1) Node currNext = curr.next; if(prev != null) { prev.next = currNext; if(currNext == null) { this.tail = prev; } } else { this.head = currNext; } curr.next = null; return curr.e; } /** * 最好：O(1) * 最坏：O(n) * 平均：(1+2+3...+n)/n = (n+1)/2 -> O(n) * @param e * @return */ public int getIndex(E e) { if(size == 0) { return -1; } int idx = 0; Node<E> curr = this.head; while (curr != null) { if(curr.e.equals(e)) { return idx; } idx ++; curr = curr.next; } return -1; } /** * O(n) * @param e * @return */ public boolean remove(E e) { int index = getIndex(e); // O(n) remove(index); // O(n) return true; } @Override public String toString() { Node<E> node = this.head; while (node != null) { System.out.print(node.toString() + " -> "); node = node.next; } return null; } public int size() { return size; } public static class Node<E> { private E e; private Node<E> next; public Node(E e, Node<E> next) { this.e = e; this.next = next; } public E getE() { return e; } public void setE(E e) { this.e = e; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } @Override public String toString() { return "["+e+"]"; } } } -
实现LRU缓存
public class Lru { private static int MAX_SIZE = 2; private static Link<String> link = new Link<>(); private static String[] arr = new String[MAX_SIZE]; /** * O(n). * @param ele */ private static void link2LRU(String ele) { int idx = link.getIndex(ele); // O(n) // O(1) if(idx > -1) { link.remove(idx); if(link.size() == 0) { link.add(ele); } else { link.add(0, ele); } } else { if(link.size() >= 2) { link.remove(link.size - 1); } if(link.size() == 0) { link.add(ele); } else { link.add(0, ele); } } } }
4.3 复杂度分析
O(n)
4.4 引入hash结构降低复杂度
package com.desmond.codebase.algorithm.link;
import java.util.HashMap;
import java.util.Map;
/**
* 单向链表.
* 可以看到，add/remove操作的O(n)都是用于查找，如果简单add/remove,时间复杂度为 O(1).
* @author presleyli
* @date 2018/12/18 10:07 PM
*/
public class LinkHash<E> extends Link<E>{
protected Map<E, Integer> valueMap = new HashMap<>();
protected Map<Integer, Node<E>> keyMap = new HashMap<>();
/**
* 最好: O(1)
* 最坏: O(n)
* 平均: (1+2+3+...+n)/n = (n+1)/2 -> O(n)
* @param index
* @return
*/
public Node<E> index(int index) {
if(index < 0 || index >= size) {
throw new RuntimeException("out-of-bound");
}
return keyMap.get(index);
}
/**
* 最好：O(1)
* 最坏：O(n)
* 平均：(1+2+3...+n)/n = (n+1)/2 -> O(n)
* @param e
* @return
*/
public int getIndex(E e) {
Integer idx = valueMap.get(e);
return idx == null ? -1 : idx;
}
}
5.基于数组的LRU缓存淘汰算法
5.1 思路
维护一个有序单向链表，越早访问的数据放入链表尾部。当访问一个数据时，遍历整个链表，如果数据存在，则删除这个数据，之后把他插入头结点；如果数据不存在
* 如果链表已满，则删除尾结点，然后插入该数据到头结点
* 如果链表未满，则直接插入头结点
5.2 实现
package com.desmond.codebase.algorithm.link;
import com.desmond.codebase.algorithm.link.Link.Node;
/**
* 维护一个有序单向链表，越早访问的数据放入链表尾部。当访问一个数据时，遍历整个链表，
* 1. 如果数据存在，则删除这个数据，之后把他插入头结点；
*
* 2. 如果数据不存在
* a) 如果链表已满，则删除尾结点，然后插入该数据到头结点
* b) 如果链表未满，则直接插入头结点
* @author presleyli
* @date 2018/12/22 8:13 PM
*/
public class Lru {
private static int MAX_SIZE = 2;
private static Link<String> link = new Link<>();
private static String[] arr = new String[MAX_SIZE];
/**
* O(n).
* @param ele
*/
private static void link2LRU(String ele) {
int idx = link.getIndex(ele); // O(n)
// O(1)
if(idx > -1) {
link.remove(idx);
if(link.size() == 0) {
link.add(ele);
} else {
link.add(0, ele);
}
} else {
if(link.size() >= 2) {
link.remove(link.size - 1);
}
if(link.size() == 0) {
link.add(ele);
} else {
link.add(0, ele);
}
}
}
/**
* O(n)
* @param ele
*/
private static void arry2LRU(String ele) {
int idx = -1;
for(int i=0; i<arr.length; i++) { // O(n)
if(arr[i] != null && arr[i].equalsIgnoreCase(ele)) {
idx = i;
break;
}
}
if(idx > -1) {
arr[idx] = null;
insertArrFirst(ele); // O(n)
} else {
if(arr.length >= 2) {
arr[arr.length - 1] = null;
}
insertArrFirst(ele); // O(n)
}
}
/**
* 最好: O(1)
* 最坏: O(n)
* 平均:(1+2+3+..+n)/n -> O(n)
* @param ele
* @return
*/
private static boolean insertArrFirst(String ele) {
if(arr[0] == null) { // 1
arr[0] = ele;
return true;
}
for(int i=arr.length - 1; i>=1;i--) { // n-1
arr[i] = arr[i-1]; // n - 1
}
arr[0] = ele; //1
return true;
}
public static void main(String[] args) {
/////////link.
// 2.数据不存在
// 2.1 未满
link2LRU("1");
System.out.println(link);
link2LRU("2");
System.out.println(link);
// 2.3 已满
link2LRU("3");
System.out.println(link);
// 1.数据存在
link2LRU("2");
System.out.println(link);
/////////arr.
// 2.数据不存在
// 2.1 未满
arry2LRU("1");
printArr();
arry2LRU("2");
printArr();
// 2.3 已满
arry2LRU("3");
printArr();
// 1.数据存在
arry2LRU("2");
printArr();
}
public static void printArr() {
System.out.println();
for(String s : arr) {
System.out.print("arr[" + s + "}->");
}
}
}
5.3 复杂度分析
O(n)