双向链表

单向链表和双向链表对比

单向链表

• 只能从头遍历到尾或者从尾遍历到头
• 链表相连的过程是单向的，实现的原理是上一个元素中有一个指向下一个的引用
• 比较明显的缺点，可以轻松到达下一个节点，但是回到前一个节点是很难的，但是在实际开发中，经常会遇到回到上一个节点的情况。

举例：

假设一个文本编辑用链表来存储文本，每一行用一个String对象存储在链表的一个节点中，当编辑器用户向下移动光标时， 链表直接操作到下一个节点即可，但是当用户将光标向上移动呢，这个时候为了回到上一个节点，可能需要从first开始， 依次走到想要的节点上。

双向链表

• 既可以从头遍历到尾，又可以从尾遍历到头
• 节点相连的过程是双向的，实现的原理是上一个节点既有前连接的引用，也有一个向后连接的引用
• 双向链表可以有效的解决单向链表中提到的问题

双向链表的特点

• 缺点就是每次在插入或删除某个节点时，需要处理四个引用，而不是两个，实现起来要困难些
• 可以使用一个head和一个tail分别指向头部和尾部节点
• 每个节点都有三部分组成：前一个节点的指针（prev）, 保存的元素（item）, 后一个节点的指针（next）
• 双向链表的第一个节点的prev是null, 最后的节点的next是null

常见方法

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

append 方法

向链表尾部添加数据可能有两种情况：

• 链表本身为空，新添加的数据是唯一的节点
• 链表不为空，需要向其他节点后面追加节点

append 第一个节点

append 非第一个节点

// 1.append 方法
append(data) {
	// 1-1.根据data创建节点
	let newNode = new this.Node(data)

	// 1-2.判断是否添加的是第一个节点
	if (this.length === 0) {
		this.head = newNode
		this.tail = newNode
	} else {
		// 注意！！不用通过循环找到最后一个节点，和单向链表不同之处

		newNode.prev = this.tail
		this.tail.next = newNode
		this.tail = newNode
	}
	// 1-3.length + 1
	this.length += 1
}

toString 方法

将链表转成字符串形式

  // 2.1 toString
  DoublyLinkedList.prototype.toString = function () {
    return this.forwardString()
  }

forwardString 方法

// 3.forwardString   链表数据从前往后以字符串形式返回  由前向后遍历
forwardString () {
	// 3-1.定义变量
	let current = this.head
	let resultString = ''
	// 3-2.依次向后遍历，获取每个节点
	while (current) {
		resultString += current.data + ' '
		current = current.next
	}
	return resultString
}

backwardString 方法

