<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>双向链表</title>
</head>
<body>
<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){
// 1 创建元素
const newNode = new Node(data)
// 2 追加元素
if(this.length == 0){ // 为空的时候
this.head = newNode;
this.tail = newNode;
}else{
// 查询最后一个节点
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
}
// 3 length +1
this.length+=1
}
// 2 将链表转成字符串形式
// 2.1 toString方法
DoublyLinkedList.prototype.toString = function(){
return this.backwardString()
}
// 2.2 forwardString 方法
DoublyLinkedList.prototype.forwardString = function(){
// 1 定义变量
var current = this.tail
var resultString = ""
// 2 依次向前遍历 获取每一个节点
while(current){
resultString += current.data + ‘ ‘
console.log(current.prev)
current = current.prev
}
return resultString
}
// 2.3 backwardString 方法
DoublyLinkedList.prototype.backwardString = function(){
// 1 定义变量
var current = this.head
var resultString = ""
// 2 依次向后遍历 获取每一个节点
while(current){
resultString += current.data + ‘ ‘
current = current.next
}
return resultString
}
// 3 insert 方法
DoublyLinkedList.prototype.insert = function(position,data){
// 越界判断
if(position < 0 ||position > this.lenght) return false
// 2 根据 data 创建新的节点
var newNode = new Node(data)
// 3 判断原来的列表是否为空
if(this.lenght == 0){
this.head = newNode
this.tail = newNode
}else{
// 3.1 判断 position 是否为 0
if(position == 0){
this.head.prev = newNode
newNode.next = this.head
this.head = newNode
}else if(position = this.length){
newNode.prev = this.tail
this.tail.next = newNode
this.tail = newNode
}else{
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
}
}
//4 lenght+1
this.length+= 1
return true
}
// 4 get 方法
DoublyLinkedList.prototype.get = function(position){
// 1 越界判断
if(position < 0 || position >= this.length) return null
// 2 获取元素
var current = this.head
var index = 0
// this.length / 2 > position 从头向后遍历
// this.length / 2 < position 从后向前遍历
while(index++ < position){
current = current.next
}
return current.data
}
// 5 indexOf 方法
DoublyLinkedList.prototype.indexOf = function(data){
// 定义变量
var current = this.head
var index = 0
while(current){
if(current.data == data){
return index
}
current = current.next
index += 1
}
return -1
}
// 6 update 方法
DoublyLinkedList.prototype.update = function(position,newData){
// 越界判断
if(position < 0 ||position >= this.lenght) return false
// 查找节点
var current = this.head
var index = 0
while(index++ < position){
current = current.next
}
// 3 修改找到节点的data信息
current.data = newData
return true
}
// 7 removeAt 方法
DoublyLinkedList.prototype.removeAt = function(position){
// 1 越界判断
if(position < 0 ||position >= this.lenght) return null
var current = this.head
// 2 判断是否只有一个节点
if(this.length == 1){
this.head = null
this.tail = null
}else {
if(position == 0){ // 判断是否删除的是第一个节点
this.head.next.prev = null
this.head = this.head.next
}else if (position == this.lenght - 1){ // 判断是否删除的是最后一个节点
current = this.tail
this.tail.prev.next = null
this.tail = this.tail.prev
}else{
var index = 0
while(index++ < position){
current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev
}
// 3 lenght -1
this.length -=1
return current.data
}
}
// 8 remove 方法
DoublyLinkedList.prototype.remove = function(data){
// 1 根据 data 获取下标值
var index = this.indexOf(data)
// 2 根据 index 删除对应位置的节点
return this.removeAt(index)
}
// 9 isEmpty 方法
DoublyLinkedList.prototype.isEmpty = function(){
return this.length == 0
}
// 10 size 方法
DoublyLinkedList.prototype.size = function(){
return this.length
}
// 11 获取链表的第一个元素
DoublyLinkedList.prototype.getHead = function(){
return this.head.data
}
// 12 获取最后一元素
DoublyLinkedList.prototype.getTail = function(){
return this.tail.data
}
}
const list = new DoublyLinkedList()
// 1 测试添加
list.append(‘abc‘)
list.append(‘cba‘)
list.append(‘nba‘)
// console.log(list)
// 2 测试转成字符串
// console.log(list)
// console.log(list.forwardString())
// console.log(list.backwardString())
// 3 测试 insert
// list.insert(0,‘aaa‘)
// list.insert(4,‘bbb‘)
// list.insert(2,‘ccc‘)
// console.log(list)
// 4 测试 get 方法
// console.log(list.get(0))
// console.log(list.get(2))
// console.log(list.get(5))
// 5 测试 indexOf 方法
// console.log(list.indexOf(‘aaa‘))
// console.log(list.indexOf(‘abc‘))
// console.log(list.indexOf(‘666‘))
// 6 测试 update 方法
// list.update(0,‘num‘)
// list.update(5,‘123‘)
// console.log(list)
// 7 测试 removeAt方法
// console.log(list.removeAt(1))
// console.log(list)
// console.log(list.removeAt(0))
// 8 测试 remove 方法
// console.log(list.remove(‘cba‘))
// console.log(list)
// 9 测试其他方法
console.log(list.isEmpty())
console.log(list.size())
console.log(list.getHead())
console.log(list.getTail())
</script>
</body>
</html>
