双向链表

WARNING

如果对链表不熟悉，请移步上一节，先学习单向链表

简介

双向链表：既可以从头遍历到尾，又可以从尾遍历到头。即链表连接的过程是双向的
实现原理：一个节点既有向前连接的引用，也有一个向后连接的引用

缺点

每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些
相对于单向链表，所占内存空间更大一些
但是，相对于双向链表的便利性而言，这些缺点可以忽略

基本特点

双向链表有两个指针：head 指针指向头部第一个节点，tail 指针指向尾部最后一个节点
每个节点由三部分组成：前一个节点的指针(prev)、保存的数据(item)、后一个节点的指针(next)
双向链表的第一个节点的 prev 指向 null；
双向链表的最后一个节点的 next 指向 null；

结构图例

(1) 横向图例：

doubleLinkList

(2) 纵向图例：

doubleLinkList

常用操作

append(element)：向链表尾部添加一个新的项
insert(position, element)：向链表的特定位置插入一个新的项
get(position)：获取对应位置的元素
indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素就返回-1
update(position, element)：修改某个位置的元素
removeAt(position)：从链表的特定位置移除一项
remove(element)：从链表中移除一项
isEmpty()：如果链表中不包含任何元素，返回 true，如果链表长度大于 0，返回 false
size()：返回链表包含的元素个数，与数组的 length 属性类似
toString()：由于链表项使用了 Node 类，就需要重写继承自 JS 对象默认的 toString 方法，让其只输出元素的值
forwardString()：返回正向遍历节点字符串形式
backwordString()：返回反向遍历的节点的字符串形式

代码实现

0、创建双向链表类

// 创建双向链表的构造函数
function DoubleLinkList() {
	// 内部类：节点类
	function Node(data) {
		this.data = data
		this.prev = null
		this.next = null
	}

	// 属性
	this.head = null // 用于指向第一个节点
	this.tail = null // 用于指向最后一个节点
	this.length = 0 // 记录长度
}

1、toString、forwardString、backwardString 方法

// 1. 将链表转存字符串形式
// 1.1 toString方法-从前往后遍历
DoubleLinkList.prototype.toString = function () {
	return this.backwardString()
}

// 1.2 forwardString方法: 返回向前遍历节点字符串形式
DoubleLinkList.prototype.forwardString = function () {
	// (1) 定义变量
	var current = this.tail
	var resultString = ""

	// (2) 依次向前遍历，获取每一个节点
	while (current) {
		resultString += current.data + " "
		current = current.prev
	}
	return resultString
}

// 2.3 backwardString方法: 返回向后遍历的节点的字符串形式
DoubleLinkList.prototype.backwardString = function () {
	// (1) 定义变量
	var current = this.head
	var resultString = ""

	// (2) 依次向后遍历，获取每一个节点
	while (current) {
		resultString += current.data + " "
		current = current.next
	}
	return resultString
}

2、append 方法

// 2. append方法
DoubleLinkList.prototype.append = function (data) {
	// 2.1 根据元素创建节点
	var newNode = new Node(data)

	// 2、判断是否为第一个节点
	if (this.head == null) {
		// 情况1：添加的是第一个节点
		this.head = newNode
		this.tail = newNode
	} else {
		// 情况2：添加的不是第一个节点
		newNode.prev = this.tail // 新节点prev指向当前最后一个
		this.tail.next = newNode // 当前最后一个节点的next指向新节点
		this.tail = newNode // 改变最后一个节点
	}

	// 2.3 length+1
	this.length++
}

过程详解-情况 1：第一个节点

只需要让 head 和 tail 都指向新节点即可

doubleLinkList

过程详解-情况 2：不是第一个节点

通过：newNode.prev = this.tail：建立指向 1
通过：this.tail.next = newNode：建立指向 2
通过：this.tail = newNode：建立指向 3
注意最后修改 tail 指向，在未修改前 tail 始终指向原链表的最后一个节点

doubleLinkList

测试代码:

// 1.创建双向链表对象
var list = new DoubleLinkList()

