基本数据结构之数组

| 前端 | 数据结构 / 数组 | 8.5k | 14 分钟

基本数据结构之数组

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

优点:因为数据是连续存储的,内存地址连续,并且存储长度固定,所以在查找数据的时候效率比较高,比如假设数组首位元素的储存地址为100,每为元素的储存长度为2,则数组的第10位元素的储存地址为100 + (10-1) * 2, 在连续或无序访问的场景下有优势,读取的复杂度为O(1)

缺点:数组是一种连续的储存空间,并且在创建时就确定好了长度,无法动态扩容,只能储存同一种数据结构,需要在添加和删除时的复杂度为O(n),最糟糕的情况是在数组的头尾进行操作,此时需要同时移动后面的n位元素。因为数组长度不能修改,所以数组存在浪费内存空间或者数组越界的情形。

JavaScript中的数组

我们知道在 JavaScript 中,可以在数组中保存不同类型值,数组似乎也不存在长度限制,并且还可以当作栈(后进先出)和队列(先进先出)来使用。


// 队列(先进先出)
let queue = [1, "2", true] // 可以存储任意类型
// 进队,插在末尾
queue.push(4)
// 出队,弹出第一个
queue.shift()

// 栈(先进后出)
let stack = [1, "2", true]
// 压栈,插在末尾
stack.push(4)
// 弹栈,弹出最后一个
stcak.pop()

这表明JavaScript中的数组和上面介绍的数组有明显的区别,在JavaScript中有着一切皆对象的说法,[] instanceof Object 的运算结果为true, 数组也是一个特殊的对象,内部是以 key-value 形式存储数据,所以 JavaScript 中的数组可以存放不同类型的值, 并且Array内部也实现了动态扩容,Array的底层储存结构分为两种,FixedArray(快数组) 和 HashTable(慢数组)。

深入了解JavaScript的Array请参看从Chrome V8源码看JavaScript数组

JavaScript数组的常用方法示例

创建数组

除非你需要指定创建时的长度,否则推荐使用字面量的形式创建数组

// 使用new创建一个数组
const arr = new Array()

// 使用字面量创建
const arr = []

数组添加和移除元素

const arr = []
// 操作数组的尾部
// 向数组的末尾添加一个元素,数组的长度+1,方法返回加入的元素
arr.push(1)
// 数组的末尾弹出一个元素,数组的长度-1,方法返回弹出的元素
arr.pop()

// 操作数组的顶部
// 在数组的顶部添加一个元素,数组的长度+1,方法返回加入的元素
arr.unshift(1)
// 数组的顶部弹出一个元素,数组的长度-1,方法返回弹出的元素
arr.shift()

数组的索引查找和索引赋值

const arr = [1, 2]
// 使用元素的下标来进行读取,数组的下标是从0开始计算,下标0对应的是数组的第一个元素
const frist = arr[0] // frist 等于 1

// 根据数组的下标对数组进行赋值
arr[1] = 3 // arr 等于 [1, 3]

// 对数组的某项重复赋值会覆盖以前的值
arr[1] = 4 // arr 等于 [1, 4]

// 不要尝试用使用下标和.式调用读取数组的值,此时会语法错误
console.info(arr.'0') // 语法错误
console.info(arr.0) // 语法错误

// NOTE 数组也是一个特殊对象,因此还有下面这种赋值方式
// 注意这种方式的赋值并不会改变数组的length
arr.key = 5 // arr 等于[1, 4, key: 5]
const key = arr.key // key 等于 5
const key2 = arr['key'] // key 等于 5

// 对数组的下标赋值时,如果数组的下标超出数组的长度,会对数组进行扩容
arr[100] = 1 // arr.length = 101 在谷歌调试台打印会显示 [1, 4, empty × 98, 1, key: 5]

数组删除和索引插入元素

const arr = [1, 2, 3, 4]

// 使用数组的splice方法
// 删除数组的第三个元素, 数组的长度会改变
arr.splice(2, 1) // arr = [1, 2, 4]

