---

前言

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示

数据结构和编程语言的种类没有关系，这里是用javascript来实现

一、数组

要存储多个元素，数组（或称为列表）可能是最常用的数据结构

数组的缺点：
1.数组的创建通常需要申请一段连续的内存空间（一整块内存），并且大小是固定的，所以当当前数组不满足容量需求的时，需要扩容。（一般情况下是申请一个更大的数组，比如2倍，然后将原数组中的元素复制过去）
2.而且在数组开头或者中间位置插入数据的成本很高，需要大量元素的唯一

但数组的二分查找时间复杂度小，都是O(1)；数组的特点是：查询简单，增加和删除困难；

二、链表

相比较普通的线性结构，链表结构的可以总结一下：
（1）单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小
（2）结点的删除非常方便，不需要像线性结构那样移动剩下的数据
（3）结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

因为javascrpt中有数组结构，但是没有链表，所以需要我们自己封装
其中，链表中又分单向链表和双向链表。

1.单向链表

//封装一个链表对象
  function LinkedList(){
	  //头指针
	  this.head = null
	  //初始化链表的长度
	  this.length = 0

	  //定义一个Node类
	  function Node(data){
		//data数据本身
		this.data = data
		//指向下一个node的指针
		this.next = null
	  }

	  //向列表尾部添加一个新的项
	  LinkedList.prototype.append = function(data) {
		//创建一个新的项
		var newNode = new Node(data)
		//列表为空，则让head指向该node
		if(!this.length){
			this.head = newNode
		}else{
			var current = this.head
			//循环遍历找到最后一项
			while(current.next){
				current = current.next
			}
			current.next = newNode
		}
		//添加完，列表长度加一
		this.length++
	  }

	  //向特定的位置插入一个新的项
	  LinkedList.prototype.insert = function(position, data) {
		if(position < 0 || position > this.length)return false

		var newNode = new Node(data)
		if(position == 0){
			newNode.next = this.head
			this.head = newNode
		}else{
			// var index = 0
			// var current = this.head
			// var previous = null
			// while (index++ < position) {
			// 	previous = current
			// 	current = current.next
			// }
			// newNode.next = current
			// previous.next = newNode
			var current = this.head
			while(--position){current = current.next}
			newNode.next = current.next
			current.next = newNode
		}
		//添加完，列表长度加一
		this.length++

	  }

	  //获得对应位置的元素
	  LinkedList.prototype.get = function(position) {
		  if(position > this.length-1 || position < 0)return null

		  var current = this.head
		  var index = 0
		  while(index++ < position){
			  current = current.next
		  }
		  return current.data
	  }

	  //返回元素在列表中的索引，如果没有找到，则返回-1
	  LinkedList.prototype.indexOf = function(data) {
		var current = this.head
		var index =0
		while(current){
			if(current.data == data){
				return index 
			}
			index++
			current = current.next
		}
		return -1

	  }

	  //从列表中特定位置移除一项
	  LinkedList.prototype.removeAt = function(position) {
		  //越界判断
		if(position < 0 || position > this.length - 1)return null
		
		var current = this.head
		//当position == 0
		if(position == 0) {
			this.head = this.head.next
		}else{
			var index = 0
			var current = this.head
			var previous = null
			while(index++ < position){
				previous = current
				current = current.next
			}
			previous.next = current.next
		}
		this.length--
		return current.data
	  }

	  //从列表中删除一项
	  LinkedList.prototype.remove = function(data) {
		//获取data在列表中的位置
		var position = this.indexOf(data)
		//删除列表中position位置的元素
		return this.removeAt(position)
		
	  }

	  //修改某个位置的元素
	  LinkedList.prototype.update = function(position, newData) {
		if(position < 0 || position > this.length - 1)return false
		
		  var current = this.head
		  var index = 0
		  while(index++ < position){
			current = current.next
		  }
		  current.data = newData
		  return true
	  }

	  //isEmpty,判断列表是否为空，为空则返回true， 不为空则返回false
	  LinkedList.prototype.isEmpty = function() {
		return this.length == 0
	  }

	  //返回列表的长度
	  LinkedList.prototype.size = function() {
		return this.length
	  }

	  //toString, 输出列表中每个node的值
	  LinkedList.prototype.toString = function() {
		var current = this.head
		var linkString = ''

		//循环节点
		while(current){
			linkString = linkString + current.data
			current = current.next
		}
		return linkString
	  }


  }
  var link = new LinkedList()