// 2.测试append方法：追加元素
list.append("aaa")
list.append("bbb")
list.append("ccc")
console.log(list)

// 3.测试字符串方法
console.log(list.forwardString()) // ccc bbb aaa
console.log(list.backwardString()) // aaa bbb ccc
console.log(list.toString()) // aaa bbb ccc

测试结果:

doubleLinkList

3、insert 方法

// 3. insert方法：向特定位置插入一个新的数据
DoubleLinkList.prototype.insert = function (position, data) {
	// 3.1 边界判断
	if (position < 0 || position > this.length) return false

	// 3.2 根据data创建新的节点
	var newNode = new Node(data)

	// 3.4 判断原来的列表是否为空
	if (this.length == 0) {
		// 情况1：原链表为空，插入的newNode是第一个节点
		this.head = newNode
		this.tail = newNode
	} else {
		// 已有节点分多钟情况
		if (position == 0) {
			// 情况2：position == 0，插入第一个
			this.head.prev = newNode
			newNode.next = this.head
			this.head = newNode
		} else if (position == this.length) {
			// 情况3：position == this.length，插入最后一个
			newNode.prev = this.tail
			this.tail.next = newNode
			this.tail = newNode
		} else {
			// 情况4：0 < position < this.length，插入中间
			var current = this.head
			var index = 0
			while (index++ < position) {
				current = current.next
			}

			// 修改position位置前后节点的指针的指向
			newNode.next = current
			newNode.prev = current.prev
			current.prev.next = newNode
			current.prev = newNode
		}
	}

	// 3.5 length +1
	this.length += 1
	// 返回插入成功
	return true
}

过程详解-当原链表为空时

情况 1：插入的新节点是链表的第一个节点；只需要让 head 和 tail 都指向 newNode 即可

doubleLinkList

过程详解-当原链表不为空时

情况 2：当 position == 0，即在链表的首部添加节点，如下图所示：
1. 首先，通过：this.head.prev = newNode，改变指向 1
2. 然后，通过：newNode.next = this.head，改变指向 2
3. 最后，通过：this.head = newNode，改变指向 3

doubleLinkList

情况 3：position == this.length，即在链表的尾部添加节点，如下图所示：
1. 首先，通过：this.tail.next = newNode，改变指向 1；(注意这里使用 this.tail 指向原链表最后一个节点，而不是 this.head。因为当 length>1 时，this.head != this.tail)
2. 然后，通过：newNode.prev = this.tail，改变指向 2
3. 最后，通过：this.tail = newNode，改变指向 3

doubleLinkList

情况 4：0 < position < this.length，即在链表的中间插入新节点，假设在 position = 1 的位置插入，如下图所示：
1. newNode.next = current，改变指向 1
2. newNode.prev = current.prev，改变指向 2
3. current.prev.next = newNode，改变指向 3
4. current.prev = current，改变指向 4，(注意必须最后才修改 current.prev 的指向，不然就无法通过 current.prev 获取需要操作的 Node1 了)

doubleLinkList

测试代码:

// 已有：aaa bbb ccc
list.insert(0, "100") // 首部插入
list.insert(2, "200") // 中间插入
list.insert(5, "300") // 尾部插入
console.log(list.toString()) // 100 aaa 200 bbb ccc 300

4、get 方法

// 4. get方法：获取对应位置的元素
DoubleLinkList.prototype.get = function (position) {
	// 4.1 越界判断
	if (position < 0 || position >= this.length) return null

	// 4.2 获取元素
	/* 
		方法一：一次查找，效率不是很高 
		var current = this.head
		var index = 0
		while (index++ < position) {
			current = current.next
		}
	*/

	/* 方法二：二分查找 */
	var current = null
	var index = 0
	// this.length / 2 > position：从头开始遍历
	if (this.length / 2 > position) {
		current = this.head
		while (index++ < position) {
			current = current.next
		}
	} else {
		// this.length / 2 <= position: 从尾开始遍历
		current = this.tail
		index = this.length - 1
		while (index-- > position) {
			current = current.prev
		}
	}

	// 4.3 返回对应data
	return current.data
}

