1.前言
由我看来数据结构是非常重要的。我们一定经常听到程序=数据结构 + 算法。
- 数据结构：计算存储、组织数据的方式，是指数据相互之间是以什么方式排列在一起的。
- 算法：通过执行一系列精确定义的步骤来解决问题或完成任务。
简单概述：
- 数据结构：存储数据
- 算法：处理数据
2.数据结构的分类
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图。它们可以从“逻辑结构”和“物理结构”两个维度进行分类。
2.1 逻辑结构
逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中，数据按照一定顺序排列，体现了数据之间的线性关系；而在树中，数据从顶部向下按层次排列，表现出“祖先”与“后代”之间的派生关系；图则由节点和边构成，反映了复杂的网络关系。
线性结构：
- 数据元素之间存在一对一的关系。
- 如数组、链表、栈、队列等。
树形结构：
- 数据元素之间存在一对多的关系。
- 如树、二叉树、红黑树、AVL树等。
图形结构：
- 数据元素之间存在多对多的关系。
- 如图、有向图、无向图等。
- 线性数据结构：数组、链表、栈、队列、哈希表，元素之间是一对一的顺序关系。
- 非线性数据结构：树、堆、图、哈希表。
非线性数据结构可以进一步划分为树形结构和网状结构。
- 树形结构：树、堆、哈希表，元素之间是一对多的关系。
- 网状结构：图，元素之间是多对多的关系。
2.2 物理结构
程序运行时，正在处理的数据主要存储在内存中。
- 硬盘用于长期存储大量数据
- 内存用于临时存储程序运行中正在处理的数据
- 缓存则用于存储经常访问的数据和指令
- 硬盘难以被内存取代。首先，内存中的数据在断电后会丢失，因此它不适合长期存储数据；其次，内存的成本是硬盘的几十倍，这使得它难以在消费者市场普及。
系统内部是通过内存地址来访问目标位置的数据。比如：堆就处于一块内存空间，我们new出来的对象都会存储在堆中，栈中的局部变量只是存有指向他们的地址值，然后通过这块内存地址来进行访问的。
物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，两种物理结构在时间效率和空间效率方面呈现出互补的特点。
物理结构在很大程度上决定了程序对内存和缓存的使用效率，进而影响算法程序的整体性能。
所有数据结构都是基于数组、链表或二者的组合实现的。
连续空间存储和分散空间存储对比
1. 连续空间存储
连续空间存储是指在存储介质上将数据存储在连续的物理位置上，数据块在存储时需要占据连续的存储空间。这种存储方式通常用于传统的文件系统和数据库系统中。
特点：
- 顺序存取：数据存储在物理上连续的存储块中，可以通过顺序访问来快速读取和写入数据。
- 简单管理：管理连续空间相对简单，文件系统可以通过维护一个位图或链表来管理空闲和已分配的存储块。
优点：
- 快速访问：可以通过索引计算存储的地址，适合顺序读取和随机访问。
- 简化碎片管理：减少了碎片化和存储管理的复杂性。提高内存空间的利用率。
- 元素紧密排列：不需要额外的空间来存储节点间的引用
- 快速访问：可以通过索引计算存储的地址，适合顺序读取和随机访问。
缺点：
- 动态扩展困难：难以动态扩展文件大小，需要移动数据。大小需要在编译时确定。
- 浪费：需要一次性分配足够的连续内存空间，这可能导致内存浪费。
2. 分散空间存储
分散空间存储是一种将数据分散存储在存储介质的不同物理位置上的方式，旨在提高数据存储的弹性和效率。这种方法通常用于分布式存储系统和对象存储系统中。
特点：
- 数据分片：数据被切分成多个部分（分片），每个分片存储在不同的物理位置上。
- 冗余备份：通常会在多个位置上存储数据的冗余备份，以增加数据的可靠性和容错性。
- 动态扩展：可以轻松地增加存储容量，无需移动数据。
优点：
- 高可用性：由于冗余备份和分布式存储，数据可靠性较高。
- 灵活性：以 "节点" 为单位进行动态内存分配和回收，提供了更大的灵活性。 大小可以在运行时动态确定。
缺点：
- 访问速度：由于数据分散存储在不同位置，可能会影响访问速度。
- 管理复杂性：需要复杂的数据分布和一致性管理。
- 内存碎片化：在程序运行时，随着反复申请与释放内存，空闲内存的碎片化程度会越来越高，从而导致内存的利用效率降低。
3. 应用场景比较
连续空间存储适合需要快速访问和操作的场景，如传统文件系统、数据库系统等，特别是对于大文件的顺序读写操作效果显著。
分散空间存储适合需要高可用性、可扩展性和冗余备份的场景，如云存储、分布式文件系统等，可以处理大规模数据和分布式计算的需求。
如果数据量非常大、动态性很高、顺序存储的预期大小难以估计，那么基于分散存储的实现更加合适。分散存储能够将大量数据分散存储于内存的不同部分，并且避免了内存不够产生的额外开销。
扩展：
缓存虽然在空间容量上远小于内存，但它比内存快得多，在程序执行速度上起着至关重要的作用。由于缓存的容量有限，只能存储一小部分频繁访问的数据，因此当 CPU 尝试访问的数据不在缓存中时，就会发生缓存未命中（cache miss），此时 CPU 不得不从速度较慢的内存中加载所需数据。因此，“缓存未命中”越少，CPU 读写数据的效率就越高。
缓存会采取以下数据加载机制。
- 缓存行：缓存不是单个字节地存储与加载数据，而是以缓存行为单位。相比于单个字节的传输，缓存行的传输形式更加高效。
- 预取机制：处理器会尝试预测数据访问模式（例如顺序访问、固定步长跳跃访问等），并根据特定模式将数据加载至缓存之中，从而提升命中率。
- 空间局部性：如果一个数据被访问，那么它附近的数据可能近期也会被访问。因此，缓存在加载某一数据时，也会加载其附近的数据，以提高命中率。
- 时间局部性：如果一个数据被访问，那么它在不久的将来很可能再次被访问。缓存利用这一原理，通过保留最近访问过的数据来提高命中率。
连续存储和分散存储对比：
- 占用空间：连续存储元素比分散存储元素占用空间更多，导致缓存中容纳的有效数据量更少。
- 缓存行：分散存储数据分散在内存各处，而缓存是“按行加载”的，因此加载到无效数据的比例更高。
- 预取机制：连续存储比分散存储的数据访问模式更具“可预测性”，即系统更容易猜出即将被加载的数据。
- 空间局部性：连续存储被存储在集中的内存空间中，因此被加载数据附近的数据更有可能即将被访问。
总体而言，数组具有更高的缓存命中率，因此它在操作效率上通常优于链表。这使得在解决算法问题时，基于数组实现的数据结构往往更受欢迎。
高缓存效率并不意味着数组在所有情况下都优于链表。实际应用中选择哪种数据结构，应根据具体需求来决定。
