JavaScript 数据结构与算法

• 掌握 JS 内置的数据结构及背后的工作原理
• 依据内置数据结构自定义创建其他数据结构（链表、堆栈、队列、二叉搜索树、有限队列、堆、图形等）
• 理解不同数据结构的存在意义及背后工作原理
• 学会比较不同数据结构在进行操作的时间复杂度
• 掌握分析数据结构，优化数据结构的思考方式及实现过程
• 学会分析在开发环境中对数据结构的选择

基础知识

lesson-1: 什么是数据结构&为什么需要数据结构

数据结构是计算机存储、组织数据的方式，允许我们管理数据

不同的场景需要不同的数据结构

• 有序列表数据允许重复——Array
• 无序列表数据不允许重复——Set
• 无序数据键值对形式——Object
• 有序键值对可遍历数据——Map

lesson-2: 数组

• 保留插入顺序
• 通过索引访问元素
• 可遍历（for 循环）
• 大小（长度）动态调整
• 允许重复
• 删除和查找元素比较耗费性能

const names = ['Summer', 'Henry', 'Lucy', 'Summer']

// 索引值从0开始
console.log(names[1])
console.log(names.length)

// for循环遍历
for (const name of names) {
  console.log(name)
}

// 添加元素
names.push('Lucy')
console.log(names.length)

// 查询元素
const lucyIndex = names.findIndex((name) => name === 'Lucy')
console.log(lucyIndex)

// 删除元素
names.splice(2, 1)
console.log(names)

lesson-3: 集合

• 无序（存储和读取顺序可能不一样）
• 通过方法访问和获取元素
• 可遍历（for 循坏）
• 大小（长度）动态调整
• 不允许重复（要求元素唯一）
• 删除和查找元素简单快捷

const ids = new Set()

// 添加元素
ids.add('a')
ids.add(1)
ids.add('b')
ids.add(1)
// Set(3) {'a', 1, 'b'}

// 集合遍历元素
for (const id of ids) {
  console.log(id)
}

// 集合访问元素
console.log(ids.has('a')) // true

// 集合删除元素
ids.delete('b')
console.log(ids) // Set(2) {'a', 1}
console.log(ids[0]) // undefined

lesson-4: 数组 VS 集合

数组

• 总是使用数组
• 如果强调排序和元素重复，则必须使用

集合

• 仅在顺序无关紧要且仅要求唯一值时可用
• 与数组相比，可以简化数据访问（例如查找，删除）

lesson-5: 对象

• 无序的键值对数据
• 通过键（属性）访问元素
• 不可遍历（除了 for-in 循环）
• 键是唯一的，值不是
• 键必须是字符串，数字或符号
• 可以存储数据和 “函数”（方法）

const person = {
  name: 'John',
  age: 33,
  hobbies: ['Sports', 'Music'],
  greeting() {
    console.log('Hello, I am ' + this.name)
  },
}

console.log(person[0]) // undefined
console.log(person['name'])
console.log(person.name)

// 添加属性
person.sex = 'male'
// 删除属性
delete person.age
console.log(person)

// 有方法，添加功能
person.greeting()

lesson-6: 映射

• 有序的键值对数据
• 通过键访问元素
• 可遍历（使用 for 循环）
• 键是唯一的，值不是
• 键可是各种类型的值（包括对象、数组）
• 纯数据存储，针对数据访问进行了优化

const resultData = new Map()

// 添加键值对 set
resultData.set('average', 1.6)
resultData.set('lastResult', null)

const person = { name: 'John', age: 34 }

resultData.set(person, 1.24)

// for循环
for (const el of resultData) {
  console.log(el)
}

// key相同情况
resultData.set('average', 23)

// 获取或者访问值
console.log(resultData.get('lastResult'))
console.log(resultData.lastResult) //undefined

// 删除
console.log(resultData.delete('average'))

// 删除key为对象的时候
resultData.delete({ name: 'John', age: 34 })

console.log(resultData)

lesson-7: 对象&映射

对象

• 非常通用的构造和数据存储结构
• 如果添加额外的功能则必须使用

映射

• 专注于数据存储
• 与对象相比，可以简化数据访问