过程详解

方法一：效率一般：定义两个变量 current 和 index，通过 while 循环遍历分别获取当前的节点和对应的索引值 index，一直找到需要获取的 position 位置的最后一个节点，此时 index = pos = x，然后 return current.data 即可
方法二：二分查找，效率高：通过 this.length / 2 与 position 的大小来判断
1. 如果 this.length / 2 > position：从头（head）开始遍历
2. 如果 this.length / 2 < position：从尾（tail）开始遍历

doubleLinkList

测试代码

// 已有：100 aaa 200 bbb ccc 300
console.log(list.get(0)) // 100
console.log(list.get(2)) // 200
console.log(list.get(5)) // 300

5、indexOf 方法

// 5. indexOf方法：返回元素在列表中的索引，如果列表中没有该元素则返回-1
DoubleLinkList.prototype.indexOf = function (data) {
	// 5.1 定义变量
	var current = this.head
	var index = 0
	// 5.2 查找和data相同的节点
	while (current) {
		if (current.data == data) {
			return index
		}
		current = current.next
		index += 1
	}
	// 5.3 查找到最后也没找到对应的元素，返回-1
	return -1
}

过程详解

以（current）作为条件，通过 while 循环遍历链表中的所有节点（停止条件为 current = null）。在遍历每个节点时将 current 指向的当前节点的 data 和传入的 data 进行比较即可

测试代码

// 已有：100 aaa 200 bbb ccc 300
console.log(list.indexOf("100")) // 0
console.log(list.indexOf("200")) // 2
console.log(list.indexOf("300")) // 5

6、update 方法

// 6. update方法：修改某个位置的元素
DoubleLinkList.prototype.update = function (position, newData) {
	// 6.1 越界判断
	if (position < 0 || position >= this.length) return false

	// 6.2 查找正确的节点
	var current = this.head
	var index = 0
	// 这里使用依次循环遍历，也可以使用二分查找
	while (index++ < position) {
		current = current.next
	}

	// 6.3 修改找到节点的data信息
	current.data = newData
	return true
}

测试代码

// 已有：100 aaa 200 bbb ccc 300
list.update(0, "mmm")
list.update(2, "nnn")
console.log(list.toString()) // mmm aaa nnn bbb ccc 300

7、removeAt 方法

// 7. removeAt方法：从特定位置移除一项
DoubleLinkList.prototype.removeAt = function (position) {
	// 7.1 越界判断
	if (position < 0 || position >= this.length) return null

	// 7.2 判断是否只有一个节点

	// 定义在最上面方便以下各种情况返回current.data
	var current = this.head
	if (this.length === 1) {
		// 情况1：表只有一个节点
		this.head = null
		this.tail = null
	} else {
		// 链表节点不止一个的情况
		if (position === 0) {
			// 情况2：删除第一个节点
			this.head.next.prev = null
			this.head = this.head.next
		} else if (position === this.length - 1) {
			// 情况3：删除最后一个节点
			// 先获取引用，该情况下返回被删除的最后一个节点
			current = this.tail
			// 再改变指针
			this.tail.prev.next = null
			this.tail = this.tail.prev
		} else {
			// 情况4：删除链表中间的节点
			var index = 0
			while (index++ < position) {
				current = current.next
			}
			current.prev.next = current.next
			current.next.prev = current.prev
		}
	}

	// 7.3 length - 1
	this.length -= 1
	// 7.4 返回被删除节点的数据
	return current.data
}

过程详解-当链表的 length = 1 时

情况 1：删除链表中的所有节点：只需要让链表的 head 和 tail 指向 null 即可

doubleLinkList

过程详解-当链表的 length > 1 时

情况 2：删除链表中的第一个节点
1. 首先，this.head.next.prev = null，改变指向 1
2. 然后，this.head = this.head.next，改变指向 2
3. 注意：虽然 Node1 有引用指向其它节点，但是没有引用指向 Node1，那么 Node1 会被自动回收

doubleLinkList

情况 3：删除链表中的最后一个节点
1. 首先，this.tail.prev.next = null，修改指向 1
2. 然后，this.tail = this.tail.prev，修改指向 2