// 在数组指定位置插入元素, 数组的长度会改变
arr.splice(1, 0, 10) // arr = [1, 10, 2, 4]

// delete根据下标删除元素,此时数组的长度不会改变,相当于对改下标赋值undefined
delete arr[0] //  arr = [empty, 10, 2, 4]

// 清空数组,采用splice
arr.splice(0, arr.length)

// 推荐
// JS数组的length属性不是只读的,是可写的, 通过对数组的length赋值0可以清空数组
arr.length = 0

// 不推荐的一种数组清空
// 这种方式只是修改了变量的引用,并没有清空原数组对象,假如该数组被其他的变量所引用,其内容不变
arr = []

数组的遍历

const arr = new Array(10).fill(1)

// for...in遍历,不推荐的一种遍历
// 此种遍历可能会遍历到arr上面的非索引属性 比如arr.key
// 性能最差
for (let index in arr) {
    console.info(index)
    console.info(arr[index])
}

// for...of遍历,性能略强于for...in
for(let value of (arr)) {
    console.info(value)
}

// 最经典的一种遍历方式,有时侯会取长度缓存,性能最好
for (let i = 0; i < arr.length; i++) {
    console.info(i)
    console.info(arr[i])
}

// Array.prototype.forEach
// 返回值为undefined
arr.forEach((item, index) => {
    console.info(item)
    console.info(index)
})

// Array.prototype.map
// 返回值为每次回调函数执行的返回值组成的新数组,原数组数据不变
arr.map((item, index) => {
    console.info(item)
    console.info(index)
    return item.id
})

数组的常用方法

// Array.of 这是一个静态方法
// 接收传入的参数组成一个数组
const arr = Array.of(1, true, '', null, undefined) // arr = [1, true, "", null, undefined]


// Array.from 这是一个静态方法
// 将可遍历对象(类数组、含有length属性的对象、Set、Map)转化为数组
// 第二个参数可以传入一个处理函数,第三个参数可以传入修改处理函数的上下文对象
const arr = Array.from({length: 3, "1": 2}) // arr =  [undefined, 2, undefined]
// [].slice.call(arguments)也可以转化类数组


// Array.isArray 这是一个静态方法
// 用来判断参数对象是否是一个数组
const isArray = Array.isArray([1]) // isArray = true


// Array.prototype.indexOf
// 传入第一个参数为查找对象,第二个可选参数为起始位置
// 当寻找到第一个相等时函数就会中断遍历返回索引,未存在该项时返回 -1
// 相等策略为全等
const index = [1, '1', { a: 1 }].indexOf({a: 1}) // index = -1
const index = [1, '1', { a: 1 }].indexOf('1') // index = 1


// Array.prototype.lastIndexOf
// 该函数和indexOf作用相同,indexOf从头开始遍历,lastIndexOf从尾部向前遍历
const index = [1, '1', true, '1', { a: 1 }].lastIndexOf('1') // index = 3


// Array.prototype.concat
// 函数接收传入的参数和调用的数组连接为一个新的数组返回,不会更改原数组对象
// 注意如果参数是数组时函数会扁平化(flat)一层数组
const arr = [].concat(1, [2, 3]) // arr = [1, 2, 3]
const arr = [].concat(1, [2, [3]]) // arr = [1, 2, Array(1)]


// Array.prototype.includes
// 传入第一个参数为检测对象,第二个可选参数为起始位置
// 当寻找到第一次相等时函数就会中断遍历返回true,未找到相等时函数返回false
// 全等匹配
const has = [1].includes(1) // has = true
const has = ['1'].includes(1) // has = false


// Array.prototype.findIndex
// 函数的第一个参数为一个predicate处理函数,第二个可选参数为处理函数的上下文
// 当处理函数第一次返回真时findIndex返回该处的索引,函数停止遍历
// findIndex和indeOf的区是一个是直接进行全等匹配,一个可以自己通过处理函数进行匹配
// 因此findIndex比indeOf的适用返回要广
const index = [{id: 1}].findIndex(item => item.id === 1)


