线性表(每个线性表上的数据最多只有前和后两个方向):数组,链表,队列,栈 非线性表(数据之间并不是简单的前后关系):二叉树,堆,图 数组的概念 数组( Array )是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。 数组的特点 连续的内存空间和相同类型的数据 数组的优点 随机访问:利用寻址公式对元素进行访问: a[i]_address = base_address + i * data_type_size 数组的查找操作时间复杂度不是O(1),即便是排好的数组,用二分查找,时间复杂度也是O(logn);正确的说法 数组支持随机访问,根据下标随机访问的时间复杂度为O(1) 数组的缺点 低效的插入和删除 插 …

单链表 data.next-->data.next-->NULL 时间复杂度 插入节点: 时间复杂度:O1 删除节点 时间复杂度:O1 查找节点 时间复杂度:O(n) 链表想要随机访问第K个元素arr[k],需要根据指针一个一个找 双向链表 -->prev.data.next<==>prev.data.next<==>prev.data.next 即支持两个方向,每个节点不知有一个后继指针next,还有一个前驱指针prev指向前面的结点 空间复杂度 双向链表需要额外的两个空间来存储后继结点和其前驱结点的地址.所以,如果存储同样多的数据,双向链表要比单链表占用更多的内存空间.虽然两个指针比较浪 …