最基础的数据结构-数组

数组的定义

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

名词解释

• 线性表

  数据排成像一条线一样的结构.每个线性表的数据最多只有前和后两个方向.除了数组,链表,栈,队列也是线性表结构.
  

• 连续的存储空间和相同类型的数据

  由于该特性使得数组的可以随机访问(按照下标查找元素).有利则有弊,插入和删除操作则需要搬移大量的元素.
  

数组的基本操作

• 插入数据 O(n)

  首先找到该元素,删除该元素并将该元素前面的所有元素向后移动.

• 删除数据 O(n)

  首先找到该元素,删除该元素并将该元素后面的所有元素向前移动.

• 修改数据 O(1)

  根据索引,找到对应的元素,修改该元素即可.

• 查找数据{按索引查找 O(1), 按元素值查找,需要遍历 O(n)}

  按元素来查找,可以通过二分查找来完成,O(logn).{前提是数组中的元素是有序的}

完整代码,戳此查看.

• Array 普通的数组
• OrderArray 可排序的数组