JavaScript中的双向链表
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title></title>
<script>
function doubleLinkedList () {
var Node = function (element) {
this.element = element;
this.next = null;
this.prev = null;//新增的，保存链表最后一项
};
var length = 0;
var head = null;
var tail = null;
this.append = function(element){
var node = new Node(element);
var current;
var previous;
if(!head){ //若head为空
head = node;
tail = node;
}else{ //head不为空
current = head;
while(current){
previous = current;
current = current.next;
}
node.next = current;
// current.prev = node;
previous.next = node;
node.prev = previous;
}
length++;
return true;
}
//在任意一个位置插入一个新元素
this.insert = function (position, element) { //检查是否越界
if (position >= 0 && position <= length) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position === 0) {
if (!head) {//如果链表为空，把head和tail都指向这个新节点
head = node;
tail = node;
}
else { //链表不为空
node.next = current;
current.prev = node;
head = node;
}
}
else { //插入的位置不是第一个
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
return true;
}
else{
return false;
}
}
//从任意位置移除元素
this.removeAt = function (position) {
if (position >=0 && position < length) {
var current = head;
var previous, index = 0;
if (position === 0) {//移除第一项
head = current.next;
if(length === 1) {//如果只有一项
tail = null;
} else {
head.prev = null;//更新指向上一个元素的指针
}
}
else {
while (index++ < position) {
previous = current;
current = current.next;
}
//将previous与current的下一项链接起来，跳过currrent
previous.next = current.next;
// current.next.prev = previous;
}
length--;
return current.element;
}
else {
return null;
}
};
this.isEmpty=function(){
return length===0;
}
//将doubleLinkedlist对象转换为字符串
this.toString=function(){
var current=head;
var string='';
while(current){ //检查元素是否存在
string+=','+current.element;
current=current.next;
}
return string.slice(1);
}
this.getHead=function(){
return head;
}
this.getTail=function(){
return tail;
}
this.size=function(){
return length;
}
}
var arr=new doubleLinkedList();
arr.append(1);
arr.append(2);
arr.append(3);
arr.append(4);
arr.append(5);
console.log(arr.size())
console.log(arr.toString()+'----------length：'+arr.size());
arr.insert(0,10)
console.log(arr.toString()+'----------length：'+arr.size());
arr.insert(3,10)
console.log(arr.toString()+'----------length：'+arr.size());
arr.insert(5,10)
console.log(arr.toString()+'----------length：'+arr.size());
arr.removeAt(0);
console.log(arr.toString()+'----------length：'+arr.size());
arr.removeAt(6);
console.log(arr.toString()+'----------length：'+arr.size());
arr.isEmpty()
console.log(arr.toString()+'----------length：'+arr.size());
console.log(arr.toString()+'----------length：'+arr.size());
console.log(arr.getHead())
console.log(arr.getTail())
</script>
</head>
<body>
</body>
</html>
数组的优点
- 随机访问性强（通过下标进行快速定位）
- 查找速度快
数组的缺点
- 插入和删除效率低（插入和删除需要移动数据）
- 可能浪费内存（因为是连续的，所以每次申请数组之前必须规定数组的大小，如果大小不合理，则可能会浪费内存）
- 内存空间要求高，必须有足够的连续内存空间。
- 数组大小固定，不能动态拓展
链表的优点
- 插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）
- 内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）
- 大小没有固定，拓展很灵活。
链表的缺点
- 不能随机查找，必须从第一个开始遍历，查找效率低