lesson-8: 弱映射&弱集合

集合和映射的变体 → 值和键仅 “弱引用” → 如果未在应用程序的其他任何地方使用，垃圾回收则可以删除值和键

lesson-9: 自定义数据结构-链表

每一个元素都知道下一个元素

可以有效地调整大小并在列表的开头和结尾插入

链表

lesson-10: 链表构造函数 & append 方法

class LinkedList {
  constructor() {
    this.head = null // 链表中第一个节点
    this.tail = null // 链表中最后一个节点
  }

  // append 追加节点(末尾添加)
  append(value) {
    const newNode = { value: value, next: null }
    if (this.tail) {
      this.tail.next = newNode
    }
    this.tail = newNode
    if (!this.head) {
      this.head = newNode
    }
  }
}

const linkedList1 = new LinkedList()

lesson-11: 创建输出链表的方法

// 以数组方式输出节点
toArray() {
  const elements = []
  let curNode = this.head
  while (curNode) {
    elements.push(curNode)
    curNode = curNode.next
  }
  return elements
}

lesson-12: prepend 方法

// prepend 前置节点（头部添加）
prepend(value) {
  const newNode = { value: value, next: this.head }
  this.head = newNode
  if (!this.tail) {
    this.tail = newNode
  }
}

lesson-13: delete 方法

// delete 删除节点
delete(value) {
  if (!this.head) {
    return
  }
  while (this.head && this.head.value === value) {
    this.head = this.head.next
  }
  let curNode = this.head
  while (curNode.next) {
    if (curNode.next.value === value) {
      curNode.next = curNode.next.next
    } else {
      curNode = curNode.next
    }
  }
  if (this.tail.value === value) {
    this.tail = curNode
  }
}

lesson-14: find & insertAfter 方法

// find 节点查询
find(value) {
  if (!this.head) {
    return null
  }

  let curNode = this.head
  while (curNode) {
    if (curNode.value === value) {
      return curNode
    }
    curNode = curNode.next
  }
  return null
}

// insertAfter 某个节点后面插入
insertAfter(value, afterValue) {
  const existingNode = this.find(afterValue)
  if (existingNode) {
    const newNode = { value: value, next: existingNode.next }
    existingNode.next = newNode
  }
}

总结

class LinkedList {
  constructor() {
    this.head = null // 链表中第一个节点
    this.tail = null // 链表中最后一个节点
  }

  // append 追加节点(末尾添加)
  append(value) {
    const newNode = { value: value, next: null }
    if (this.tail) {
      this.tail.next = newNode
    }
    this.tail = newNode
    if (!this.head) {
      this.head = newNode
    }
  }

  // prepend 前置节点（头部添加）
  prepend(value) {
    const newNode = { value: value, next: this.head }
    this.head = newNode
    if (!this.tail) {
      this.tail = newNode
    }
  }

  // find 节点查询
  find(value) {
    if (!this.head) {
      return null
    }

    let curNode = this.head
    while (curNode) {
      if (curNode.value === value) {
        return curNode
      }
      curNode = curNode.next
    }
    return null
  }

  // insertAfter 某个节点后面插入
  insertAfter(value, afterValue) {
    const existingNode = this.find(afterValue)
    if (existingNode) {
      const newNode = { value: value, next: existingNode.next }
      existingNode.next = newNode
    }
  }

  // delete 删除节点
  delete(value) {
    if (!this.head) {
      return
    }
    while (this.head && this.head.value === value) {
      this.head = this.head.next
    }
    let curNode = this.head
    while (curNode.next) {
      if (curNode.next.value === value) {
        curNode.next = curNode.next.next
      } else {
        curNode = curNode.next
      }
    }
    if (this.tail.value === value) {
      this.tail = curNode
    }
  }

  // 以数组方式输出节点
  toArray() {
    const elements = []
    let curNode = this.head
    while (curNode) {
      elements.push(curNode)
      curNode = curNode.next
    }
    return elements
  }
}

const linkedList1 = new LinkedList()

