[数据结构与算法]js数据结构之链表1

js数据结构
链表：每一个节点内部都包含数据和指针
1.封装链表

function LinkList() {
	//内部的类：节点类
	function Node(data) {
		this.data = data;
		this.next = null;
	}
	//属性:head指向链表的第一个节点,length表示链表的长度
	this.head = null;
	this.length = 0;
}

2.链表的常见操作
(1).增
append(element):向列表尾部添加一个新的项

LinkList.prototype.append = function (data) {
	//1.创建一个新的节点
	var newNodde = new Node(data);
	//2.判断添加的是否为第一个节点
	if(this.length == 0) {
		this.head = newNode; 
	}else{
		//不是第一个节点则要找到最后一个节点的next
		var current = this.head;
		while(current.next){
			current = current.next;
		}
		//最后一个节点的next指向新的节点
		current.next = newNode;
	}
	//长度加一
	this.length += 1;
}

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

LinkList.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 flag = 0;
		var current = this.head;
		var previous = null;
		while(flag!=position) {
			previous = current;
			current = current.next;
			flag = flag + 1;
		}
		//可以把=号看作是->箭头,由前指向后,便于理解
		previous.next = newNode;
		newNode.next = current;
	}
	this.length += 1;
	return true;
	
}

(2).删
removeAt(position)：从列表的特定位置移除一项

LinkList.prototype.removeAt = function(position) {
	if(position<0||position>=this.length) return false;
	var current = this.head;
	var flag = 0;
	var previous = null;
	if(position == 0) {
		this.head = this.head.next;
	}else{
		while(flag<position){
			previous = current;
			current = current.next;
			flag++;
		}
		previous.next = current.next;
	}
	this.length--;
	return true;
}

remove(element):从列表中移除一项元素element

LinkList.prototype.reMove = function(data) {
	var index = indexOf(data);
	removeAt(index);
}

(3).改
update(position,element):修改某个位置的元素

LinkList.prototype.update = function(position,data) {
	if(position<0||position>=this.length) {
		return false;
	}
	else{
		var current = this.head;
		var flag = 0;
		while(flag < position) {
			current = current.next;
			flag++;  
		}
		current.data = data;
		return true;
	}
}

(4).查
get(position):获取对应位置的元素

LinkList.prototype.get = function(position) {
	if(position<0||position>=this.length) {
		return null;
	}
	else{
		var current = this.head;
		var flag = 0;
		while(flag < position) {
			current = current.next;
			flag++;  
		}
		return current.data;
	}
}

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

LinkList.prototype.indexOf = function(data) {
	var current = this.head;
	var flag = 0;
	while(current) {
		if(current.data == data){
			return flag; 
		}
		current = current.next;
		flag++;  
	}
	return -1;
}

(5).其他：
isEmpty():返回true或者false

LinkList.prototype.isEmpty = function() {
	if(this.length==0) return true;
	else return false; 
}

size():返回链表长度

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

toString()：遍历链表的值，以字符串形式打印出来

LinkList.prototype.toString = function() {
	var current = this.head;
	var listString = "";
	//当链表里还有值时
	while(current) {
		listString += current.data + "";
		current = current.next;
	}
	return listString
}