数据结构与算法 – 链表

链表是由一组节点组成的集合。 每个节点都使用一个对象的引用指向它的后继。 指向另一个节点的引用叫做链。 链表有三种类型,单向链表,双向链表和循环链表,这里重点只介绍前面两种链表。

链表的类包含了两个类,Node 类用来表示节点, LinkedList 类提供了插入节点、 删除节点、 显示列表元素的方法, 以及其他一些辅助方法。

1、单向链表的类实现

function Node(element){
	this.element = element;
	this.next = null;
}
function LList() {
	this.head = new Node("head");
	this.find = find;
	this.insert = insert;
	this.remove = remove;
	this.display = display;
}
function find(item) {
	var currNode = this.head;
	while (currNode.element != item) {
		currNode = currNode.next;
	}
	return currNode;
}
function insert(newElement, item) {
	var newNode = new Node(newElement);
	var current = this.find(item);
	newNode.next = current.next;
	current.next = newNode;
}
function display() {
	var currNode = this.head;
	while (!(currNode.next == null)) {
		console.log(currNode.next.element);
		currNode = currNode.next;
	}
}
function findPrevious(item) {
	var currNode = this.head;
	while (!(currNode.next == null) && (currNode.next.element != item)) {
		currNode = currNode.next;
	} 
	return currNode;
}
function remove(item) {
	var prevNode = this.findPrevious(item);
	if (!(prevNode.next == null)) {
		prevNode.next = prevNode.next.next;
	}
}

尽管从链表的头节点遍历到尾节点很简单, 但反过来, 从后向前遍历则没那么简单。 通过给 Node 对象增加一个属性, 该属性存储指向前驱节点的链接, 这样就容易多了。 此时向链表插入一个节点需要更多的工作, 我们需要指出该节点正确的前驱和后继。 但是在从链表中删除节点时, 效率提高了, 不需要再查找待删除节点的前驱节点了。

2、双向链表的类实现

function Node(element){
	this.element = element;
	this.next = null;
	this.previous = null;
}
function LList() {
	this.head = new Node("head");
	this.find = find;
	this.insert = insert;
	this.remove = remove;
	this.display = display;
}
function find(item) {
	var currNode = this.head;
	while (currNode.element != item) {
		currNode = currNode.next;
	}
	return currNode;
}
function insert(newElement, item) {
	var newNode = new Node(newElement);
	var current = this.find(item);
	newNode.next = current.next;
	newNode.previous = current;
	current.next = newNode;
}
function display() {
	var currNode = this.head;
	while (!(currNode.next == null)) {
		console.log(currNode.next.element);
		currNode = currNode.next;
	}
}
function remove(item) {
	var currNode = this.find(item);
	if (!(currNode.next == null)) {
		currNode.previous.next = currNode.next;
		currNode.next.previous = currNode.previous;
		currNode.next = null;
		currNode.previous = null;
	}
}
function findLast() {
	var currNode = this.head;
	while (!(currNode.next == null)) {
		currNode = currNode.next;
	} 
	return currNode;
}
function dispReverse() {
	var currNode = this.head;
	currNode = this.findLast();
	while (!(currNode.previous == null)) {
		console.log(currNode.element);
		currNode = currNode.previous;
	}
}

3、循环链表

循环链表和单向链表相似, 节点类型都是一样的。 唯一的区别是, 在创建循环链表时, 让其头节点的 next 属性指向它本身, 即:
head.next = head这种行为会传导至链表中的每个节点, 使得每个节点的 next 属性都指向链表的头节点。 换句话说, 链表的尾节点指向头节点, 形成了一个循环链表。

  • 支付宝二维码 支付宝
  • 微信二维码 微信
相关文章