Day2 线性表之数组与链表

系统管理员 2021-09-18 04:44 389阅读 0赞

#### 数组 ####

主题：为什么数组要从 0 开始编号？

问：什么是数组？
    答：数组是一种线性表结构。用一组连续的内存空间来保存类型一致的数据。
    例如 Java 中定义 int[] arr = new int[5];
     
    问：如何实现随机访问？
    答：两个概念
    	1. 线性表，数组、链表、栈、队列
    	2. 连续的内存空间和相同的数据类型
    	所以才可以 随机访问（数组的杀手锏）
    
    问：数组为什么插入和删除是低效的？
    答： 
    	插入/删除
    		1. 末尾 O(1)
    		2. 头部 O(n)
    
    插曲：
    JVM 的标记-清除算法
    
    问：数组和链表的区别？
    答：链表适合删除和插入，时间复杂度是 O(1)；数组适合查找，支持随机访问，时间复杂度是 O(1)
    
    再问： 为什么数组从 0 开始标号？
    a[i] _address = base_address + i * type_size

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]

##### 链表 #####

主题：如何实现 LRU 淘汰算法？

1. CPU 缓存
    2. 数据库缓存
    3. 浏览器缓存
    
    问：常见的缓存淘汰策略？
    答：
    	1.	FIFO 先进先出 
    	2.	LFU 最少使用
    	3.	LRU 最近最少使用
    
    问：常见的链表结构？
    答：
    	1. 单向链表
    	2. 双向链表
    	3. 循环链表
    注意：
    1. 头结点
    2. 尾节点
    
    删除操作：
    1. 删除结点中 值=某值 的点------删除操作是O(1), 但是表里查找 O(n)
    2. 删除给定指针指向的节点------单向链表是O(1), 双向链表是 O(n)
    
    再问：如何实现 LRU 淘汰算法？
    答：
    	1. 如果数据之前已有，那么遍历将其原来位置删除，并将其插入表头
    	2. 如果没有，判断缓存是否已满。如果已满，将链表尾结点删除，将新的结点插入头		  部；如果未满，将结点插入头部
    
    扩展：
    1. 结合哈希表实现，时间复杂度 O(1)
    2. 使用数组实现 LRU

**链表数组性能比较**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70]: /images/20210918/2817c1050e8647c98c418e802d3d3569.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqYXZhZG9n_size_16_color_FFFFFF_t_70 1]: /images/20210918/96bfb5985b9a4a80927b5093ba16ff6d.png