数据结构基础（一）

​ 我作为一个移动端的开发，像数据结构、算法之类的只是平常看看，项目中很少用得到，但是面试却必不可少，也总感觉知道总比不知道强，所以开始从头走一下数据结构和算法相关的知识，数据结构和算法不分离，所以结合着屡一下这方的相关知识：

一、概念与内容

1、数据结构：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

根据结构分为：逻辑结构和存储结构

逻辑结构：图形结构、树形结构、线性结构、集合结构

存储结构：表、堆栈、队列、数组、树、二叉树、图

2、算法：（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法的研究内容：

空间复杂度：一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。 所以多注意一些计算过程的定义的临时变量 ，防止内存空间的消耗

时间复杂度：是指执行算法所需要的计算工作量，用O(n)表示;时间复杂度计算如下：

• 我们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。

  比如：T(n) = 100，此时时间复杂度为 O(1)。T(n) = n + 29，此时时间复杂度为 O(n)。
  

• 我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。 同时因为要求的精度不高，所以我们直接忽略低此项。

  比如：T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。
  

• 因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

  T(n) = 3n^3，此时时间复杂度为 O(n^3)。
  

如何把握这两者：

程序好坏=空间复杂度+时间复杂度+应用场景（更重要）；三者中应用场景还是最主要的

二、线性表之顺序存储结构

1、顺序表：常见 数组、Arraylist

优点：尾插效率高，支持随机访问

缺点：中间插入或者删除效率低

三、链表

1、单链表

2、单链表环

3、双链表

4、双链表环