// 4.backwardString 链表数据从后往前以字符串形式返回
// 由后向前遍历
backwardString () {
	// 4-1.定义变量
	let current = this.tail
	let resultString = ''

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

insert 方法

链表为空情况

链表为空情况插入一个节点

if (this.length === 0) {
    // 第一种情况 链表为空
    this.head = newNode
    this.tail = newNode
}

链表为空情况插入一个节点

链表不为空 放在第一位

链表不为空，position = 0

// 5-3-2 第二种情况 判断 position 是否为 0
if (position == 0) {
    // 原来的第一个节点的 prev = newNode
    // newNode.next = 原来的第一个节点
    this.head.prev = newNode // 第一步
    newNode.next = this.head // 第二步
    this.head = newNode // 第三步
}

测试 insert position = 0

链表不为空，放在最后一位

insert 在最后

if (position == this.length) {
    // 5-3-3 最后一个节点 和append 实现一样
    // newNode.prev  = 原来的最后一个节点
    newNode.prev = this.tail
    this.tail.next = newNode
    // 改变最后一个指针
    this.tail = newNode
}

insert 在最后测试

链表不为空 放在非0，非最后的其他位置

insert 非0 非 length 的其他位置

// 其他情况
let current = this.head
let index = 0
while (index++ < position) {
    current = current.next
}
// 修改指针
newNode.next = current
newNode.prev = current.prev
current.prev.next = newNode
// 注意此处，最后修改
current.prev = newNode

insert 非0 非 length 的其他位置

// 5.insert 方法
insert(position, data) {
	// 5-1.越界判断
	if (position < 0 || position > this.length) {
		return false
	}
	// 5-2.根据data创建新的节点
	let newNode = new this.Node(data)
	// 5-3.判断原来的列表是否为空
	if (this.length === 0) {
		// 5-3-1 第一种情况 链表为空
		this.head = newNode
		this.tail = newNode
	} else {
		// 5-3-2 第二种情况 判断 position 是否为 0
		if (position == 0) {
			// 原来的第一个节点的 prev = newNode
			// newNode.next = 原来的第一个节点
			this.head.prev = newNode
			newNode.next = this.head
			this.head = newNode
		} else if (position == this.length) {
			// 5-3-3 最后一个节点 和append 实现一样
			// newNode.prev  = 原来的最后一个节点
			newNode.prev = this.tail
			this.tail.next = newNode
			// 改变最后一个指针
			this.tail = newNode
		} else {
			// 5-3-4 其他情况
			let current = this.head
			let index = 0
			while (index++ < position) {
				current = current.next
			}
			// 修改指针
			newNode.next = current
			newNode.prev = current.prev
			current.prev.next = newNode
			// 注意此处，最后修改
			current.prev = newNode
		}
	}
	// length + 1
	this.length += 1
	return true
}

get 方法

// 6.get 方法
get(position) {
	// 6-1.越界判断
	if (position < 0 || position >= this.length) {
		return null
	}
	// TODO:
	// this.length / 2 > position 从头向后遍历
	// this.length / 2 < position 从后向前遍历
	// 6-2.获取元素
	let current = this.head
	let index = 0
	while (index++ < position) {
		current = current.next
	}
	return current.data
}

indexOf 方法

// 7.indexOf 方法
indexOf(data) {
	// 7-1.定义变量
	let current = this.head
	let index = 0

	// 7-2.查找和data相同的节点
	while (current) {
		if (current.data === data) {
			return index
		}
		current = current.next
		index += 1
	}
	return -1
}

update 方法

和get 方法类似，get是找到，然后返回当前，update 则是找到并更新

// 8.update 方法
update(position, newData) {
	// 8-1.越界判断
	if (position < 0 || position >= this.length) {
		return false
	}

	// 8-2.寻找正确的节点

	let current = this.head
	let index = 0

	while (index++ < position) {
		current = current.next
	}

	// 8-3.修改找到的节点
	current.data = newData

	return true
}

removeAt 方法

链表只有一个值的时候，即 length = 1

length = 1

// 9-2.判断情况
if (this.length === 1) {
    // 9-2.1.是否只有一个节点
    this.head = null
    this.tail = null
}

length = 1

链表长度不为1 ，删除第1位置的元素

链表长度不为1，删除第一个节点

// 9-2.2.删除第一个节点
if (position == 0) {
    // 虽然被删除的节点有指向别人，但是没有任何引用指向被删除的节点，被删除的节点会被回收
    this.head.next.prev = null
    this.head = this.head.next
}

链表长度不为1，删除第一个节点

链表长度不为1 ，删除最后一个元素

链表长度不为1，删除最后一个节点

if (position == this.length - 1) {
    // 先拿到最后一个节点的前一个节点，修改其next 指向 null
    // 修改 tail的指向
    current = this.tail // 用于返回删除的数据
    this.tail.prev.next = null
    this.tail = this.tail.prev
}

链表长度不为1，删除最后一个节点

链表长度不为1， 删除非第一个，非最后一个的其他位置的元素

链表长度不为1，删除中间某个节点

let index = 0
while (index++ < position) {
    current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev

链表长度不为1，删除中间某个节点

// 9.removeAt 方法
removeAt(position) {
	// 9-1.边界判断
	if (position < 0 || position >= this.length) {
		return null
	}


	let current = this.head

	// 9-2.判断情况
	if (this.length === 1) {
		// 9-2.1.是否只有一个节点
		this.head = null
		this.tail = null
	} else {
		// 9-2.2.删除第一个节点
		if (position == 0) {
			// 虽然被删除的节点有指向别人，但是没有任何引用指向被删除的节点，被删除的节点会被回收
			this.head.next.prev = null
			this.head = this.head.next
		} else if (position == this.length - 1) {
			// 先拿到最后一个节点的前一个节点，修改其next 指向 null
			// 修改 tail的指向
			current = this.tail // 用于返回删除的数据
			this.tail.prev.next = null
			this.tail = this.tail.prev
		} else {
			let index = 0
			while (index++ < position) {
				current = current.next
			}
			current.prev.next = current.next
			current.next.prev = current.prev
		}
	}


	// 9-3.length - 1
	this.length -= 1
	return current.data
}

remove 方法

// 10.remove 方法
remove(data) {
	// 10-1.根据data获取下标值
	let index = this.indexOf(data)
	// 10-2.根据index删除对应位置的节点
	return this.removeAt(index)
}

其他方法

// 11.isEmpty 方法
isEmpty() {
	return this.length === 0
}

// 12.size 方法
size() {
	return this.length
}

// 13.getHead 方法
getHead() {
	return this.head.data
}

// 14.getTail 方法
getTail() {
	return this.tail.data
}

完整代码实现