linkedList1.append(1)
linkedList1.append('Summer')
linkedList1.append('Summer')
linkedList1.append('Hello')
linkedList1.append(5)
linkedList1.append(true)
linkedList1.prepend('第一个元素')
linkedList1.prepend('第一个元素')

console.log(linkedList1.toArray())

linkedList1.delete('Summer')
linkedList1.delete('第一个元素')
linkedList1.delete(5)

console.log(linkedList1.toArray())
console.log(linkedList1.find('Summer'))
console.log(linkedList1.find(true))

lesson-15: 为什么需要链表

历史上（对于其他编程语言），主要原因是内存管理：不必事先指定（占用）的大小

如今，JavaScript 具有动态数组（内置动态调整大小），而内存并不是 JavaScript 应用程序中的主要问题

如果在列表的开头进行高频插入操作，那链表会很有用——链表比数组操作更快

leeson-16: 衡量性能（时间复杂度——大 O 符号）

表示代码执行时间的增长变化趋势

lesson-17: 链表时间复杂度 & 数组

列表和表格

什么是列表和表格数据结构

栈 & 队列

哈希表

lesson-18: 什么是“列表和表格结构”

列表（Lists）——值的集合，例如：数组，集合，链表；适合存储通过位置（通过索引或搜索）检索的值，也适合循环

表格（Tables）——键值对的集合，例如：对象，映射；适合存储通过键检索的值，不关注循环

lesson-19: 内置表格和列表

// 列表结构——数组
const shoppingList = ['Apple', 'Banana', 'Orange']

const thirdItem = shoppingList[2]

for (const item of shoppingList) {
  // 得到每一项采购的水果名称
}

// 表格结构——对象
const citizens = {
  123: {
    name: 'summer',
    age: 26,
    sex: 'female',
    address: 'xxxx',
    birthdate: 'xxx',
  },
  456: {},
}

const summerData = citizens['123'] // ==> summer相关的信息

堆栈

lesson-20: 列表——堆栈（Stack）

简化的数组，后进先出（Last In First Out，LIFO）

lesson-21: 自定义堆栈结构（数组）

class Stack {
  constructor() {
    this.items = []
  }

  push(value) {
    this.items.push(value)
  }

  pop() {
    return this.items.pop()
  }

  isEmpty() {
    return this.items.length === 0
  }

  toArray() {
    return this.items.slice()
  }
}

const stack = new Stack()

stack.push('关冰箱门！')
stack.push('推入大象')
stack.push('开冰箱门！')

console.log(stack.toArray())

console.log(stack.pop())
console.log(stack.toArray())
console.log(stack.pop())
console.log(stack.toArray())
console.log(stack.pop())
console.log(stack.toArray())

lesson-22: 自定义堆栈结构（链表）

import { LinkedList } from './linked-list.js'

class Stack {
  constructor() {
    this.list = new LinkedList()
  }

  push(value) {
    this.list.prepend(value)
  }

  pop() {
    return this.list.deleteHead()
  }

  isEmpty() {
    return !this.list.head
  }

  toArray() {
    return this.list.toArray()
  }
}

// linked-list.js
export class LinkedList {
  constructor() {
    this.head = null // 链表中第一个节点
    this.tail = null // 链表中最后一个节点
  }

  // append 追加节点(末尾添加)
  append(value) {
    const newNode = { value: value, next: null }
    if (this.tail) {
      this.tail.next = newNode
    }
    this.tail = newNode
    if (!this.head) {
      this.head = newNode
    }
  }

  // prepend 前置节点（头部添加）
  prepend(value) {
    const newNode = { value: value, next: this.head }
    this.head = newNode
    if (!this.tail) {
      this.tail = newNode
    }
  }

  // find 节点查询
  find(value) {
    if (!this.head) {
      return null
    }

    let curNode = this.head
    while (curNode) {
      if (curNode.value === value) {
        return curNode
      }
      curNode = curNode.next
    }
    return null
  }

  // insertAfter 某个节点后面插入
  insertAfter(value, afterValue) {
    const existingNode = this.find(afterValue)
    if (existingNode) {
      const newNode = { value: value, next: existingNode.next }
      existingNode.next = newNode
    }
  }

