Array

[TOC]

数组的基础特性

数组是一种线性表数据结构, 使用一组连续的内存空间, 来存储一组具有相同类型的数据.

数组属于线性表结构

  • 线性表
    • 每个线性表上的数据最多只有前后两个方向, 除了数组 , 链表/队列/栈 也是线性表结构
    • 相对应的, 二叉树/堆/图 等, 属于 非线性表, 在非线性表中, 数据之间并不是简单的前后关系

随机访问

数组的实现有以下两个限制:

* 连续的内存空间
* 相同类型的数据

正是因为这两个限制, 所以数组支持 随机存取. 但也正是因为这两个限制, 则也导致数组中在中间位置 删除 和 插入 数据变得相对低效, 因为为了保证是连续的内存空间, 所以在中间元素被删除时 需要将后面的全部元素向前搬一位.

关于 随机存取 一词的理解:

第一次看到这个词会感到非常疑惑, "什么? 数组还支持随机存取? 但是我通过下标访问数组难道不都是确定位置的存取吗?"

实际上 随机存取 这个词, 如果是在数组的视角下, 那么就非常的贴切了, 数组并不知道我们下一次会访问访问哪一个位置, 这个访问对他来说是随机的, 同时对于我们来说也是, 我们可以随意跳至我们想要去的位置.

与 随机存储 这个概念相对的是 顺序访问, 也就是需要一个一个遍历到我们想要的位置, 举个例子, 链表, 在链表中, 我们如果想要访问一个中间元素, 我们必须从链表的第一个节点一直遍历到那一个中间节点, 而无法直接访问到我们想要的那个中间节点.

那么为什么数组可以高效的随机访问数组元素呢?

我们回到数组的两个限制, 在第二个限制中, 要求数组中的元素都是相同的数据类型, 那么相同的数据类型, 也就意味着占用的内存空间相同, 那么这样, 我们就可以通过计算 需要访问的下标 和 元素的内存空间 得到偏移量, 然后将 数组内存块的首地址 加上 偏移量, 得到我们需要访问的元素的内存地址. 然后直接访问便可, 所以数组通过下标随机访问的时间复杂度是 O(1)

低效的 插入与删除

因为 连续内存空间的特性, 所以在向数组中间插入或删除时 , 需要保证空间的连续性, 所以需要将后面的元素全部前移一位或者后移一位, 这种操作最坏的时间复杂度是 O(n). 但是在某些特殊场景下, 对这种低效插入和低效删除有一定的优化空间.

低效插入

如果 当前数组只是被当做一个存储数据的集合, 这种情况下, 我们为了避免大规模的数据搬移, 可以将 k 位置的元素挪到数组的最后, 然后把元素插入到 k 的位置上.

低效删除

低效删除的应对方式是懒惰删除, 在底层实现时, 对于被删除的数组元素, 我们仅仅只是记录下该元素已经被删除, 而不是真正的删除和搬动数据. 等到合适的时机时, 例如 数组空间不够,或者达到阈值时, 再一次性进行删除, 这样就大大的减少了删除操作导致的数据搬移. JVM 的标记清除垃圾回收算法 和这个原理类似.

极客时间-数据结构与算法之美

很多时候我们并不是要去死记硬背某个数据结构或者算法, 而是要学习它背后的思想和处理技巧, 这些东西才是最有价值的.

数组越界

在 C 语言中, 数组越界是一种未决行为, 并没有规定数组访问越界时, 编译器应该如何处理, 并且 访问数组的本质就是访问一段连续内存. 而在 C语言中, 只要不是访问受限的内存, 理论上所有的内存空间都是可以只有访问的. 所以 只要数组通过偏移计算得到的内存地址是可用的, 那么 程序就可能不会报任何错误.

正因为如此, 很多计算机恶意程序 都是通过 数组越界的方式 非法访问内存地址的漏洞, 来攻击系统.

以上部分内容 在 "极客时间" - 数据结构于算法之美 的基础上进行再演绎和修改

Problem List

  • LeetCode
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
    • xxx.ProblemName
Copyright © Haoyu LIN 2017-2018 all right reserved,powered by Gitbook该文件修订时间: 2019-09-28 17:31:35

results matching ""

    No results matching ""