doubleLinkList

情况 4：删除链表中间的节点
1. 通过 while 循环找到需要删除的节点，比如 position = x，那么需要删除的节点就是 Node(x+1)，如下图所示：
2. 通过：current.next.prev = current.prev，修改指向 1
3. 通过：current.prev.next = current.next，修改指向 2
4. 这样就没有引用指向 Node(x+1)了（current 虽指向 Node(x+1)，但 current 时临时变量，该方法执行完就会被销毁），随后 Node(x+1)就会被自动删除

doubleLinkList

测试代码

// 已有：mmm aaa nnn bbb ccc 300
console.log(list.removeAt(0)) // mmm
console.log(list.toString()) // aaa nnn bbb ccc 300

// 已有：aaa nnn bbb ccc 300
console.log(list.removeAt(3)) // ccc
console.log(list.toString()) // aaa nnn bbb 300

8、remove|isEmpty|size 方法

// 8. remove方法：从列表移除一项
DoubleLinkList.prototype.remove = function (data) {
	// 8.1 根据data获取下标值
	var index = this.indexOf(data)
	// 8.2 根据index 删除对应位置的节点
	return this.removeAt(index)
}

// 9. isEmpty方法：为空返回true，不为空返回false
DoubleLinkList.prototype.isEmpty = function () {
	return this.length === 0
}

// 10. size方法：返回节点个数
DoubleLinkList.prototype.size = function () {
	return this.length
}

测试代码

// 8. 测试remove方法
// 已有：aaa nnn bbb 300
console.log(list.remove("nnn")) // nnn
console.log(list.toString()) // aaa bbb 300

// 已有：aaa bbb 300
// 9. 测试isEmpty方法
console.log(list.isEmpty()) // false
// 10. 测试size方法
console.log(list.size()) // 3

9、getHead|getTail 方法

// 11. 获取链表的第一个元素
DoubleLinkList.prototype.getHead = function () {
	return this.head.data
}

// 12. 获取链表的最后一个元素
DoubleLinkList.prototype.getTail = function () {
	return this.tail.data
}

测试代码

// 已有：aaa bbb 300
// 11. 测试getHead方法
console.log(list.getHead()) // aaa
// 12. 测试getTead方法
console.log(list.getTail()) // 300

10、完整代码

