1.顺序结构 - 可扩容的数组
1)底层实现: 数组
2)特点:
a.按照顺序排列,每个元素都带有标号
b.除了有标号是连续的,内存中的物理空间也是连续的
3)优缺点:
优点: 查询速度快(因为有连续的下标,可以根据下标进行查询)
缺点:
a.插入/删除速度慢(插入/删除都是要移动元素的,所以元素一多就会执行效率慢)
b.内存的物理空间是连续的,利用不到碎片空间
2.链式结构
1)底层实现:节点(data(存储数据) + next(下一个节点的引用))
2)特点:
a.链表是内存中固定顺序,但是他的物理空间不连续
b.没有下标,并且从头节点开始
c.所有节点的访问,都必须通过头节点
d.head(头节点): 只存next,不存data
e.head.next = null -> 空链表
3)不同的链表:
a.单向链表
特点: 只有头节点,只能从头节点出发
b.双向链表(最常用)
特点: 有头节点和尾节点,所以可以从头节点出发也可以从尾节点出发
头节点: 不存元素,只有next
尾节点: 不存元素,只有pre
c.循环链表
特点: 尾节点指向头节点
可以从任意位置开始,都可以找到想要的元素
4)优缺点:
优点:
a.插入/删除效率高
b.不需要连续的内存物理空间,所以空间利用率高
缺点:
查询效率低,只能从头节点出发开始查询
3.栈
1).底层实现: 可以基于链表或数组
2).特点: 先进后出(后进先出)
3).特有方法:
push() - 压栈(往里加)
pop() - 弹栈(往外取)
4.队列
1).底层实现: 以基于链表或数组
2).特点: 先进先出(后进后出)
线性结构: 数据元素之间存在一对一的关系
顺序结构 + 链式结构 + 队列 + 栈 -> 线性结构