2.封装双向链表

双向链表的特点：
1.可以使用一个head和一个tail分别指向头部和尾部的节点
2.每个节点都由三个部分组成，前一个节点的指针（prev） 和保存的元素（item）和后一个节点的指针（next）
3.双向链表的第一个节点的prev是null
双向链表的最后的节点的next是null

  function DouleLinkList() {
		//封装一个内部类，节点
		function Node(data) {
			this.data = data
			this.prev = null
			this.next = null
		}
		//头指针
		this.head = null
		//尾部指针
		this.tail= null
		//链表长度
		this.length = 0

		//向列表尾部添加一个新的项
		DouleLinkList.prototype.append = function(data) {
			//创建新节点
			var newNode = new Node(data)

			//判断是否为空，为空直接插入
			if(this.length == 0){
				this.head = newNode
				this.tail = newNode
			}else{
				newNode.prev = this.tail
				this.tail.next = newNode
				this.tail = newNode
			}

			//链表长度加一
			this.length++
		}

		//向列表的特定位置插入一个特定的项
		DouleLinkList.prototype.insert = function(position, data) {
			//越界判断
			if(position < 0 || position > this.length)return false

			//创建新节点
			var newNode = new Node(data)

			//当链表为空
			if(this.length == 0) {
				this.head = newNode
				this.tail = newNode
			}else{
				//当插入位置的是链表头部
				if(position == 0){
					this.head.prev = newNode
					newNode.next = this.head
					this.head = newNode
					//当插入位置是链表的最尾部
				}else if(position == this.length){
					newNode.prev = this.tail
					this.tail.next = newNode
					this.tail = newNode
				}else{
					//判断一般情况
					var current = this.head
					var index = 0
					while(index++ < position){
						current = current.next
					}
					newNode.next = current
					newNode.prev = current.prev
					current.prev.next = newNode
					
					current.prev = newNode

				}
			}
			this.length++
			return true
			
		}

		//获得对应位置的元素
		DouleLinkList.prototype.get = function(position) {
			if(position < 0 || position >= this.length)return null

			var current = this.head
			var index = 0

			while(index++ < position){
				current = current.next
			}
			
			return current.data
		}

		//返回元素在列表中的索引。如果列表中没有该元素则返回-1
		DouleLinkList.prototype.indexOf = function(data) {
			var current = this.head
			var index = 0

			while(current){
				if(current.data == data){
					return index
				}
				
				current = current.next
				index++
			}
			reutrn -1
		}

		//修改某个位置的元素
		DouleLinkList.prototype.update = function(position, data) {
			if(position < 0 || position >= this.length)return false

			var current = this.head
			var index = 0

			while(index++ < position){
				current = current.next
			}

			current.data = data
			return true
			

		}

		//从列表的特定位置移除一项
		DouleLinkList.prototype.removeAt = function(position) {
			if(position < 0 || position >= this.length)return null

			var current = this.head
			//当链表中只有一个元素时
			if(this.length == 1) {
				this.head = null
				this.tail = null
			}else{
				//当链表长度大于一，并且删除的是第一个元素
				if(position == 0){
					this.head.next.perv = null
					this.head = this.head.next
				}else if(position == this.length - 1){
					this.tail.prev.next = null
					this.tail = this.tail.perv
				}else{
					
					var index = 0
					while(index++ < position){
						current = current.next
					}
					current.prev.next = current.next
					current.next.prev = current.prev
				}
			}
			this.length--
			return current.data
		}

		//从列表中移除一项
		DouleLinkList.prototype.remove = function(data) {
			//根据data获取下标值
			var index = this.indexOf(data)
			//根据index删除元素
			return this.removeAt(index)
		}

		//如果链表中不包含任何元素则返回true，如果链表长度大于一则返回false
		DouleLinkList.prototype.isEmpty = function() {
			return this.length == 0
		}

		//返回链表中的元素个数
		DouleLinkList.prototype.size = function() {
			return this.length
		}

		//toString，输出链表中每个节点的data
		DouleLinkList.prototype.toString = function() {
			return this.forwardString()
		}

		//forwardString, 返回正向遍历的节点字符串表达形式
		DouleLinkList.prototype.forwardString = function() {
			var current = this.head
			var resultString = ''

			while(current){
				
				resultString = resultString + current.data
				current = current.next
			}

			return resultString
		}

		//backwardString, 返回反向遍历的节点字符串表达形式
		DouleLinkList.prototype.backwardString = function() {
			var current = this.tail
			var resultString = ''

			while(current){
				resultString = resultString + current.data
				current = current.prev
			}

			return resultString
		}
		
  }

  var a = new DouleLinkList()

