数据结构之线性表

线性表

线性表的顺序存储

指用一组地址连续的存储单元依次存储线性表的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中

function List(len, initData) {
	if (!initData) 
		initData = []

	if ( !(initData instanceof Array) )
		throw 'initData为数组'

	if (len < initData.length) 
		throw 'initData初始数据过长'

	this.len = len
	this._list = new Array(len)

	this.init(initData)
}

List.prototype = {
	init: function(initData) {
		for (var i in initData) {
			this._list[i] = initData[i]
		}
	},
	delIndex: function(i) {
		if (i <= 0) 
			throw 'i不能为负数'

		if (i > this.len) 
			throw 'i不能大于线性表长度'

		if (this.len === 0)
			throw '当前为空'

		var val = this._list[i]
		this.len --
		this._list.length = this.len
		for (var j = i; j < this.len; j++)
			this._list[j] = this._list[j + 1]

		return val;
	},
	delValue: function(val) {
		var idx = this.getIndex(val)
		return this.delIndex(idx)
	},
	insert: function(i, val) {
		if (i <= 0) 
			throw 'i不能为负数'

		if (i > this.len) 
			throw 'i不能大于线性表长度'

		this.len ++
		for (var j = this._list.length; j > i; j--) 
			this._list[j] = this._list[j - 1]

		this._list[i] = val;
	},
	getIndex: function(val) {
		var index = -1
		for (var i = 0; i < this.len; i++) {
			if (this._list[i] === val) {
				index = i
				break;
			} 
		}
		return index
	},
	getValue: function(i) {
		return this._list[i]
	},
	getList() {
		return this._list
	}
}

var l = new List(20, [1, 2, 3, 4, 5, 6, 7, 8, 9])
console.log(l.getList())
l.insert(2, 22)
console.log(l.getList())
console.log(l.getIndex(22))
console.log(l.getValue(2))
l.delValue(22);
console.log(l.getList())
l.delIndex(2);
console.log(l.getList())

线性表的链式存储

链表：链表使用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置。

• 单向链表

function Node(data) {
	this.data = data
	this.next = null
}

function LinkList(headData) {
	this.head = new Node(headData)
}

LinkList.prototype = {
	insert: function(data, index) {
		var newNode = new Node(data)
		var curNode = this.find(index)

		newNode.next = curNode.next
		curNode.next = newNode
	},
	delele: function(index) {
		var curNode = this.find(index)
		var preNode = this.find(index - 1)
		preNode.next = curNode.next
	},
	find: function(index) {
		var curNode = this.head
		for (var i = 0; i < index; i++) {
			curNode = curNode.next
		}
		return curNode
	},
	display: function() {
		var curNode = this.head
		var arr = []
		while (curNode != null) {
			arr.unshift(curNode.data)
			curNode = curNode.next
		}
		return arr
	}
}

var list = new LinkList('head');  
   var array = new Array(1,2,3,4,5,6);  
   for(i = 0;i < array.length;i++){  
       list.insert(array[i]);  
   }  
   console.log( list.display() )  

   list.delele(5);  
   console.log( list.display() )

• 双向链表

function Node(data) {
	this.data = data
	this.next = null
	this.prev = null
}

function DoubleLinkList(headData) {
	this.head = new Node(headData)
}

DoubleLinkList.prototype = {
	insert: function(data, index) {
		var newNode = new Node(data)
		var curNode = this.find(index)

		newNode.next = curNode.next
		newNode.prev = curNode
		curNode.next = newNode
		curNode.next.prev = newNode
	},
	delele: function(index) {
		var curNode = this.find(index)
		var preNode = this.find(index - 1)

		
		preNode.next = curNode.next
		curNode.next.prev = preNode
	},
	find: function(index) {
		var curNode = this.head
		for (var i = 0; i < index; i++) {
			curNode = curNode.next
		}
		return curNode
	},
	display: function() {
		var curNode = this.head
		var arr = []
		while (curNode != null) {
			arr.unshift(curNode.data)
			curNode = curNode.next
		}
		return arr
	}
}

• 循环链表

function Node(data) {
	this.data = data
	this.next = null
}

function CyclicLinkList(headData) {
	this.head = new Node(headData)
	this.head.next = this.head;
}

CyclicLinkList.prototype = {
	insert: function(data, index) {
		var newNode = new Node(data)
		var curNode = this.find(index)

		newNode.next = curNode.next
		curNode.next = newNode
	},
	delele: function(index) {
		var curNode = this.find(index)
		var preNode = this.find(index - 1)

		preNode.next = curNode.next
	},
	find: function(index) {
		var curNode = this.head
		for (var i = 0; i < index; i++) {
			curNode = curNode.next
		}

		return curNode
	},
	display: function() {
		var curNode = this.head
		var arr = []
		while (curNode != null && curNode.next.data !== 'head') {
			arr.unshift(curNode.data)
			curNode = curNode.next
		}
		return arr
	}
}

var list = new CyclicLinkList('head');  
   var array = new Array(1,2,3,4,5,6);  
   for(i = 0;i < array.length;i++){  
       list.insert(array[i], i);  
   }  
   console.log( list.display() )  

   list.delele(5);  
   console.log( list.display() )