// 创建双向链表的构造函数
function DoubleLinkList() {
	// 内部类：节点类
	function Node(data) {
		this.data = data
		this.prev = null
		this.next = null
	}

	// 属性
	this.head = null // 用于指向第一个节点
	this.tail = null // 用于指向最后一个节点
	this.length = 0 // 记录长度

	/* 常见方法 */
	// 1. 将链表转存字符串形式
	// 1.1 toString方法-从前往后遍历
	DoubleLinkList.prototype.toString = function () {
		return this.backwardString()
	}

	// 1.2 forwardString方法: 返回向前遍历节点字符串形式
	DoubleLinkList.prototype.forwardString = function () {
		// (1) 定义变量
		var current = this.tail
		var resultString = ""

		// (2) 依次向前遍历，获取每一个节点
		while (current) {
			resultString += current.data + " "
			current = current.prev
		}
		return resultString
	}

	// 2.3 backwardString方法: 返回向后遍历的节点的字符串形式
	DoubleLinkList.prototype.backwardString = function () {
		// (1) 定义变量
		var current = this.head
		var resultString = ""

		// (2) 依次向后遍历，获取每一个节点
		while (current) {
			resultString += current.data + " "
			current = current.next
		}
		return resultString
	}

	// 2. append方法
	DoubleLinkList.prototype.append = function (data) {
		// 2.1 根据元素创建节点
		var newNode = new Node(data)

		// 2、判断是否为第一个节点
		if (this.head == null) {
			// 情况1：添加的是第一个节点
			this.head = newNode
			this.tail = newNode
		} else {
			// 情况2：添加的不是第一个节点
			newNode.prev = this.tail // 新节点prev指向当前最后一个
			this.tail.next = newNode // 当前最后一个节点的next指向新节点
			this.tail = newNode // 改变最后一个节点
		}

		// 2.3 length+1
		this.length++
	}

	// 3. insert方法：向特定位置插入一个新的数据
	DoubleLinkList.prototype.insert = function (position, data) {
		// 3.1 边界判断
		if (position < 0 || position > this.length) return false

		// 3.2 根据data创建新的节点
		var newNode = new Node(data)

		// 3.4 判断原来的列表是否为空
		if (this.length == 0) {
			// 情况1：原链表为空，插入的newNode是第一个节点
			this.head = newNode
			this.tail = newNode
		} else {
			// 已有节点分多钟情况
			if (position == 0) {
				// 情况2：position == 0，插入第一个
				this.head.prev = newNode
				newNode.next = this.head
				this.head = newNode
			} else if (position == this.length) {
				// 情况3：position == this.length，插入最后一个
				newNode.prev = this.tail
				this.tail.next = newNode
				this.tail = newNode
			} else {
				// 情况4：0 < position < this.length，插入中间
				var current = this.head
				var index = 0
				while (index++ < position) {
					current = current.next
				}

				// 修改position位置前后节点的指针的指向
				newNode.next = current
				newNode.prev = current.prev
				current.prev.next = newNode
				current.prev = newNode
			}
		}

		// 3.5 length +1
		this.length += 1
		// 返回插入成功
		return true
	}

	// 4. get方法：获取对应位置的元素
	DoubleLinkList.prototype.get = function (position) {
		// 4.1 越界判断
		if (position < 0 || position >= this.length) return null

		// 4.2 获取元素
		/*
						方法一：一次查找，效率不是很高
						var current = this.head
						var index = 0
						while (index++ < position) {
							current = current.next
						}
					*/

		/* 方法二：二分查找 */
		var current = null
		var index = 0
		// this.length / 2 > position：从头开始遍历
		if (this.length / 2 > position) {
			current = this.head
			while (index++ < position) {
				current = current.next
			}
		} else {
			// this.length / 2 <= position: 从尾开始遍历
			current = this.tail
			index = this.length - 1
			while (index-- > position) {
				current = current.prev
			}
		}

		// 4.3 返回对应data
		return current.data
	}

	// 5. indexOf方法：返回元素在列表中的索引，如果列表中没有该元素则返回-1
	DoubleLinkList.prototype.indexOf = function (data) {
		// 5.1 定义变量
		var current = this.head
		var index = 0
		// 5.2 查找和data相同的节点
		while (current) {
			if (current.data == data) {
				return index
			}
			current = current.next
			index += 1
		}
		// 5.3 查找到最后也没找到对应的元素，返回-1
		return -1
	}

	// 6. update方法：修改某个位置的元素
	DoubleLinkList.prototype.update = function (position, newData) {
		// 6.1 越界判断
		if (position < 0 || position >= this.length) return false

		// 6.2 查找正确的节点
		var current = this.head
		var index = 0
		// 这里使用依次循环遍历，也可以使用二分查找
		while (index++ < position) {
			current = current.next
		}

		// 6.3 修改找到节点的data信息
		current.data = newData
		return true
	}

	// 7. removeAt方法：从特定位置移除一项
	DoubleLinkList.prototype.removeAt = function (position) {
		// 7.1 越界判断
		if (position < 0 || position >= this.length) return null

		// 7.2 判断是否只有一个节点

		// 定义在最上面方便以下各种情况返回current.data
		var current = this.head
		if (this.length === 1) {
			// 情况1：表只有一个节点
			this.head = null
			this.tail = null
		} else {
			// 链表节点不止一个的情况
			if (position === 0) {
				// 情况2：删除第一个节点
				this.head.next.prev = null
				this.head = this.head.next
			} else if (position === this.length - 1) {
				// 情况3：删除最后一个节点
				// 先获取引用，该情况下返回被删除的最后一个节点
				current = this.tail
				// 再改变指针
				this.tail.prev.next = null
				this.tail = this.tail.prev
			} else {
				// 情况4：删除链表中间的节点
				var index = 0
				while (index++ < position) {
					current = current.next
				}
				current.prev.next = current.next
				current.next.prev = current.prev
			}
		}

		// 7.3 length - 1
		this.length -= 1
		// 7.4 返回被删除节点的数据
		return current.data
	}

	// 8. remove方法：从列表移除一项
	DoubleLinkList.prototype.remove = function (data) {
		// 8.1 根据data获取下标值
		var index = this.indexOf(data)
		// 8.2 根据index 删除对应位置的节点
		return this.removeAt(index)
	}

	// 9. isEmpty方法：为空返回true，不为空返回false
	DoubleLinkList.prototype.isEmpty = function () {
		return this.length === 0
	}

	// 10. size方法：返回节点个数
	DoubleLinkList.prototype.size = function () {
		return this.length
	}

	// 11. 获取链表的第一个元素
	DoubleLinkList.prototype.getHead = function () {
		return this.head.data
	}

	// 12. 获取链表的最后一个元素
	DoubleLinkList.prototype.getTail = function () {
		return this.tail.data
	}
}

