通俗地说，数据结构是组织数据的一种方式。在逻辑上可以分为线性结构，散列结构，树形结构，图形结构。算法是求解具体问题（输入->输出）的步骤描述，代码上表现出来是解决特定问题的一组有限的指令序列。算法复杂度分为两个：时间复杂度和空间复杂度。复杂度并不是准确地去计算算法所花费的时间和空间，具体的花费取决于不同的底层实现，如编译器、指令集，常数项忽略不计后被计为大O记法。

在这一小节中，主要展开线性表-数组以及笔试面试中常见的问题。
学习数组后，可以与链表进行对比总结，因为C++中容器list和vector是由这两种数据结构实现的。vector的底层是内存可扩容的数组，而list的底层是双向链表。

数组的特性

  • 特点： 内存是连续的
  • 优点：
    • 下标访问（随机访问）时间复杂度是O(1)
    • 末尾位置增加删除元素的时间复杂度是O(1)，因为不涉及元素的移动
    • 访问元素前后相邻位置的元素非常方便，因为内存是连续的
  • 缺点：
    • 非末尾位置增加删除元素需要进行大量的数据移动，时间复杂度为O(n)
    • 搜索的时间复杂度
      • 无序数组 - 线性查找，时间复杂度为O(n)
      • 有序数组 - 二分查找，时间复杂度为O(logn)
    • 数组扩容消耗比较大