数据结构系列一：初识集合框架+复杂度

前言

数据结构——是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是计算机专业的基础课程，但也是一门不太容易学好的课，它当中有很多费脑子的东西，之后在学习时，你若碰到了困惑或不解的地方 都是很正常的反应，就像你想乘飞机去旅行，在飞机场晚点几个钟头，上了飞机后又颠簸恐慌了一把一样，别大惊小怪，都很平常，只要能安全到这就是成功。——封清扬《大话数据结构》

---

---

一、如何学好数据结构+前置知识

从数据结构开始，代码量会变多，逻辑性会变强，还是需要有语法的基础的，数据结构是一门可以拉开差距的学科，这部分在面试、笔试、和工作中应用的非常多！
那么，我们如何学好数据结构呢？

• 多画图
• 多思考
• 多调试
• 多写代码

学习数据结构的前置知识：泛型、包装类
Java中集合类的背后就是数据结构。集合类有很多，所以把这些集合类有些书上叫：集合框架，集合框架里面会有很多的集合类，每一个集合类背后又是一个数据结构。
为什么会有这么多种数据结构？
一个集合类描述和组织数据的方式是不一样的，数据结构就是数据+结构，结构：描述或组织一些数据

• 从学习的角度来看，我们先学背后的数据结构，然后学对应的集合类，最后学集合框架，这样一个顺序，掌握的效果会更好

二、集合框架

（1）了解集合框架

Java集合框架Java Collection Framework，又被称为容器container，是定义在java.util包下的一组接口和其实现的类
其主要表现为将多个元素element置于一个单元中，用于对这些元素进行快速、便捷的存储、检索、管理，即平时我们俗称的增删改查CRUD
例如：一副扑克牌（一组牌的组合）、一个邮箱（一组邮件的集合）、一个通讯录（一组姓名和电话的映射关系）等等

内部关系：接口extends接口、类implements接口

（2）集合框架的重要性

• 成熟的使用集合框架，有助于我们便捷、快速的写出高效、稳定的代码
• 学习背后的数据结构知识，有助于我们理解各个集合的优缺点及应用场景

（3）背后所涉及的数据结构以及算法

1.什么是数据结构

数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合

2.容器背后的数据结构

该阶段，我们主要学习一下容器，每个容器其实都是对某种特定数据结构的封装

1. Collection：是一个接口，包含了大部分容器常用的一些方法

2. List：是一个接口，规范了ArrayList和LinkedList中要实现的方法

   • ArrayList：实现了List接口，底层为动态类型顺序表
   • LinkedList：实现了List接口，底层为双向链表

3. Stack：底层是栈，栈是一种特殊的顺序表

4. Queue：底层是队列，队列是一种特殊的顺序表

5. Deque：是一个接口

6. Set：集合，是一个接口，里面放置的是K模型

   • HashSet：底层为哈希桶
   • TreeSet：底层为红黑树

7. Map：映射，里面存储的是K-V模型的键值对

   • HashMap：底层为哈希桶
   • TreeMap：底层为红黑树

三、时间和空间复杂度

（1）算法效率

算法效率分析分为两种：第一种是时间效率，第二种是空间效率，时间效率被称为时间复杂度，二空间效率被称为空间负责度，时间负责度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间

（2）时间复杂度

1.时间复杂度的概念

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间，一个算法执行所消耗的时间，从理论上来说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道，但是我们需要每个算法都上机测试吗？是都可以上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式，一个算法所花费的时间与其中语句的执行次数成正比，算法中的基本操作的执行次数，为算法的时间复杂度

2.大O阶方法的推导

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除这个项目相乘的常数，得到的结果就是大O阶

通过上面我们会发现大O阶的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数
两个算法如果比较复杂度时，一般比较最坏情况下

（3）空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数，空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法