// 0.创建双向链表对象
var list = new DoubleLinkList()

// 1.测试append方法：追加元素
list.append("aaa")
list.append("bbb")
list.append("ccc")
console.log(list)

// 2.测试字符串方法
console.log(list.forwardString()) // ccc bbb aaa
console.log(list.backwardString()) // aaa bbb ccc
console.log(list.toString()) // aaa bbb ccc

// 3.insert方法测试
// 已有：aaa bbb ccc
list.insert(0, "100") // 首部插入
list.insert(2, "200") // 中间插入
list.insert(5, "300") // 尾部插入
console.log(list.toString()) // 100 aaa 200 bbb ccc 300

// 4.get方法测试
// 已有：100 aaa 200 bbb ccc 300
console.log(list.get(0)) // 100
console.log(list.get(2)) // 200
console.log(list.get(5)) // 300

// 5.indexOf方法测试
// 已有：100 aaa 200 bbb ccc 300
console.log(list.indexOf("100")) // 0
console.log(list.indexOf("200")) // 2
console.log(list.indexOf("300")) // 5

// 6. 测试update方法
// 已有：100 aaa 200 bbb ccc 300
list.update(0, "mmm")
list.update(2, "nnn")
console.log(list.toString()) // mmm aaa nnn bbb ccc 300

// 7. 测试removeAt方法
// 已有：mmm aaa nnn bbb ccc 300
console.log(list.removeAt(0)) // mmm
console.log(list.toString()) // aaa nnn bbb ccc 300

// 已有：aaa nnn bbb ccc 300
console.log(list.removeAt(3)) // ccc
console.log(list.toString()) // aaa nnn bbb 300

// 8. 测试remove方法
// 已有：aaa nnn bbb 300
console.log(list.remove("nnn")) // nnn
console.log(list.toString()) // aaa bbb 300

// 已有：aaa bbb 300
// 9. 测试isEmpty方法
console.log(list.isEmpty()) // false
// 10. 测试size方法
console.log(list.size()) // 3
// 11. 测试getHead方法
console.log(list.getHead()) // aaa
// 12. 测试getTead方法
console.log(list.getTail()) // 300

# 双向链表

# 简介

# 缺点

# 基本特点

# 结构图例

# 常用操作

# 代码实现

# 0、创建双向链表类

# 1、toString、forwardString、backwardString 方法

# 2、append 方法

# 3、insert 方法

# 4、get 方法

# 5、indexOf 方法

# 6、update 方法

# 7、removeAt 方法

# 8、remove|isEmpty|size 方法

# 9、getHead|getTail 方法

# 10、完整代码

双向链表

简介

缺点

基本特点

结构图例

常用操作

代码实现

0、创建双向链表类

1、toString、forwardString、backwardString 方法

2、append 方法

3、insert 方法

4、get 方法

5、indexOf 方法

6、update 方法

7、removeAt 方法

8、remove|isEmpty|size 方法

9、getHead|getTail 方法

10、完整代码