三、栈

栈：它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈也被称为后进先出（LIFO）表

1.封装一个栈结构

（一）基于数组

function Stack(){
	//存放数据使用数组
	this.items = [];
	//压栈
	Stack.prototype.push = function(element){
		this.items.push(element)
	}
	//出栈
	Stack.prototype.pop = function(){
		return this.items.pop()
	}
	//访问栈顶
	Stack.prototype.peek = function(){
		return this.items[this.items.length]
	}
	//查询栈是否为空
	Stack.prototype.isEmpty = function(){
		return this.items.length == 0
	}
	//查询栈中的存放个数
	Stack.prototype.size = function(){
		return this.items.length
	}
	//toString
	Stack.prototype.toString = function(){
		return this.items.reduce( (total, currentValue) => {
			return total + (currentValue + '')
		} )
	}
}
//创建栈对象
var stack = new Stack()

2.栈的使用场景

（一）将十进制转化为二进制

function dectobin (decNum) {
	//创建一个栈对象
	var stack = new Stack();
	//存放最后结果
	var binString = ''
	//循环得余数
	while( decNum > 0 ){
		//求余数存入stack中
		stack.push(decNum % 2)
		decNum = Math.floor(decNum / 2)
    }
    //循环导出值
	while(!stack.isEmpty()){
		binString += stack.pop()
	}
	return binString
}
console.log(dectobin(100)) // 十进制100转换为二进制：1100100 

四、队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
栈也被称为先进先出的线性表

1.封装队列

（一）基于数组

function Queue(element){
	//存放数据
	this.items = []
	
	//元素添加进队列
	Queue.prototype.enqueue = function(element){
		this.items.push(element)
	}
	//从队列中删除元素
	Queue.prototype.dequeue = function(){
		return this.items.shift()
	}
	//查看队列中的第一个元素
	Queue.prototype.front = function(){
		return this.items[0]
	}
	//查看队列中是否为空
	Queue.prototype.isEmpty = function(){
		return this.items.length == 0
	}
	//查看队列中元素的个数
	Queue.prototype.size = function(){
		return this.items.length
	}
	//toString
	Queue.prototype.toString = function(){
		return this.items.reduce( (total, currentValue) => {
			return total + (currentValue + '')
		} )
	}
}	

//创建一个队列对象
var queue = new Queue()
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
alert(queue) //102030

2.队列的使用场景

(一) 击鼓传花

题目描述：有n位玩家围在一起玩游戏，设定一个固定的值m，从第一个玩家开始数数字，当数到m的玩家立即淘汰，然后从重新开始，依次循环，直到最后一名玩家存活，则为胜者。

function passGame(nameList, num){
	//创建一个队列结构
	var queue = new Queue()

	//将玩家列表插入队列
	nameList.map( item => {
		queue.enqueue(item)
	})

	//循环，当队列中只剩下一个玩家就停止游戏
	while(queue.size() > 1){
		for(let i = 0; i < num - 1; i++ ){
			queue.enqueue(queue.dequeue())
		}
		//淘汰数到num的玩家
		queue.dequeue()
	}
	alert(queue.toString())
	//返回队列中剩下的最后一个玩家
	return queue.toString()

}

passGame(['小明', '小红', '小白','小蓝', '小紫'], 3) //小蓝

3.优先级队列

