常见数据结构的JS实现（一）

数据结构和算法是一位优秀的程序员的基本功。在面试时这两点也是考察的重点，本文参考《学习JavaScript数据结构与算法》一书，总结了常见的数据结构。

目录：
一、数组
二、栈和队列
三、链表
四、集合
五、字典和散列表
六、树
七、图

内容较多，先介绍前三种数据结构。

一、数组：
几乎所有的编程语言都原生支持数组类型，因为数组是最简单的内存数据结构。与其他语言相比，JavaScript数组长度和元素类型都是不固定的。并且，数组在内存空间中也可以不连续存在。

1 创建和初始化数组
JavaScript创建数组有两种基本方式：第一种是使用Array构造函数，如下面代码所示：

var colors = new Array();
var colors = new Array(10);  //  创建长度为10的数组
var colors = new Array('red', 'blue', 'green'); //创建包含'red','blue','green'三个值的数组

在使用Array构造函数时，可以省略new操作符。
第二种是使用数组字面量表示法，如下代码所示：

var colors = []; //创建一个空数组
var colors = ['red','blue','green]; //创建一个包含3个字符串的数组

2 添加和删除元素
添加元素到数组末尾：

var colors = ['red','blue','green'];
colors.push('yellow');
console.log(colors);  //  ["red", "blue", "green", "yellow"]

添加元素到数组头部：

var colors = ['red', 'blue', 'green'];
colors.unshift('yellow');
console.log(colors);  //  ["yellow", "red", "blue", "green"]

删除数组末尾元素：

var colors = ['red', 'blue', 'green'];
colors.pop();
console.log(colors);  // ["red", "blue"]

删除数组头部元素：

var colors = ['red', 'blue', 'green'];
colors.shift();
console.log(colors);  // ["blue", "green"]

删除任意位置的元素：
通过数组提供的splice方法，可以删除任意位置的元素，如下所示：

var colors = ['red', 'blue', 'green'];
colors.splice(1,1);
console.log(colors);  // ["red", "green"]

3 JavaScript中数组方法：
JavaScript中数组有很多很强大的方法，大家可以参阅
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array

二、栈和队列：
栈和队列也是比较常见的数据结构，栈是一种遵从后进先出（LIFO）原则的有序列表，只能对栈顶元素进行添加或删除操作。队列是一种遵从先进先出（FIFO）原则的有序列表，只能在尾部添加元素，从头部移除元素。我们可以通过数组来实现栈和队列。
1 栈：

栈.PNG

栈需要声明的方法：
push(element(s)): 添加一个（或几个）新元素到栈顶
pop(): 移除栈顶的元素，同时返回被移除的元素
peek(): 返回栈顶元素
isEmpty(): 栈中是否有元素
clear(): 移除栈中所有元素
size(): 返回栈包含的元素个数
下面是栈的实现方式（构造函数）:

function Stack() {
  var items = [];
  this.push= function(element) {
    items.push(element);
  };
  this.pop= function() {
    return items.shift();
  };
  this.peek= function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length == 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size= function() {
    return items.length;
  };
}

至此，便可以通过var newStack = new Stack()的方式声明一个栈。
2 队列：

队列.PNG

队列需要声明的方法：
enqueue(element(s)): 向队列尾部添加一个（或多个）元素
dequeue(): 移除队列中的第一个元素，并返回该元素
front(): 返回队列中的第一个元素
isEmpty(): 队列中是否有元素
clear(): 移除队列中所有元素
size(): 返回队列包含的元素个数
下面是队列的实现方式（构造函数）：

function Queue() {
  var items = [];
  this.enqueue = function(element) {
    items.push(element);
  };
  this.dequeue = function() {
    return items.shift();
  };
  this.front = function() {
    return items[0];
  };
  this.isEmpty = function() {
    return items.length == 0;
  };
  this.clear = function() {
    items = [];
  };
  this.size= function() {
    return items.length;
  };
}

同样，通过var newQueue = new Queue()的方式声明一个队列。

三、链表：
虽然JavaScript中数组是动态的，并且可以在任意位置添加和删除元素。但其添加和删除元素的成本仍很高，需要移除元素。
链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成。链表，仿佛一列火车，一个元素对应火车的一节车厢，元素的指针就像车厢间的连接。

链表.jpg
首先，创建链表之前先要创建链表中的Node节点。因此，需要先声明Node节点的构造函数。Node节点有两个属性，一个是element属性，即要添加到列表的值，以及一个next属性，即指向列表中写一个节点项的指针：

var Node = function (element) {
  this.element = element;
  thie.next = null;
}

链表需要声明的方法：
append(element): 向链表尾部添加一个新的项

  this.append = function(element) {
    var node = new Node(element),
        current;
    if (head === null) { // 判断链表是否为空
      head = node;
    } else {
        current = head;
        while(current.next) { // 遍历链表，直到最后一个元素
          current = current.next;
        }
        current.next = node; // 找到最后一个元素，将其next设为node
    }
    length++; // 更新链表长度
  };

insert(position, element): 向链表的特定位置插入一个新的项

this.insert = function(position, element) {
  if (position > -1 && position <= length) {
    var node = new Node(element),
        current = head,
        previous,
        index = 0;
    if (position === 0) { //在第一个位置添加
      node.next = current;
      head = node;
    } else {
        while (index++ < position) {
           previous = current;
           current = current.next;
        }
        node.next = current;
        previous.next = node;
    }
    length++; // 更新链表长度
    return true;
  } else {
    return false;
  }
};

removeAt(position): 从链表的特定位置移除一项

this.removeAt = function(position) {
// 检查是否越界
  if (position > -1 && position < length) {
    var current = head,
        previous,
        index = 0;
// 移除第一项
    if (position === 0) {
        head = current.next;
    } else {
        while (index++ < position) {
          previous = current;
          current = current.next;
        }
        // 将previous与current的下一项连接起来
        previous.next = current.next;
      }
    length--;
    return current.element;
} else {
    return null;
  }
};

indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回-1

this.indexOf = function(element) {
  var current = head,
      index = 0;
  while (current) {
    if (element === current.element) {
      return index;
    }
    index++;
    current = current.next;
  }
  return -1;
};

remove(element): 从链表中移除一项

this.remove = function(element) {
  var index = this.indexOf(element);
   return this.removeAt(index);
};

isEmpty(): 链表是否为空

this.isEmpty = function () {
  return length === 0;
};

size(): 链表中包含元素的个数

this.size = function () {
  return length;
};

链表有多种不同的类型，这边介绍两种常见的: 双向链表和循环链表
双向链表：双向链表与普通链表的区别在于，双向链表的链接是双向的：一个链向下一个元素，另一个链向前一个元素，如下图所示：

双向链表.jpg
循环链表：最后一个元素指向下一个元素的指针不是引用null，而是第一个元素，如下图所示：
循环链表.jpg

至此，数组、队列、栈和链表介绍完毕。剩下的四个数据结构下回分晓~