双向链表

[conan1992]

双向链表

• 每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 也就是实现起来要困难一些
• 并且相当于单向链表, 必然占用内存空间更大一些.

代码实现

function DoublyLinkedList(){
	this.length = 0;
	this.head = null;
	this.tail = null
}
function Node(element){
	this.element = element;
	this.next = null;
	this.prev = null;
}
DoublyLinkedList.prototype.append = function(element){
	var newNode = new Node(element);
	if(!this.head){
		this.head = newNode;
		this.tail = newNode;
	}else{
		this.tail.next = newNode;
		newNode.prev = this.tail;
		this.tail = newNode;
	}
	this.length++;
};
DoublyLinkedList.prototype.forwardArray = function(element){
	var arr = [];
	var currentNode = this.head
	while(currentNode){
		arr.push(currentNode.element)
		currentNode = currentNode.next;
	}
	return arr
}
DoublyLinkedList.prototype.reverseArray = function(element){
	var arr = [];
	var currentNode = this.tail
	while(currentNode){
		arr.push(currentNode.element)
		currentNode = currentNode.prev;
	}
	return arr
}
DoublyLinkedList.prototype.insert = function(position, element){
	//检测越界问题
	if(position<0 || position>this.length){
		throw Error("请输入正确position")
	}
	var newNode = new Node(element);
	var currentNode = this.head;
	var previousNode = null;
	var index = 0;
	if(position==0){
		if(this.head){
			this.head = newNode;
			newNode.next = currentNode;
			currentNode.prev = newNode;
		}else{
			this.head = newNode;
			this.tail = newNode;
		}
	}else if(position == this.length){
		this.tail.next = newNode;
		newNode.prev = this.tail;
		this.tail = newNode;
	}else{
		while(index++<position){
			previousNode = currentNode;
			currentNode = currentNode.next
		}
		previousNode.next = newNode;
		currentNode.prev = newNode;
		newNode.prev = previousNode;
		newNode.next = currentNode;
	}
	return this.length++;
}
DoublyLinkedList.prototype.removeAt = function(position){
	//检测越界问题
	if(position<0 || position>this.length-1){
		return null
	}
	var currentNode = this.head;
	var prevNode = null;
	var index = 0;
	if(position==0){
		//不用再判断是否存在头结点了，越界的时候检测过了
		if(this.length==1){
			this.head = null;
			this.tail = null;
		}else{
			this.head = this.head.next;
			this.head.prev = null;
			
		}
	}else if(position=this.length-1){
		currentNode = this.tail
		this.tail = this.tail.prev
		this.tail.next = null;
	}else{
		while(index++<position){
			prevNode = currentNode;
			currentNode = currentNode.next;
		}
		prevNode.next = currentNode.next
		currentNode.next.prev = prevNode;
		
	}
	this.length--;
	return currentNode.element
}
DoublyLinkedList.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
}
// 判断是否为空
DoublyLinkedList.prototype.isEmpty = function () {
    return this.length === 0
}

// 获取链表长度
DoublyLinkedList.prototype.size = function () {
    return this.length
}

// 获取第一个元素
DoublyLinkedList.prototype.getHead = function () {
    return this.head.element
}

// 获取最后一个元素
DoublyLinkedList.prototype.getTail = function () {
    return this.tail.element
}
var DoublyLinkedList = new DoublyLinkedList();
DoublyLinkedList.append('a')
DoublyLinkedList.append('b')
DoublyLinkedList.append('c')
DoublyLinkedList.append('d')
console.log(DoublyLinkedList.removeAt(3))
console.log(DoublyLinkedList.head, DoublyLinkedList.tail)
console.log(DoublyLinkedList.forwardArray())
console.log(DoublyLinkedList.reverseArray())

参考链接

• 数据结构(六)之双向链表