一、数据结构概念
1. 数据类型
（1）原子类型：其值不可再分的数据类型。
（2）结构类型：其值可以再分解成若干成分的数据类型。
（3）抽象数据类型：一个数学模型及定义在该数据模型上的一组操作。
2. 数据结构
数据结构是一组或多组存在特定关系的数据元素的集合。
（1）数据的逻辑结构
数据的逻辑结构分为线性结构和非线性结构。
集合：结构中的数据元素除了同属一个集合外，没有任何关系。
线性结构：结构中的数据元素只存在一对一的关系。
树形结构：结构中的数据元素存在一对多的关系。
网状结构：结构中的数据元素存在多对多的关系。
（2）数据的存储结构
存储结构是指数据结构在计算机中的表示（映像、物理结构），包括数据元素的表示和关系的表示。
顺序存储：把逻辑上相邻的元素放在物理位置也相邻的存储单元中，元素的关系可以由存储单元的邻接关系来体现，如数组。
优点：可以通过索引直接访问任何位置的元素，不需要从头遍历，且每个元素占用最少的存储空间，不会有指针或链接信息占用额外空间。
缺点：只能使用相邻的一整块空间，会产生外部碎片。
链式存储：存储元素时借助指示元素位置的指针来表示元素之间的逻辑关系，不需要存储单元物理位置相邻，如List。
优点：充分利用所有存储单元，不会出现碎片。
缺点：每个元素存储指针占用额外空间，且必须顺序存取。
索引存储：在存储元素时附加索引表，索引项形式为 [关键字，地址]，常用于数据库或文件系统。
优点：检索速度快。
缺点：索引表占用额外空间，增删数据需要额外花时间修改索引表。
散列存储：根据元素的关键词找出元素的存储地址（哈希存储），如哈希表。
优点：增删查操作快。
缺点：哈希表占用额外的空间，有可能需要花时间处理哈希冲突。
二、算法
1. 算法特征
（1）有穷性：算法总在执行有穷步之后结束，每一步都在有穷时间内完成。
（2）确定性：算法每条指令有确切的含义，对于相同的输入只能得出相同的输出。
（3）可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次实现。
（4）输入：算法有零个或多个输入。
（5）输出：算法有零个或多个输出。
2. 算法效率的度量
（1）时间复杂度：算法中基本运算的执行次数的数量级作为该算法的时间复杂度。
时间复杂度表示算法执行所需的时间，它描述了算法的运行时间与输入数据规模之间的关系。时间复杂度通常用大O表示法（Big O notation）来表示，形式为O(f(n))，其中f(n)是输入数据规模n的函数。
常见的时间复杂度：
O(1)：常数时间复杂度，表示算法的执行时间与输入数据规模无关。
O(n)：线性时间复杂度，表示算法的执行时间与输入数据规模成正比。
O(n^2)：平方时间复杂度，表示算法的执行时间与输入数据规模的平方成正比。
O(log n)：对数时间复杂度，表示算法的执行时间与输入数据规模的对数成正比。
O(n log n)：线性对数时间复杂度，表示算法的执行时间与输入数据规模乘以其对数成正比。
（2）空间复杂度：该算法所需的存储空间。
空间复杂度表示算法执行所需的内存空间，它描述了算法的存储空间与输入数据规模之间的关系。空间复杂度也通常用大O表示法来表示，形式为O(f(n))，其中f(n)是输入数据规模n的函数。
常见的空间复杂度：
O(1)：常数空间复杂度，表示算法的存储空间与输入数据规模无关。
O(n)：线性空间复杂度，表示算法的存储空间与输入数据规模成正比。
O(n^2)：平方空间复杂度，表示算法的存储空间与输入数据规模的平方成正比
