本文源自本人的学习记录整理与理解，其中参考阅读了部分优秀的博客和书籍，尽量以通俗简单的语句转述。引用到的地方如有遗漏或未能一一列举原文出处还望见谅与指出，另文章内容如有不妥之处还望指教，万分感谢。
数据结构简单认识.png
线性表
-
线性表是具有n个相同类型元素的有限序列(n>=0)
结构图.png
- a1是首节点(首元素)，an是尾节点(尾元素)
- a1是a2的前驱，a2是a1上午后继
常见的线性表有：
- 数组
- 链表
- 栈
- 队列
- 哈希表(散列表)
数组(Array)
-
数组是一种顺序存储的线性表，所有元素的内存地址是连续的
NSArray *array = @[11,22,33];
内存图.png
- 在很多编程语言中，普通数组都有致命的缺点：无法动态修改容量
- 实际开发中，我们更希望数组的容量是可以动态改变的
动态数组(Dynamic Array)接口设计
-
intsize(); //元素的数量 -
booleanisEmpty(); //是否为空 -
booleancontains(E element); //是否包含某个元素 -
voidadd(E element); //添加元素到最后面 - E get(
intindex); //返回index位置对应的元素 - E set(
intindex, E element); //设置index位置的元素 -
voidadd(intindex, E element); //往index位置添加元素 - E remove(
intindex); //删除index位置对应的元素 -
intindexOf(E element); //查看元素的位置 -
voidclear(); //清除所有元素
image.png
动态数组明显缺点：
可能会造成内存空间的大量浪费，比如：很久都不一定会用到扩容后的空间
数组修改元素时间复杂度：O(1), 这个复杂度和下标无关；
数组查询元素时间复杂度：O(1), 这个复杂度和下标无关；
数组访问特点：
- 随机访问速度非常快
