# 数据结构介绍

数组：Array
堆栈：Stack
队列：Queue
链表：Linked Lists
树：Trees
图：Graphs
字典树：Trie
散列表（哈希表）：Hash Tables

我们可以先大体感知一下各种数据结构之间的关系：

栈和队列是类似数组的结构，非常多的初级题目要求用数组实现栈和队列，它们在插入和删除的方式上和数组有所差异，但是实现还是非常简单的；
链表、树和图这种数据结构的特点是，其节点需要引用其他节点，因此在增/删时，需要注意对相关前驱和后继节点的影响；
可以从堆栈和队列出发，构建出链表；
树和图最为复杂，但它们本质上扩展了链表的概念；
散列表的关键是理解散列函数，明白依赖散列函数实现保存和定位数据的过程；
直观上认为，链表适合记录和存储数据；哈希表和字典树在检索数据以及搜索方面有更大的应用场景。

# 堆栈和队列

栈和队列是一种操作受限的线性结构，它们非常简单，虽然 JavaScript 并没有原生内置这样的数据结构，但是我们可以轻松地模拟出来

栈的实现，后进先出 LIFO（Last in、First out）：

class Stack {
  constructor(...args) {
  	 // 使用数组进行模拟
    this.stack = [...args]
  }
  push(...items) {
  	 // 入栈
    return this.stack.push(... items)
  }
  pop() {
  	// 出栈，从数组尾部弹出一项
    return this.stack.pop()
  }
  peek() {
    return this.isEmpty() 
        ? undefined
        : this.stack[this.size() - 1]
  }
  isEmpty() {
    return this.size() == 0
  }
  size() {
    return this.stack.length
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

队列的实现，先进先出 FIFO（First in、First out），“比葫芦画瓢”即可：

class Queue {
  constructor(...args) {
  	 // 使用数组进行模拟
    this.queue = [...args]
  }
  enqueue(...items) {
    // 入队
    return this.queue.push(... items)
  }
  dequeue() {
    // 出队
    return this.queue.shift()
  }
  front() { 
    return this.isEmpty()
        ? undefined
        : this.queue[0]
  }
  back() {
    return this.isEmpty()
        ? undefined
        : this.queue[this.size() - 1]
  }
  isEmpty() {
    return this.size() == 0
  }
  size() {
    return this.queue.length
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

我们可以看到不管是栈还是队列，都是用数组进行模拟的。数组是最基本的数据结构，但是它的价值是惊人的。

# 链表（单向链表和双向链表）

堆栈和队列都可以利用数组实现，链表和数组一样，也实现了按照一定的顺序存储元素，不同的地方在于链表不能像数组一样通过下标访问，而是每一个元素都能够通过“指针”指向下一个元素。我们可以直观地得出结论：链表不需要一段连续的存储空间，“指向下一个元素”的方式能够更大限度地利用内存。

根据上述内容，我们可以总结出链表的优点在于：

链表的插入和删除操作的时间复杂度是常数级的，我们只需要改变相关节点的指针指向即可；
链表可以像数组一样顺序访问，查找元素的时间复杂度是线性的。

要想实现链表，我们需要先对链表进行分类，常见的有单链表和双向链表。

单链表：单链表是维护一系列节点的数据结构，其特点是：每个节点包含了数据，同时包含指向链表中下一个节点的指针。
双向链表：不同于单链表，双向链表特点：每个节点分支除了包含其数据以外，还包含了分别指向其前驱和后继节点的指针。

根据双向链表的特点，我们实现一个节点构造函数（节点类），如下代码：

class Node {
    constructor(data) {
        // data 为当前节点储存的数据
        this.data = data
        // next 指向下一个节点
        this.next = null
        // prev 指向前一个节点
        this.prev = null
    }
}

@前端进阶之旅: 代码已经复制到剪贴板

有了节点类，我们来初步实现双向链表类，如下代码：

class DoublyLinkedList {
    constructor() {
        // 双向链表开头
        this.head = null
        // 双向链表结尾
      	 this.tail = null
    }
    // ...
}

@前端进阶之旅: 代码已经复制到剪贴板

接下来，需要实现双向链表原型上的一些方法，这些方法包括以下几种。

# `add：在链表尾部添加一个新的节点`

add(item) {
  // 实例化一个节点
  let node = new Node(item)
  // 如果当前链表还没有头
  if(!this.head) {
    this.head = node
    this.tail = node
  }
  
  // 如果当前链表已经有了头，只需要在尾部加上该节点
  else {
    // 把当前的尾部作为新节点的 prev
    node.prev = this.tail
    // 把当前的尾部的 next 指向为新节点 node
    this.tail.next = node
    this.tail = node
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

# `addAt：在链表指定位置添加一个新的节点`

addAt(index, item) {
   let current = this.head
   
   // 维护查找时当前节点的索引
   let counter = 1
   let node = new Node(item)
   // 如果在头部插入
   if (index === 0) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } 
   
   // 非头部插入，需要从头开始，找寻插入位置
   else {
     while(current) {
      current = current.next
      if( counter === index) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

# `remove：删除链表指定数据项节点`

remove(item) {
  let current = this.head
  while (current) {
       // 找到了目标节点
    if (current.data === item ) {
      // 目标链表只有当前目标项，即目标节点即是链表头又是链表尾
      if (current == this.head && current == this.tail) {
        this.head = null
        this.tail = null
      } 
      // 目标节点为链表头
      else if (current == this.head ) {
        this.head = this.head.next
        this.head.prev = null
      } 
      // 目标节点为链表尾部
      else if (current == this.tail ) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } 
      // 目标节点在链表首尾之间，中部
      else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

# `removeAt：删除链表指定位置节点`

removeAt(index) {
  // 都是从“头”开始遍历
  let current = this.head
  let counter = 1
  // 删除链表头部
  if (index === 0 ) {
   this.head = this.head.next
   this.head.prev = null
  } 
  else {
   while(current) {
    current = current.next
    // 如果目标节点在链表尾
    if (current == this.tail) {
     this.tail = this.tail.prev
     this.tail.next = null
    } 
    else if (counter === index) {
     current.prev.next = current.next
     current.next.prev = current.prev
     break
    }
    counter++
   }
  }
}

@前端进阶之旅: 代码已经复制到剪贴板

# `reverse：翻转链表`

reverse() {
  let current = this.head
  let prev = null
  while (current) {
   let next = current.next
   // 前后倒置
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}

@前端进阶之旅: 代码已经复制到剪贴板

# `swap：交换两个节点数据`

swap(index1, index2) {
  // 使 index1 始终小于 index2，方便后面查找交换
  if (index1 > index2) {
    return this.swap(index2, index1)
  }
  let current = this.head
  let counter = 0
  let firstNode
  while(current !== null) {
    // 找到第一个节点，先存起来
    if (counter === index1 ){
        firstNode = current
    } 
    // 找到第二个节点，进行数据交换
    else if (counter === index2) {
      // ES 提供了更为简洁的交换数据的方式，这里我们用传统方式实现，更为直观
      let temp = current.data
      current.data = firstNode.data
      firstNode.data = temp
    }
    current = current.next
    counter++
  }
  return true
}

@前端进阶之旅: 代码已经复制到剪贴板

# `isEmpty：查询链表是否为空`

isEmpty() {
  return this.length() < 1
}

@前端进阶之旅: 代码已经复制到剪贴板

# `length：查询链表长度`

length() {
  let current = this.head
  let counter = 0
  // 完整遍历一遍链表
  while(current !== null) {
    counter++
    current = current.next
  }
  return counter
}

@前端进阶之旅: 代码已经复制到剪贴板

# `traverse：遍历链表`

如上代码，有了上面 length 方法的遍历实现，traverse 也就不难理解了，它接受一个遍历执行函数，在 while 循环中进行调用。

# `find：查找某个节点的索引`

# 树

二叉搜索树有以下特性：

# 数据结构介绍

# 堆栈和队列

# 链表（单向链表和双向链表）

# add：在链表尾部添加一个新的节点

# addAt：在链表指定位置添加一个新的节点

# remove：删除链表指定数据项节点

# removeAt：删除链表指定位置节点

# reverse：翻转链表

# swap：交换两个节点数据

# isEmpty：查询链表是否为空

# length：查询链表长度

# traverse：遍历链表

# find：查找某个节点的索引

# 树

# 图

# `add：在链表尾部添加一个新的节点`

# `addAt：在链表指定位置添加一个新的节点`

# `remove：删除链表指定数据项节点`

# `removeAt：删除链表指定位置节点`

# `reverse：翻转链表`

# `swap：交换两个节点数据`

# `isEmpty：查询链表是否为空`

# `length：查询链表长度`

# `traverse：遍历链表`

# `find：查找某个节点的索引`

JS数据结构介绍|算法篇

JS数据结构介绍|算法篇