算法与数据结构总结(二)-------数组、链表概述
数组
1.线性表(Linear List)。线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。
2.连续的内存空间和相同类型的数据。正是因为这两个限制,才使得数组具有时间复杂度为O(1)的“随机访问”特点。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。
ps.因为数组是利用连续的内存空间进行数据的存储,因此系统可以使用寻址公式,来计算每个元素存储的内存地址,由此实现随机访问的时间复杂度O(1)。
ps.链表适合插入、删除,时间复杂度O(1);数组适合查找,查找的时间复杂度O(1)”。实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是O(logn)。所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。
链表
1.链表与数组不同,创建链表存储数据时,不需要一块连续的内存空间,它通过“指针”将一组零散的内存块串联起来使用。
2.常见的链表结构:单链表、双向链表和循环链表。
3.数组和链表性能比较:
4.链表应用:实现LRU缓存淘汰算法
缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。
常见的策略有三种:先进先出策略FIFO(First In, First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历链表。
1.如果此数据之前已经被缓存在链表中了,我们遍历得到这个数据对应的结点,并将其从原来的位置删除,然后再插入到链表的头部。
2.如果此数据没有在缓存链表中,又可以分为两种情况:
(1)如果此时缓存未满,则将此结点直接插入到链表的头部;
(2)如果此时缓存已满,则链表尾结点删除,将新的数据结点插入链表的头部。
这样我们就用链表实现了一个LRU缓存。
ps.数组简单易用,在实现上使用的是连续的内存空间,可以借助CPU的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对CPU缓存不友好,没办法有效预读。
理解:CPU在从内存读取数据的时候,会先把读取到的数据加载到CPU的缓存中。而CPU每次从内存读取数据并不是只读取那个特定要访问的地址,而是读取一个数据块并保存到CPU缓存中,然后下次访问内存数据的时候就会先从CPU缓存开始查找,如果找到就不需要再从内存中取。
这样就实现了比内存访问速度更快的机制,也就是CPU缓存存在的意义:为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入。
对于数组来说,存储空间是连续的,所以在加载某个下标的时候可以把以后的几个下标元素也加载到CPU缓存这样执行速度会快于存储空间不连续的链表存储。