单向链表

链表类

先创建单向链表类 LinkedList , 并像其添加属性和方法

class LinkedList {
	// 链表长度，静态属性
	length = 0

	// head 初始化为 null,默认指向 第一个节点
	head = null

	// 内部节点类，用于创建节点
	Node = class {
		constructor(data) {
			this.data = data
			this.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(): 由于列表项使用了Node类，就需要重写继承自JavaScript 对象默认的 toString方法，让其只输出元素的值

append 方法

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

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

链表为空-添加数据

链表不为空-添加数据

// 添加元素
append(data) {
	// 1.创建新节点
	const newNode = new this.Node(data)
	// 2.判断是否添加的是第一个节点
	if (this.length === 0) {
		// 长度为0 ，只有head
		this.head = newNode
	} else {
		// 用一个变量指向 head
		let currentNode = this.head
		// 不停的查找，谁的next为空，即为最后一个节点，
		while (currentNode.next) {
			currentNode = currentNode.next // 不停的移动currentNode
		}
		currentNode.next = newNode // 最后一个节点的next 指向新节点
	}

	// 3.更新长度
	this.length += 1
}

append 追加新节点

测试append

let list = new LinkedList()
// 测试append
list.append('a')
list.append('b')
list.append('c')
console.log(list)

append 追加新节点

toString 方法

• 从 head 开始获取每一个元素
• 循环遍历每一个节点，取出其中的element，拼接成字符串并返回

// 2.toString 方法
toString() {
	let listString = ''
	let current = this.head
	while (current) {
		listString += current.data + ''
		// 移动指针
		current = current.next
	}
	return listString
}

insert 方法

在任意位置插入数据。

添加到第一个位置

添加到第一个位置，表示新添加的节点是头，就需要将原来的头节点，作为新的节点的next， 另外这个时候的 head 应该指向新节点。

第一个位置插入数据

第一个位置插入数据

添加到其他位置

如果是添加到其他位置，就需要先找到这个节点位置， 通过while循环，一点点向下找，并且在这个过程中保存上一个节点和下一个节点。 找到正确的位置后，将新节点的next指向下一个节点，将上一个节点的next指向新的节点。

添加到其他位置

找到位置并添加

  // 3.insert方法
insert(position, data) {
	// 3-1 对position 进行越界判断 position不小于0， 也不能比length大很多
	if (position < 0 || position > this.length) {
		return false
	}

	// 3-2.根据data创建节点
	const newNode = new this.Node(data)

	// 3-3.判断插入的位置是否为0
	if (position === 0) {
		// 原来的第一个即为 this.head, 先将原来第一个节点指向newNode的next
		newNode.next = this.head // 第一步 先讲newNode和一个数据关联
		this.head = newNode // 第二步，在将this.head 指向newNode
	} else {
		let index = 0 // 不停的位移
		let current = this.head // 当前节点初始化为 head
		let previous = null // head 的 上一节点为 null
		// ++index 先运算在赋值
		// index++ 先赋值在运算
		// 在 0 ~ position 之间遍历，不断地更新 current 和 previous
		while (index++ < position) {
			previous = current
			// 更新current 直到找到对应位置。不停的移动current
			current = current.next
		}
		// index++ 找到对应位置了
		newNode.next = current // 第一步
		previous.next = newNode // 第二步
	}
	// 更新length
	this.length += 1
	return true
}

// 测试 insert
list.insert(2, '99')
console.log(list, '测试insert')

get 方法

返回当前position的数据

// 4.get 获取数据方法
get(position) {
	// 4-1.越界判断
	if (position < 0 || position >= this.length) {
		return null
	}
	// 2.获取对应的节点
	let current = this.head
	let index = 0
	// 将current 不断的往后移动
	// 假如要找 position = 2情况
	// index = 0 小于 2 current = 更新
	// index = 1 小于 2 current = 更新
	// index = 2 不小于 2 跳出 while循环 此时 current 即为 position
	while (index++ < position) {
		current = current.next
	}

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

	return current.data
}

indexOf 方法

查找索引

// 5.indexOf 方法
indexOf(data) {
	let current = this.head
	let index = 0

	// 开始查找
	while (current) {
		if (current.data === data) {
			return index
		}
		// 更新并移动 current 和 index
		current = current.next
		index += 1

	}
	// 找不到返回 -1
	return -1
}

update 方法

// 6.update 方法
update(position, newData) {
	//	和 get 有点儿类似
	// 6-1.越界判断
	if (position < 0 || position >= this.length) {
		return false
	}
	// 6-2.查找正确的节点
	let current = this.head
	let index = 0
	while (index++ < position) {
		current = current.next
	}
	// 6-3.将 position 位置的 node 的 data 修改成 newData
	current.data = newData
	return true
}

removeAt 方法

// 7.removeAt 方法
removeAt(position) {
	// 7-1.越界判断
	if (position < 0 || position >= this.length) {
		return null
	}
	// 7-2.判断是否删除的是第一个节点
	let current = this.head
	if (position === 0) {
		// 如果是第一个，即 修改 head 的指向
		this.head = this.head.next
	} else {
		// 让删除的前一个的next等于删除的下一个next
		let index = 0

		let previous = null
		while (index++ < position) {
			// 移动 current 和 previous
			previous = current
			current = current.next
		}
		// 让前一个节点的next 指向current的next即可
		previous.next = current.next
	}

	// 长度减1
	this.length -= 1

	// 返回删除的当前节点
	return current.data
}

remove 方法

// 8.remove 方法
remove(data) {
	// 8-1.根据data先获取在列表中的位置
	let position = this.indexOf(data)
	// 8-2.根据位置信息删除节点
	return this.removeAt(position)
}

isEmpty 方法

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

size 方法

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

完整代码