// Array.prototype.find
// find和findIndex的区别只是findIndex是返回索引而find是返回索引对应的值
const arr = [{id: 1}]
const find = arr.find(item => item.id === 1) // find = {id: 1}
const find = arr[arr.findIndex(item => item.id === 1)] // find = {id: 1}


// Array.prototype.join
// 该方法接收一个字符串作为分隔符,将数组的每一项拼接起来
// 会调用对象的toString方法,null和undefined会被当作空字符串''
const ips = [
    null,
    undefined,
    {
        ip: '127.0.0.1',
        toString: function () {
            return this.ip
        }
    },
    {ip: '0.0.0.0'}
].join(';') // ";;127.0.0.1;[object Object]"


// Array.prototype.filter
// 第一个参数为一个predicate处理函数,第二个可选参数为处理函数的上下文
// 函数返回处理函数执行为真的选项集合
// 用于筛选特定数据
const sources = [{ title: '第一行' }, { title: '私密行', hide: true }]
const tableData = sources.filter(item => !item.hide) // tableData = [{ title: '第一行'}]


// Array.prototype.reduce
// 函数接收一个第一个参数为处理函数,第二个可选参数为初始累加值
// 函数遍历数组,调用处理函数使得每个数组值和累加值进行运算
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr.reduce((a, b) => a + b, 100) // 145

// TODO 这里可以连接到一个经典的reduce的使用场景,以后补充


// Array.prototype.reduceRight
// reduceRight从末尾向前遍历,reduce是从头开始开始遍历
const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr.reduceRight((a, b) => a + b, 100) // 145


// Array.prototype.every
// 第一个参数为一个predicate处理函数,第二个可选参数为处理函数的上下文
// 函数遍历所有数据,每个数据选项都调用处理函数,当所有处理函数返回真时函数返回真,否则返回false
// 用于检测数组是否全部满足条件
const formData = [{ field: 'name', value: '你好' }, { field: 'password', value: '' }]
const valid = formData.every(item => !!item.value) // valid = false


// Array.prototype.some
// 第一个参数为一个predicate处理函数,第二个可选参数为处理函数的上下文
// 当第一次处理函数返回为真,则函数中断遍历返回true,否则返回false
// 用于检测数组只要有一项数据符合某种逻辑
const grades = [{ course: 'English', grade: 90 }, { course: 'Geography', grade: 20 }]
const isGoodBoy = grades.some(item => item.grade >= 80) // isGoodBoy = true


// Array.prototype.keys
// 无参,返回一个索引集合的Iterator
// 注意[].keys和Object.keys([])不同
// Object.keys返回的是key的集合,[].keys返回的是key的集合的Iterator
const it = [{ a: 1 }, 2, 3, 4, 5].keys()
let item
while((item = it.next()) && !item.done) {
    console.info(item) // { value: 0, done: false }
}


// Array.prototype.values
// 无参,返回一个值集合的Iterator
const it = [{ a: 1 }, 2, 3, 4, 5].values()
let item
while((item = it.next()) && !item.done) {
    console.info(item) // { value: { a: 1 }, done: false }
}


// Array.prototype.entries
// 无参,返回一个包含值和索引集合的Iterator
// Iterator.next返回数据的value是一个数组,第一项是索引,第二项是数组选项值
const it = [{ a: 1 }, 2, 3, 4, 5].entries()
let item
while((item = it.next()) && !item.done) {
    console.info(item) // { value: [0, { a: 1 }], done: false }
}


// Array.prototype.reverse
// 无参,反向排列原数组数据, 注意此处是修改了原数组而不是生成一个副本,返回倒排后的数组
const arr = [1, 2, 3] // arr = [1, 2, 3]
arr.reverse() // arr = [3, 2, 1]


// Array.prototype.sort
// 函数接收一个参数为compareFn比较函数, 比较函数返回两个选项之间的差值
// sort会直接修改原数组,返回重新排列后的数组
// 返回值为正数,则表示a应该位于b的后面,返回值为负数,则表示a应该位于b的前面
// a - b 表示从小到大升序排, b - 1 表示从大到小降序排
const arr = [11, 2, 22, 1]
arr.sort((a, b) => a - b) // arr = [1, 2, 11, 22]
arr.sort((a, b) => b - a) // arr = [22, 11, 2, 1]

