【面试复习】【数据结构】----数组和链表
数组
访问数组元素为O(1),插入和删除均为O(n)
查找不为O(1),数组的正确表述是数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)
特点:
一组连续的内存空间,存储相同类型的数据
根据下标寻找元素,使用内存地址访问
a[i]_address = base_address + i * data_type_size
链表
访问链表元素为O(n),插入和删除均为O(1)
插入和删除操作比较多,就用链表
特点:
不需要连续内存空间,可以用指针把零散内存块串联起来,不知道要插入多少数据时,用链表就好
- 单链表:单个方向,只有next指针,插入删除O(1),访问元素O(N)
- 循环链表:特殊的单链表,尾结点指向头结点,处理环形结构问题,约瑟夫问题
- 双向链表:有前驱和后继指针,需要更多内存空间,但提供操作灵活性
只有当找到了要删除或插入的结点,双向链表的删除和插入操作才是O(1),单向链表为O(N),
要不然遍历查找那个结点比较耗时,所以它们的复杂度都为O(n)
双向链表的好处:空间换时间,费内存但省时间
-
CPU缓存友好性:
数组可以借助CPU缓存机制,预读数组中的数据,提高访问效率,[^1]
链表在内存中不是连续存储,对CPU缓存不友好,无法有效预读 -
内存大小限制:
数组的大小固定了,声明的数组过大过小都会导致内存问题,而且扩容时,需要拷贝原数组,非常费时
链表没有大小限制,天然支持动态扩容