  // delete 删除节点
  delete(value) {
    if (!this.head) {
      return
    }
    while (this.head && this.head.value === value) {
      this.head = this.head.next
    }
    let curNode = this.head
    while (curNode.next) {
      if (curNode.next.value === value) {
        curNode.next = curNode.next.next
      } else {
        curNode = curNode.next
      }
    }
    if (this.tail.value === value) {
      this.tail = curNode
    }
  }

  // 删除头部节点
  deleteHead() {
    if (!this.head) {
      return null
    }
    const deleteHead = this.head
    if (this.head.next) {
      this.head = this.head.next
    } else {
      this.head = null
      this.tail = null
    }

    return deleteHead
  }

  // 以数组方式输出节点
  toArray() {
    const elements = []
    let curNode = this.head
    while (curNode) {
      elements.push(curNode)
      curNode = curNode.next
    }
    return elements
  }
}

lessson-23: 堆栈时间复杂度 & 数组

队列

简化的数组，先进先出（First In First Out，FIFO）

lesson-24: 自定义队列结构（数组实现）

class Queue {
  constructor() {
    this.items = []
  }

  enqueue(value) {
    this.items.unshift(value)
  }

  dequeue() {
    return this.items.pop()
  }

  isEmpty() {
    return this.items.length === 0
  }

  toArray() {
    return this.items.slice()
  }
}

const queue = new Queue()

queue.enqueue('第1号')
queue.enqueue('第2号')
queue.enqueue('第3号')

console.log(queue.toArray())

console.log(queue.dequeue())
console.log(queue.toArray())
console.log(queue.dequeue())
console.log(queue.toArray())
console.log(queue.dequeue())
console.log(queue.toArray())

lesson-25: 自定义队列结构（链表实现）

import { LinkedList } from './linked-list.js'

class Queue {
  constructor() {
    this.list = new LinkedList()
  }

  enqueue(value) {
    this.list.append(value)
  }

  dequeue() {
    return this.list.deleteHead()
  }

  isEmpty() {
    return !this.list.head
  }

  toArray() {
    return this.list.toArray()
  }
}

// linked - list.js
export class LinkedList {
  constructor() {
    this.head = null // 链表中第一个节点
    this.tail = null // 链表中最后一个节点
  }

  // append 追加节点(末尾添加)
  append(value) {
    const newNode = { value: value, next: null }
    if (this.tail) {
      this.tail.next = newNode
    }
    this.tail = newNode
    if (!this.head) {
      this.head = newNode
    }
  }

  // prepend 前置节点（头部添加）
  prepend(value) {
    const newNode = { value: value, next: this.head }
    this.head = newNode
    if (!this.tail) {
      this.tail = newNode
    }
  }

  // find 节点查询
  find(value) {
    if (!this.head) {
      return null
    }

    let curNode = this.head
    while (curNode) {
      if (curNode.value === value) {
        return curNode
      }
      curNode = curNode.next
    }
    return null
  }

  // insertAfter 某个节点后面插入
  insertAfter(value, afterValue) {
    const existingNode = this.find(afterValue)
    if (existingNode) {
      const newNode = { value: value, next: existingNode.next }
      existingNode.next = newNode
    }
  }

  // delete 删除节点
  delete(value) {
    if (!this.head) {
      return
    }
    while (this.head && this.head.value === value) {
      this.head = this.head.next
    }
    let curNode = this.head
    while (curNode.next) {
      if (curNode.next.value === value) {
        curNode.next = curNode.next.next
      } else {
        curNode = curNode.next
      }
    }
    if (this.tail.value === value) {
      this.tail = curNode
    }
  }

  // 删除头部节点
  deleteHead() {
    if (!this.head) {
      return null
    }
    const deleteHead = this.head
    if (this.head.next) {
      this.head = this.head.next
    } else {
      this.head = null
      this.tail = null
    }

    return deleteHead
  }

  // 以数组方式输出节点
  toArray() {
    const elements = []
    let curNode = this.head
    while (curNode) {
      elements.push(curNode)
      curNode = curNode.next
    }
    return elements
  }
}

lesson-26: 队列时间复杂度 & 数组