附：有序和无序

单独解释有序和无序数据结构

形象的比喻

假象一个场景：一个大操场，一万个学生，你是管理这些学生的老师。

无序结构：放羊式散养，但你要认识每个人（费脑子），有一个花名册

• 新增一个学生：记录下这个学生的名字，把学生丢进操场，爱去哪儿去哪儿，别跑了就行。
• 查找一个学生：根据学生的名字，你站在高处一眼把学生认出来。（或者，那一根线把学生的手和名单上的名字牵起来，查找时根据名字，牵线拉出来）

（此处画个图。。。）

有序结构：排好队，一个挨一个，你不用认识每个人，也无需要花名册

• 最前面插入一个学生：让 10000 个人挨个往后挪一个位置，空出最前面的位置，插入学生
• 中间插入一个学生：找位置加塞进去，后面每个学生都往后挪一个位置（5000 个人挨个往后挪）
• 最后面插入一个学生：比较简单，直接排队尾即可
• 查找学生：从第一名学生开始，挨个往后查找，直到找到为止

（此处画个图。。。）

Array 和 Object

抛开 ES6 的 Map 和 Set 不谈。其实 ES5 中数组和对象，就是有序和无序。

// 有序
const arr = [ /* 一万个学生 */ ]
arr.unshift('张三') // 最前面插入一位
arr.splice(4999, 0, '李四') // 中间插入一位
arr.push('王五') // 最后插入一位
arr.includes('xxx') // 查找一个学生

// 无序
const obj = {
    'zhangsan': true, // 光记录名字，其他信息没有，就随便用 true 代替了
    'lisi': true.
    // 一共一万个学生
}
obj['wangwu'] = true // 插入一个学生
'xxx' in obj // 查找一个学生

应用场景

虽然大家平常都用数组和对象，但对有序和无序的场景并不一定有考虑到。举一个 vnode 例子。

{ // tag attrs children 可以是无序的
    tag: 'div',
    attrs: { // id className style 可以是无序的
        id: 'div1',
        className: 'container'
        style: 'color: red;'
    },
    children: [ // children 必须是有序的！！！否则渲染就乱了！！！
        {
            tag: 'img',
            attrs: { src: 'xxx.png', alt: 'xxx' }
        },
        'hello',
        'world'
    ]
}

还有：栈和队列，必须是有序的，顺序不能乱。。。

总结

• 有序结构
  • 优点：组织有序，不混乱
  • 缺点：插入、查找太慢
• 无序结构
  • 优点：插入、查找很快
  • 缺点：无序

【思考】有没有一种数据结构能整合两者的优点呢？—— 二叉树，以及二叉树的其他变种（数据结构内容，不课程不讲）