2.数组与链表.md

什么是数组?

数组是一种线性表数据结构,它用一组连续的内存空间,来存储一组具有相同类型的数据

线性表

线性表就是数据排成一条线一样的结构

常见的线性表结构: 数组,链表,队列,栈等

优点: 两限制使得具有随机访问的特性

两限制(连续的内存空间和先沟通类型的数据)

缺点: 删除,插入数据效率低

非线性表

比如: 二叉树,堆,图等

在非线性表中,数据并不是简单的前后关系

数据怎么根据下标随机访问的?

通过寻址公式,计算出该元素的内存地址

a[i]_address = base_adress + i * data_type_size

为何数组插入删除低效?

插入: 若有一个元素想要插入 arr[n] 的第k个位置插入数据,需要k-n的位置往后移

删除: 与插入类似,为了保持内存的连续性

最好情况时间复杂度 O(1)

最坏情况时间复杂度 O(n)

平均复杂度 O(n)

提高效率: 将多次删除操作集中在一起执行,可以先记录以及删除的数据,但是不进行数据的迁移,而仅仅是记录,当发现没有更多空间储存时才执行真正的删除操作,这也是JVM标记清除垃圾回收算法的核心思想

为什么数组下标从0开始?

从数组存储的内存模型来看,下标最确切的定义应该是偏移,如果用a来表示数组,a[0]就是偏移为0的位置也是首地址,a[k]就是偏移了k个type_size的位置

所以计算a[k]的内存地址：

a[k]_address = base_address + k * data_type_size

如果数组是从 1 开始计数，那么就会变成：

a[k]_address = base_address + （k-1）* data_type_size

对于CPU来说，多了一次减法的指令,数组作为非常基础的数据结构,效率的优化尽可能做到最好,所以为了减少一次减法操作,数组选择了从0开始编号

当然，还有一定的历史原因,C语言是这样设计的,java,js一类的语言沿用这一设计,或者说这样一定程度上减少C语言程序员学习java的学习成本

什么是缓存?

缓存是一种提高数据读取性能的技术,常见的CPU缓存,数据库缓存,浏览器缓存等

什么是缓存淘汰策略

指的是当缓存被用满时清理数据的优先顺序

有哪些缓存淘汰策略?

常见的三种

1. 先进先出策略 FIFO

2. 最少使用策略 LFU

3. 最近最少使用策略 LRU

什么是链表?

1. 和数组一样,链表也是一种线性表

2. 从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构

3. 链表中的每一块内存块被称为节点Node,节点除了存储数据外,还记录链上下一个节点的地址,即后继指针next

链表的特点

1. 插入,删除数据效率高O(1)级别(只需要更改指针指向),随机访问效率低O(n)级别(需要从头到尾进行遍历)

2. 和数组相比,内存空间消耗更大,因为每个存储数据的节点需要额外的空间存储后继指针

常用链表: 单链表,循环链表,双向链表

单链表: 每个节点只包含一个后继指针;单链表两个特点,首尾节点,首节点地址表示整条链条,尾节点后继指针指向空地址null;性能特点,插入和删除节点时间复杂度都为O(1),查找的时间复杂度为O(n)

循环链表: 尾节点的后继指针指向首节点的地址;适用于存储有循环特点的数据,比如约瑟夫问题

双向链表: 节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next);首节点的前驱指针prev和尾节点的后继指针均为指向空地址;和单链表相比,存储相同的的数据,需要消耗更多的存储空间,插入和删除比单链表效率更高的O(1)级别

链表缺点: 内存空间消耗更大,因为需要额外的空间存储指针信息;对链表进行频繁的插入和删除,会导致频繁的内存申请和释放,容易造成内存碎片

选择

数组简单易用,在实现上使用连续的内存空间,可以借助CPU的缓冲机制预读数组中的数据,所以访问效率更高,而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法预读;如果代码对内存的使用非常苛刻,数组更合适

CPU缓存机制是什么?为什么数组更好?

CPU在内存中读取数据时,会先把读取到的数据加载到CPU缓存,而CPU每次从内存读取数据并不是只读取特定访问地址,二十读取一个数据块,并保存到CPU缓存中,然后下次访问内存数据的时候就会先从CPU缓存中查找,如果找到就不需要再从内存中取,这样就实现比内存访问速度更快的速度,也就是CPU缓存存在的意义: 为了弥补内存访问速度过慢,CPU执行速度过快直接的差异而引入

CPU缓存是加载一个内存数据块,数组是连续的内存,链表是非连续内存,所以数组里面的数据更可能被全部加载到缓存里面去