优先队列，又称为优先级队列、堆。优先队列是一种特殊的队列，除了具有队列的先入先出，队列头出，队列尾入的结构特点，优先队列最重要的就是要实现快速得到队列中优先级最高的元素，因此，优先队列有一定的顺序特点，这是一种弱序，即队列头部的那个元素是优先级最高的，我们往往以元素值的大小作为优先级来讨论，比如说，数值大的优先级高，则优先队列元素会按一定规则的大小顺序排列，从而使得在队列头部的元素始终保持数值最大（优先级最高）的特点。总之，优先队列的目的就是实现将元素入队列，并快速返回队列优先级最高优先级元素。

（一）封装一个优先级队列

   function PriorityQueue(){
		//封装内部类，优先级队列元素
		function QueueElement(element, priority) {
			this.element = element
			this.priority = priority
		}
		//存储优先级队列的元素
	   this.items = []

	   //往优先级队列中插入元素
	   PriorityQueue.prototype.enqueue = function(element, priority){

		   //创建优先级队列的元素
		   var queueElement = new QueueElement(element, priority)

		   //判断队列有元素，若为空，则直接插入
		   if(this.items.length == 0){
			   this.items.push(queueElement)
		   }else{
			   //
			   var flag = false
				//队列中存在元素，要进行优先级比较
				for(var i =0 ; i < this.items.length  ; i++){
					if(queueElement.priority > this.items[i].priority){
						this.items.splice(i, 0, queueElement)
						flag = true
						break
					}
				}
				if(!flag){
					//若flag为fasle，表示还未找到优先级比该元素小的，元素未插入，则直接插入队尾
					this.items.push(queueElement)
				}
		   }
		   
	   }
	   //从队列中删除元素
	   PriorityQueue.prototype.dequeue = function(){
			return this.items.shift()
		}
		//查看队列中的第一个元素
		PriorityQueue.prototype.front = function(){
			return this.items[0]
		}
		//查看队列中是否为空
		PriorityQueue.prototype.isEmpty = function(){
			return this.items.length == 0
		}
		//查看队列中元素的个数
		PriorityQueue.prototype.size = function(){
			return this.items.length
		}
		//toString
		PriorityQueue.prototype.toString = function(){
			var str = ''
			for(var i =0; i < this.items.length ; i++){
				str += this.items[i].element+''
			}
			return str
		}
   }
    //创建一个实例
	var priorityQueue = new PriorityQueue()
	//插入元素
	priorityQueue.enqueue(10,10)
	priorityQueue.enqueue(20,20)
	priorityQueue.enqueue(30,30)
	
	alert(priorityQueue) //302010

五、总结

1.数组和链表的比较

相对于数组，链表有以下优点：
1.内存空间不是必须连续的，可以利用计算机的内存，实现灵活的内存动态管理
2.链表不必在创建时就确定大小，并且大小可以无限的延伸下取
3.链表在插入和删除数据时，事件复杂度可以达到O（1），相对数组效率高很多

相对于数组，链表有以下缺点：
1.链表访问任何一个位置的元素时，都需要从头开始访问，无法跳过第一个元素访问任何一个元素
2.无法通过下标值直接访问元素，需要从头一个个访问，直到找到对应的元素

2.单向链表和双向链表的比较

单向链表：
1.只能从头遍历到尾或者从尾遍历到头（一般从头到尾）
2.也就是链表相连的过程是单向的
3.实现的原理是上一个链表中有一个指向下一个的引用

单向链表有一个比较明显的缺点：
我们可以很轻松的到达下一个节点，但是回到前一个节点是很难的，但是，在实际开发中，经常会遇到回到上一个节点的情况
双向链表：
1.既可以从头遍历到尾，又可以从尾遍历到头
2.也就是链表相连的过程是双向的
3.一个节点既有向前连接的引用，也有一个向后连接的引用
4.双向链表可以解决单向链表中无法回到上一个节点的问题
双向链表的缺点？
每次在插入或者删除某个节点时，需要处理四个引用，而不是两个，也就是实现起来要困难一些。
并且相当于单向链表，必然占用内存空间更大一些。
但是这些缺点和我们使用起来的方便程度相比，是微不足道的