<Git命令简化笔记 JavaScript排序算法及性能比较>

JavaScript链表实例

#### 前言
  从某种意义上来说，JavaScript的集合为一种集合的对象，主要有Array，与像Java的数组不同，JavaScript的数组也是一种类对象，而链表，没有定义这种数据类型，所以这里[西法](http://www.boatsky.com "太空船博客")使用函数模拟一下链表，但与实际Java的链表还是有差异的。（注：以下例子的链表是线型不循环的。）
#### 单向链表
  单向链表身为一种集合，有一个个节点构成，每个节点，需有类似指针next与数据存储字段nodeData，用函数Node表示，而函数LinkedList表示单向链表。
```javascript
function LinkedList(){
	this.head = null;
	this.length = 0;
	function Node(nodeData){
		this.nodeData = nodeData;
		this.next = null;
	}
	//插入至任意位置
	this.insert = function(nodeIndex,nodeData){
		//插入结果bool值
		var b = false;
		nodeIndex = parseInt(nodeIndex);
		if(nodeIndex === nodeIndex){
			if(nodeIndex >=0 && nodeIndex <= this.length){
				if(nodeIndex == 0){
					this.unshift(nodeData);
				}
				else if(nodeIndex == this.length){
					this.push(nodeData);
				}
				else {
					var q = 1,
						pNode = this.head,
						qNode = pNode.next,
						currentNode = new Node(nodeData);
					//插入至pq之间，相当于取代q的位置，同时把q退后一位
					while(q < nodeIndex){
						pNode = pNode.next;
						qNode = pNode.next;
						q++;
					}
					pNode.next = currentNode;
					currentNode.next = qNode;
					this.length++;
				}
				b = true;
			}
		}
		return b;
	}
	//删除任意位置
	this.delete = function(nodeIndex){
		var b = false;
		nodeIndex = parseInt(nodeIndex);
		if(nodeIndex === nodeIndex){
			if(nodeIndex >=0 && nodeIndex < this.length){
				if(nodeIndex == 0){
					this.shift();
				}
				else if(nodeIndex == this.length - 1){
					this.pop();
				}
				else {
					var q = 1,
						pNode = this.head,
						qNode = pNode.next,
						rNode = qNode.next;
					//p,q,r。删除q
					while(q < nodeIndex){
						pNode = pNode.next;
						qNode = pNode.next;
						rNode = qNode.next;
						q++;
					}
					pNode.next = rNode;
					this.length--;
				}
				b = true;
			}
		}
		return b;
	}
	//插入首位
	this.unshift = function(nodeData){
		if(this.head != null){
			var oldHead = this.head;
			this.head = new Node(nodeData);
			this.head.next = oldHead;
		}
		else {
			this.head = new Node(nodeData);
		}
		this.length++;
		return this.length;
	}
	//插入到末位
	this.push = function(nodeData){
		var currentNode = null;
		if(this.head == null){
			this.head = new Node(nodeData);
		}
		else {
			currentNode = this.head;
			while(currentNode.next){
				currentNode = currentNode.next;
			}
			currentNode.next = new Node(nodeData);
		}
		this.length++;
		return this.length;
	}
	//删除首位
	this.shift = function(){
		var nodeData;
		if(this.head != null){
			nodeData = this.head.nodeData;
			if(this.head.next == null){
				this.head = null;
			}
			else {
				this.head = this.head.next;
			}
			this.length--;
		}
		return nodeData;
	}
	//删除末位
	this.pop = function(){
		var currentNode,nodeData;
		if(this.head != null){
			currentNode = this.head;
			if(currentNode.next == null){
				this.head = null;
				nodeData = currentNode.nodeData;
			}
			else {
				//找到倒数第二个
				while(currentNode.next.next){
					currentNode = currentNode.next;
				}
				nodeData = currentNode.next.nodeData;
				currentNode.next = null;
			}
			this.length--;
		}
		return nodeData;
	}
	//链表反转
	this.reverse = function(){
		if(this.head != null && this.head.next != null){
			var p,q,r;
			p = this.head;
			q = this.head.next;
			this.head.next = null;
			while(q.next){
				r = q.next;
				q.next = p;
				p = q;
				q = r;
			}
			q.next = p;
			this.head = q;
		}
	}
}
```
在chrome控制台写几行例子测试一下：
```javascript
var linkedList = new LinkedList();
console.log(linkedList.unshift(10));//10
console.log(linkedList.push(30));//10,30
console.log(linkedList.push(40));//10,30,40
console.log(linkedList.shift());//30,40
console.log(linkedList.pop());//30
//这么写的原因，在chrome console.log，程序过程中的打印对象结果，在最终查看内部详情时，却显示最终结果
console.log(JSON.parse(JSON.stringify(linkedList)));
console.log(linkedList.insert(0,10));//10,30
console.log(linkedList.insert(1,20));//10,20,30
console.log(linkedList.delete(1));//10,30
console.log(linkedList.reverse());//30,10
```
#### 双向链表
道理同上，只是增加一个prve指向上个节点，因为双向链表反转没什么意义，此处省略。
```javascript
function LinkedListTwo(){
	this.head = null;
	this.length = 0;
	function Node(nodeData){
		this.nodeData = nodeData;
		this.prev = null;
		this.next = null;
	}
	//插入至任意位置
	this.insert = function(nodeIndex,nodeData){
		var b = false;
		nodeIndex = parseInt(nodeIndex);
		if(nodeIndex === nodeIndex){
			if(nodeIndex >=0 && nodeIndex <= this.length){
				if(nodeIndex == 0){
					this.unshift(nodeData);
				}
				else if(nodeIndex == this.length){
					this.push(nodeData);
				}
				else {
					var q = 1,
						pNode = this.head,
						qNode = pNode.next,
						currentNode = new Node(nodeData);
					//插入至pq之间，相当于取代q的位置，同时把q退后一位
					while(q < nodeIndex){
						pNode = pNode.next;
						qNode = pNode.next;
						q++;
					}
					pNode.next = currentNode;
					currentNode.prev = pNode;
					currentNode.next = qNode;
					qNode.prev = currentNode;
					this.length++;
				}
				b = true;
			}
		}
		return b;
	}
	//删除任意位置
	this.delete = function(nodeIndex){
		var b = false;
		nodeIndex = parseInt(nodeIndex);
		if(nodeIndex === nodeIndex){
			if(nodeIndex >=0 && nodeIndex < this.length){
				if(nodeIndex == 0){
					this.shift();
				}
				else if(nodeIndex == this.length - 1){
					this.pop();
				}
				else {
					var q = 1,
						pNode = this.head,
						qNode = pNode.next,
						rNode = qNode.next;
					//p,q,r。删除q
					while(q < nodeIndex){
						pNode = pNode.next;
						qNode = pNode.next;
						rNode = qNode.next;
						q++;
					}
					pNode.next = rNode;
					rNode.prev = pNode;
					this.length--;
				}
				b = true;
			}
		}
		return b;
	}
	//插入首位
	this.unshift = function(nodeData){
		if(this.head != null){
			var oldHead = this.head;
			this.head = new Node(nodeData);
			this.head.next = oldHead;
			oldHead.prev = this.head;
		}
		else {
			this.head = new Node(nodeData);
		}
		this.length++;
		return this.length;
	}
	//插入到末位
	this.push = function(nodeData){
		var currentNode = null;
		if(this.head == null){
			this.head = new Node(nodeData);
		}
		else {
			currentNode = this.head;
			while(currentNode.next){
				currentNode = currentNode.next;
			}
			var insertNode = new Node(nodeData);
			currentNode.next = insertNode;
			insertNode.prev = currentNode;
		}
		this.length++;
		return this.length;
	}
	//删除首位
	this.shift = function(){
		var nodeData;
		if(this.head != null){
			nodeData = this.head.nodeData;
			if(this.head.next == null){
				this.head = null;
			}
			else {
				this.head = this.head.next;
				this.head.prev = null;
			}
			this.length--;
		}
		return nodeData;
	}
	//删除末位
	this.pop = function(){
		var currentNode,nodeData;
		if(this.head != null){
			currentNode = this.head;
			if(currentNode.next == null){
				this.head = null;
				nodeData = currentNode.nodeData;
			}
			else {
				while(currentNode.next.next){
					currentNode = currentNode.next;
				}
				nodeData = currentNode.next.nodeData;
				currentNode.next = null;
			}
			this.length--;
		}
		return nodeData;
	}
	
}
```
测试：
```javascript
var linkedListTwo = new LinkedListTwo();
console.log(linkedListTwo.unshift(10));//10
console.log(linkedListTwo.push(30));//10,30
console.log(linkedListTwo.push(40));//10,30,40
console.log(linkedListTwo.shift());//30,40
console.log(linkedListTwo.pop());//30
console.log(linkedListTwo.insert(0,10));//10,30
console.log(linkedListTwo.insert(1,20));//10,20,30
console.log(linkedListTwo.delete(1));//10,30
```

如果觉得有帮忙，您可以在本页底部留言。

JavaScript链表实例

全部留言

我要留言