链表结构

[conan1992]

链表结构

链表结构不同于数组, 链表中的元素在内存中不必是连续的空间；
链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.

相对于数组, 链表有一些优点:

• 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.
• 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.
• 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.

代码实现

function LinkedList(){
	this.length = 0;
	this.head = null;
}
function Node(element){
	this.element = element;
	this.next = null;
}
LinkedList.prototype.append = function(element){
	var newNode = new Node(element);
	if(!this.head){
		this.head = newNode;
	}else{
		var currentNode = this.head;
		while(currentNode.next){
			currentNode = currentNode.next
		}
		currentNode.next = newNode;
	}
	this.length++;
	//console.log(this.head)
};
LinkedList.prototype.toArray = function(element){
	var arr = [];
	var currentNode = this.head
	while(currentNode){
		arr.push(currentNode.element)
		currentNode = currentNode.next;
	}
	return arr
}
LinkedList.prototype.insert = function(position, element){
	//检测越界问题
	if(position<0 || position>this.length){
		throw Error("请输入正确position")
	}
	var newNode = new Node(element);
	var currentNode = this.head;
	var prevNode = null
	var index = 0;
	if(position==0){
		newNode.next = this.head;
		this.head = newNode;
	}else{
		while(index++<position){
			prevNode = currentNode;
			currentNode = currentNode.next;
		}
		prevNode.next = newNode;
		newNode.next = currentNode;
	}
	return this.length++;
}
LinkedList.prototype.removeAt = function(position){
	//检测越界问题
	if(position<0 || position>=this.length){
		return null
	}
	var currentNode = this.head;
	var prevNode = null;
	var index = 0;
	if(position==0){
		this.head = currentNode.next;
	}else{
		while(index++<position){
			prevNode = currentNode;
			currentNode = currentNode.next;
		}
		prevNode.next = currentNode.next
	}
	this.length--;
	return currentNode.element
}
LinkedList.prototype.indexOf = function(element){
	//检测越界问题
	var currentNode = this.head;
	var index = 0;
	while(currentNode){
		if(currentNode.element==element){
			return index
		}
		currentNode = currentNode.next
		index++
	}
	return -1
}
//根据元素删除信息
LinkedList.prototype.remove = function (element) {
    var index = this.indexOf(element)
    return this.removeAt(index)
}
LinkedList.prototype.isEmpty = function (element) {
	return this.length == 0
}
//获取链表的长度
LinkedList.prototype.size = function () {
    return this.length
}
var linkedList = new LinkedList();
linkedList.append('a')
linkedList.append('b')
linkedList.append('c')

console.log(linkedList.toArray())
console.log(linkedList.remove('b'))
console.log(linkedList.toArray())

参考链接

• 数据结构(五)之链表结构