<script>
// 封装双向链表
function DoublyLinkedList() {
// 封装内部类: 节点类
function Node(data) {
this.data = data;
this.prev = null;
this.next = null;
}
// 属性
this.head = null;
this.tail = null;
this.length = 0;
// 常见操作：方法
// 1.追加方法
DoublyLinkedList.prototype.append = function(data) {
// 创建新节点
var newNode = new Node(data);
// 判断长度是否为0
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
// 长度+1
this.length += 1;
};
// 2.toString 方法
DoublyLinkedList.prototype.toString = function() {
return this.backwardString();
};
// 2.2 forwardString 方法
DoublyLinkedList.prototype.forwardString = function() {
// 定义变量
var current = this.tail;
var resultString = "";
// 依次向前遍历
while (current) {
resultString += current.data + " ";
current = current.prev;
}
return resultString;
};
// 2.3 backwardString 方法
DoublyLinkedList.prototype.backwardString = function() {
// 定义变量
var current = this.head;
var resultString = "";
// 依次向后遍历
while (current) {
resultString += current.data + " ";
current = current.next;
}
return resultString;
};
// 3 insert 方法
DoublyLinkedList.prototype.insert = function(position, data) {
// 越界判断
if (position < 0 || position > this.length) return false;
var newNode = new Node(data);
// 判断原来链表是否为空
if (this.length === 0) {
this.head = newNode;
this.tail = newNode;
} else {
if (position === 0) {
//判断position是否为0
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
} else if (position == this.length) {
// position == this.length
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
// 其他情况
if (position < this.length / 2) {
// 从前到后查找指定位置插入
var current = this.head;
var index = 0;
while (index++ < position) {
current = current.next;
}
newNode.next = current;
newNode.prev = current.prev;
current.prev.next = newNode;
current.prev = newNode;
} else {
// 从后到前查找指定位置插入
var current = this.tail;
var index = this.length;
while (index-- > position) {
current = current.prev;
}
newNode.prev = current;
newNode.next = current.next;
current.next.prev = newNode;
current.next = newNode;
}
}
}
// 链表长度+1
this.length += 1;
};
// 4. get方法
DoublyLinkedList.prototype.get = function(position) {
// 越界判断
if (position < 0 || position >= this.length) return false;
if (position < this.length / 2) {
// 从前往后查找
var index = 0;
var current = this.head;
while (index++ < position) {
current = current.next;
}
return current.data;
} else {
//从后往前查找
var index = this.length - 1;
var current = this.tail;
while (index-- > position) {
current = current.prev;
}
return current.data;
}
};
// 5. indexOf 方法
DoublyLinkedList.prototype.indexOf = function(data) {
var index = 0;
var current = this.head;
while (current) {
if (current.data == data) return index;
current = current.next;
index += 1;
}
return -1;
};
// 6. update 方法
DoublyLinkedList.prototype.update = function(position, data) {
// 越界判断
if (position < 0 || position > this.length) return false;
// 通过position判断从前还是从后查找
if (position < this.length / 2) {
//从前往后找
// 定义变量
var index = 0;
var current = this.head;
// 循环查找
while (index++ < position) {
current = current.next;
}
// 修改指定位置的数据
current.data = data;
} else {
// 从后往前找
// 定义变量
var index = this.length - 1;
var current = this.tail;
// 循环查找
while (index-- > this.length) {
current = current.prev;
}
// 修改指定位置的数据
current.data = data;
}
return true;
};
// 7. removeAt方法
DoublyLinkedList.prototype.removeAt = function(position) {
// 越界判断
if (position < 0 || position >= this.length) return null;
// position === 0
if (position == 0) {
if (this.length == 1) {
this.head = null;
this.tail = null;
} else {
this.head.next.prev = null;
this.head = this.head.next;
}
} else if (position == this.length - 1) {
this.tail.prev.next = null;
this.tail = this.tail.prev;
} else {
// 通过position判断是从前还是从后查找
if (position < this.length / 2) {
//从前往后找\
// 定义变量
var current = this.head;
var index = 0;
// 循环找到指定位置
while (index++ < position) {
current = current.next;
}
// 删除指定位置的元素
current.prev.next = current.next;
current.next.prev = current.prev;
} else {
//从后往前找
// 定义变量
var current = this.tail;
var index = this.length - 1;
// 循环找到指定位置
while (index-- > position) {
current = current.prev;
}
// 删除指定位置的元素
current.prev.next = current.next;
current.next.prev = current.prev;
}
}
// 链表长度减一
this.length -= 1;
return current.data;
};
// 8. remove 方法
DoublyLinkedList.prototype.remove = function(data) {
// 获取data对应的位置
var position = list.indexOf(data);
// 从指定位置删除该元素
return list.removeAt(position);
};
// 9.isEmpty 方法
DoublyLinkedList.prototype.isEmpty = function() {
return this.length === 0
}
// 10. size 方法
DoublyLinkedList.prototype.size = function() {
return this.length
}
}
var list = new DoublyLinkedList();
</script>