const arr = [true, false, true, false]
arr.sort((a, b) => a ? 1 : -1) // arr = [false, false, true, true]


// Array.prototype.slice
// 函数接收第一个可选参数为起始位置(省略表示全部),第二个可选参数为结束位置(省略表示到末尾为止)
// 函数浅拷贝数组的指定区间返回,不会修改原数组对象
const person = { name: 'goodBoy' }
const arr1 = [person, 2, undefined]
const arr2 = arr1.slice() // 默认全部复制
arr2.push(null) // 修改了arr2,arr1还是原来的值,表明不是同一个引用
person.name = 'emmmmm' // 修改数组里面的对象
console.info(arr1[0]) // { name: "emmmmm" }
console.info(arr2[0]) // { name: "emmmmm" } 对象的属性都变了说明执行复制的时候是浅拷贝

// Array.prototype.splice
// 函数接收第一个参数为起始位置,第二个参数为是否删除(1删除,0不删)
// 函数删除或者不删除目标位置数据,然后将其它的参数添加到起始位置之后,函数会直接修改的原数组
// 用于删除、替换、插入指定位置的数据,函数返回原数据对象的起始位置数据
const arr = [1, 2, 3, 4, 5]
arr.splice(1, 1) // arr = [1, 3, 4, 5]
arr.splice(0, 1, 1, 2) // arr = [1, 2, 3, 4, 5]
arr.splice(0, 0, 0) // arr = [0, 1, 2, 3, 4, 5]


// Array.prototype.flat
// 函数接收一个可选的数字参数,表示深度层级,参数缺省时默认为1
// 函数根据指定深度递归遍历数组中的数据,将其子数组内的数据和非数组数据一起添加到一个新的数组
// 返回的是新的一个数组集合,不修改原始数据
// 用于将嵌套的数组扁平化
const arr = [1, 2, [3, [4, [5]]]]
arr.flat() // [1, 2, 3, [4, [5]]]
arr.flat(2) // [1, 2, 3, 4, [5]]
arr.flat(Infinity) // [1, 2, 3, 4, 5]


// Array.prototype.flatMap
// 函数接收一个处理函数,和一个可选的处理函数上下文
// flatMap是flat和map的一个组合,函数会使数组扁平化一个层级
// 函数先将数组扁平化一级,然后再将扁平化后的数组遍历调用处理函数,将其返回值添加到一个新的数组返回
// 不会修改原数组对象,返回的是一个拷贝
const arr = [1, 2, [3, [4, [5]]]]
arr.flatMap(item => item) // [1, 2, 3, [4, [5]]]
arr.flatMap(() => {}) // [undefined, undefined, undefined]
// 👆注意处理函数无返回值时函数返回长度只有3, 所以flatMap是先map后再flat(1)


// Array.prototype.fill
// 函数接收第一个参数作为用于填充的数据,第二个可选参数为起始位置,第三个参数为结束位置
// 位置参数缺省表示全部填充,函数直接改变原数组对象
const arr = new Array(3).fill(1) // arr = [1, 1, 1]


// Array.prototype.copyWithin
// 函数接收第一个参数为开始覆盖的位置,覆盖的长度等于第二个参数和第三参数的差值
// 第二个参数为元素复制的起始位置,缺省时表示复制区间为第一个参数到数组的末尾
// 第三个参数为元素复制的结束位置,缺省时表示结束位置为末尾,为负数时表示相对起始位置倒数
// 函数会直接修改原数组
const arr = [1, 2, 3, 4, 5, 6, 7]
arr.copyWithin(1) // arr = [1, 1, 2, 3, 4, 5, 6]
// 👆第二个参数缺省等同于arr.copyWithin(1, 1, arr.length)
arr.copyWithin(4, 3, 4) // arr = [1, 1, 2, 3, 3, 5, 6]