『嗨威说』数据结构 - 第二章学习内容小结
本文内容：
- 本章内容的小结
- 完成作业或实践时解决困难的经验分享
- 参考资料、说明推荐理由及列出相关链接(或书目名称，具体页码)
- 目前学习过程中存在的困难，待解决或待改进的问题
- 接下来的目标
一、本章内容小结：
（1）顺序表
顺序表一般表现为数组，使用一组地址连续的存储单元依次存储数据元素
(1)长度固定，必须在分配内存之前确定数组的长度，当然你可以使用vector容器来实现动态存储。
(2)存储空间连续，即允许元素的随机访问。
(3)存储密度大，内存中存储的全部是数据元素。
(4)要访问特定元素，可以使用索引访问，时间复杂度为o(1).
(5)要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为o(n).
注解：每次扩容的时候，都需要将旧的数据全部复制一份，会影响效率。不过实际上使用顺序表比链表的效率高。
（2）链表
表中的每个节点都保存有指向下一个节点的指针，所有节点串成一条链。根据指针的不同，还有单链表、双链表和循环链表的区分。
单链表是只包含指向下一个节点的指针，只能单向遍历。
双链表即包含指向下一个节点的指针，也包含指向前一个节点的指针，因此可以双向遍历。
由于链表是使用指针将节点连起来，因此无需使用连续的空间，它具有以下特点：
(1)长度不固定，可以任意增删。
(2)存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。
(3)存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。
(4)要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为o(n) 。
(5)在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为o(1)。
(6)双链表还允许在特定的数据元素之前插入或删除元素。
注解：链表的耗时大约是顺序表的 4倍左右。因为数组只需要很少的几次大块内存分配，而链表则需要很多次小块内存分配，内存分配操作相对是比较慢的，因而大大拖慢了链表的速度。这也是为什么会出现内存池。
二、完成作业或实践时解决困难的经验分享
推荐在博客园上关注一些技术大牛博主，游览他们的博文进行自学提升自我价值，多多百度或谷歌，可以在公众号上关注一些不错的技术分享者。
三、参考资料、说明推荐理由及列出相关链接(或书目名称，具体页码)：
推荐大佬博客：
https://www.cnblogs.com/roni-i/
https://www.cnblogs.com/alvinzh/category/993446.html
四、目前学习过程中存在的困难，待解决或待改进的问题
担任多重职位、多个社团、多个兼职，在平衡自己的课外时间和学习时间上存在问题，需要不断调整自我发展情况，退出一些已对自己无提升价值的社团。
关于课内的困难：这个学期的课本上的代码又很多都是伪代码，希望老师能够拿一种具体语言来操作加深我们对概念的理解。
五、接下来的目标：
（1）准备三月底的程序设计天梯赛，学习各类算法
（2）初步入门自然语言模型建立，帮助树蛙项目组完成数据流、模型的搭建。
（3）深入学习后期特效技术
上一篇： Springboot拦截器的使用