跳到主要内容

基本的线性结构

线性结构的两种基本数据结构​

假设我们要从一些列的数字里面找到最大的那个，第一步需要考虑如何存储这些数字。

计算机内存存储有两种基本方式：

+------+------+------+------+------+------+
|  1   |  2   |  3   |  4   |  5   |  6   |
+------+------+------+------+------+------+

数组

+------+-+
|  1   | |
+------+++
        | +------+-+
        +->  2   | |
          +------+++
                  | +------+-+
                  +->   3  | |
                    +------+-+

链表

  • 数组：一次性开辟一大块连续内存，元素紧挨着放在一起。
  • 链表：每次都开辟需要的节点的内存，每个节点指向下一个节点

如上就是数据结构，它可能的操作和优缺点如下：

  • 访问：
    • 数组可以按索引快速访问
    • 链表只能遍历
  • 新增元素：
    • 数组可能需要进行扩容，复制
    • 链表新增一个新的节点，修改链表指针即可
  • 删除元素：
    • 数组需要将后面的元素都移动到前面
    • 删除一个节点，修改链表指针即可
  • 修改元素：访问到某个元素，然后修改即可

求最值​

求最值的