数据结构
[TOC]
线性表
线性表定义:线性表即同类型元素构成的有序序列 线性表作用:用于存储有顺序关系的同类型元素 线性表分类:
-
数组:数组存储的数据是连续的,逻辑上相邻的元素在物理空间上也是连续的,数组是一段连续的内存空间,因此使用数组前需要预设其大小。 访问时间复杂度:O(1) 插入、删除时间复杂度:O(n) 查找时间复杂度:O(n)
-
链表:链表由节点组成,每个节点包含一个数据域和指针域,数据域用于存储数据,指针域用于存储后继结点的位置,因此链表在物理空间上是可以不连续的。 访问时间复杂度:O(n) 插入、删除时间复杂度:O(1) 查找时间复杂度:O(n)
-
队列:特殊的线性表,队列不支持随机访问,必须按照先进先出原则。 基于简单循环数组实现: 入队、出队时间复杂度:O(1) 基于动态循环数据实现: 入队、出队时间复杂度:O(1) 基于链表实现: 入队、出队时间复杂度:O(1)
- 栈:特殊的线性表,栈不支持随机访问,必须按照先进后出原则。 基于简单数组实现: 入栈、出栈时间复杂度:O(1) 基于动态数组实现: 数组头为栈顶: 入栈、出栈时间复杂度为O(n) 数组尾为栈顶 入栈、出栈时间复杂度为O(1) 基于链表实现: 入栈、出栈时间复杂度为O(1)