计算机的内存 _链表

1.内存的物理机制
内存和CPU一样，都是由大量引脚构成的集成电路，内存大致分为这几类：1.ROM:只能进行读取；2.DRAM：需要经常刷新就能进行保存数据的可被读取和写入的内存；3.SRAM：不需要经常刷新就能进行保存数据的可被读取和写入的内存。内存的引脚按作用大致分为电源、控制信号、数据信号以及地址信号。如下图所示为典型的内存的引脚配置示例。
如图所示，其中VCC和GND为电源引脚，分别接入5V和0V就能进行供电。D0-D7是数据信号，一个引脚存移位数据，一次就可以存储8位也就是一个字节的数据。A0-A9为地址引脚，一共10个引脚，一共能存储2^10=1024个地址，也就是内存能放下1024B=1K的数据。RD和WD为控制引脚，分别为read和write的缩写，当他们分别设定为1时，表示读出和写入的操作。
2.内存的逻辑模型
一般对内存的逻辑模型都会定义为楼房，每一层存储这1B的数据，像之前的内存，就是1024层楼房。但是八大基本数据类型所占据的内存空间有一个字节，也有多个字节的，所以在内存中按不同的变量类型所占据的“楼层”数就不一样。如下图所示为将数据低位存储在内存低位地址的低字节序。
3.指针与数组
指针也是一个变量，不过它表示的不是数据的值，而是内存当中存储数据的地址的值。在定义指针时，通常会以short *d的方式来定义指针变量，之所以在指针变量之前定义数据类型，其代表的是该指针变量一次能在内存中读取的长度。如果short数据类型的字节数为2个，代表该指针一次性可以在内存中取走两位地址的数据，其它数据类型类似。
数组是指多个同样的数据类型的数据在内存中连续排列的形势，而各个数据都会通过连续的编号区分开来，这个编号就是索引，例如声明一个长度为10的整数型数组，声明方式为int[]arr=new int[10]，不同数据类型的数组其在内存中的排列方式如下：
4.栈、队列以及环形缓冲区
如果内存中所有的数据都是通过数组和索引来进行读写，那么临时保存在计算过程中的数据、连接在计算机上的设备或者输入输出的数据时，就会变得比较麻烦。所以内存中会存在不通过指定地址和索引来进行数据读写的方法。
栈与队列就是其中两种，它们的区别就是数据读入和写出的先后顺序不同，下面的图分别为栈和队列数据写入和读出的过程，从两图中可以看出，栈的数据时先入后出，而队列的数据时先入先出。从理解上来看，栈的意思是“干草堆积如山”，干草堆积如山，要取干草，肯定是从最上面一层来取。
而队列排队，肯定是先到先得。队列一般是以环形缓冲区的方式来实现的，这样实现首尾相连，数据的读写也就可以循环起来了。

文章插图
5.链表与二叉树
链表与二叉树是不用考虑索引的顺序就可以对数组元素进行读写的方式。通过使用链表，可以更高效地对数组元素进行追加和删除，而二叉树主要用于数据的高效检索上面。
所谓链表就是数组的每个元素中，除开数据的值，还会附带下一个数据的索引，即可实现列表，如下图所示，索引-1表示为为链表的末尾。
链表的优势在于删除与追加数据比较方便，不用像传统数组一样一次性移动全部数据。
【计算机的内存】二叉查找树是指在链表的基础上往数组中追加元素时，考虑到数据的大小关系，将其分为左右两个方向。其便利之处在于可以使得数据的搜索更有效率，类似于二分法提高数据查询的效率。其示意图如下: