单向链表

TIP

链表，一种存储数据的线性结构，分为单向链表和双向链表

链表和数组优缺点对比

数组的缺点：

数组的创建通常需要申请一段连续的内存空间（一整块内存），并且大小是固定的
如果原数组不能满足容量需求时，需要扩容（一般是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去）
在数组的开头或中间位置插入数据的成本很高，需要进行大量元素的位移

链表的优势：

内存空间不必是连续的，元素可以任意放置，可以充分利用计算机的内存，实现灵活的内存动态管理
链表不必在创建时就确定大小，并且大小可以无限地延伸下去
链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多

链表的缺点：

链表访问任何一个位置的元素时，都需要从头开始访问（无法跳过第一个元素访问任何一个元素）
无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素

基本特点

每个节点包含 item(data) 数据和 next 指针
head 属性指向链表的第一个节点
链表中的最后一个节点指向 null
当链表中一个节点也没有的时候，head 直接指向 null

结构图例

linkList

位置图例

position 的值一般表示 position 所指位置的下一个节点。当 position 的值与 index 的值相等时，比如 position = index = 1，那么它们都表示 Node2。

linkList

常用操作

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 方法，让其只输出元素的值

代码实现

0、创建单向链表类

// 封装链表类
function LinkList() {
	// 封装一个内部类：节点类(data:数据)
	function Node(data) {
		this.data = data // 数据
		this.next = null // 下一个指针引用
	}

	/* 属性 */
	// 属性head指向链表的第一个节点，默认为null
	this.head = null
	// 记录链表的长度，默认为0
	this.length = 0
}

1、toString 方法

// 1 toString(): 转化字符串方法
LinkList.prototype.toString = function(data) {
	// 1.1 定义变量
	var current = this.head
	var resultString = ""

	// 1.2 通过while循环获取一个一个节点
	while (current) {
		resultString += current.data + " "
		// 拼接完一个节点数据之后，让current指向下一个节点
		current = current.next
	}

	// 1.3 返回字符串
	return resultString
}

2、append 方法

// 2. append(): 向尾部添加一个数据
LinkList.prototype.append = function(data) {
	// 2.1 创建新节点
	var newNode = new Node(data)

	// 2.2 判断添加的是否是第一个节点
	if (this.length === 0) {
		// 是第一个节点，直接指向新节点
		this.head = newNode
	} else {
		// 不是第一个节点，让current先指向第一个节点
		var current = this.head
		// 通过while循环查找，直到current.next为null停止循环，找到最后一个节点
		while (current.next) {
			current = current.next
		}
		// 最后节点的next指向新的节点
		current.next = newNode
	}

	// 2.3 添加完新结点之后长度+1
	this.length++
}

过程详解：

首先让 current 指向第一个节点 head
通过 while 循环使 current 指向最后一个节点，最后通过 current.next = newNode，让最后一个节点指向新节点 newNode

linkList

测试代码:

var link = new LinkList()
link.append("aaa")
link.append("bbb")
link.append("ccc")

console.log(link.toString()) // aaa bbb ccc
console.log(link)

测试结果:

linkList

3、insert 方法

// 3. insert方法: 向特定位置插入一条新的数据
LinkList.prototype.insert = function(position, data) {
	//理解positon的含义：position=0表示新节点插入后要成为第1个节点，position=2表示新节点插入后要成为第3个节点
	//3.1 对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
	if (position < 0 || position > this.length) {
		return false
	}
	// 3.2 根据data创建新节点newNode
	var newNode = new Node(data)

	// 3.3 判断插入的位置是否是第一个
	if (position === 0) {
		// 情况1：插入位置position=0
		// 让新节点指向第一个节点
		newNode.next = this.head
		// 让head指向新节点
		this.head = newNode
	} else {
		// 情况2：插入位置position > 0(该情况包含position=length)
		var index = 0
		var previous = null
		var current = this.head

		// 步骤1：通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
		while (index++ < position) {
			// 步骤2：让previous指向current当前指向的节点，然后current指向下一个节点
			previous = current
			current = current.next
		}
		// 步骤3：通过变量current，使newNode指向position位置的后一个节点
		newNode.next = current
		// 步骤4：通过变量previous，使position位置的前一个节点指向newNode
		previous.next = newNode

		/*
		启示：
		1.我们无法直接操作链表中的节点，但是可以通过变量指向这些节点，以此间接地操作节点(替身使者)；
		比如current指向节点3，想要节点3指向节点4只需要：current.next = 4即可。
		2.两个节点间是双向的，想要节点2的前一个节点为节点1，可以通过：1.next=2，来实现；
		*/
	}

	// 3.4 新节点插入后要length+1
	this.length += 1
	return true
}

过程详解-情况 1：position = 0

通过：newNode.next = this.head，建立连接 1
通过：this.head = newNode，建立连接 2（不能先建立连接 2，否则 this.head 不再指向 Node1）

linkList

过程详解-情况 2：position > 0

首先定义两个变量 previous 和 current 分别指向需要插入位置 pos = X 的前一个节点 2 和后一个节点 1
然后，通过：newNode.next = current，改变指向 3
最后，通过：previous.next = newNode，改变指向 4

linkList

过程详解-情况 2 特殊情形：position = length 情况 2 也包含了 pos = length 的情况，该情况下 current 和 newNode.next 都指向 null；建立连接 3 和连接 4 的方式与情况 2 相同。

linkList

测试代码:

// 测试insert
link.insert(0, "0a")
link.insert(3, "3b")
link.insert(5, "5c")
console.log(link.toString()) // 0a aaa bbb 3b ccc 5c

4、get 方法

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

	// 4.2 获取指定的positon位置的后一个节点的data
	var current = this.head
	var index = 0
	// 通过while循环，直到index = position，此时curent表示position后一个节点
	while (index++ < position) {
		current = current.next
	}
	// 4.3 返回data数据
	return current.data
}

过程详解

get 方法的实现过程：以获取 position = 2 为例，如下图所示
首先使 current 指向第一个节点，此时 index=0
通过 while 循环使 current 循环指向下一个节点，注意循环终止的条件 index++ < position，即当 index=position 时停止循环，此时循环了 1 次，current 指向第二个节点(Node2)，最后通过 current.data 返回 Node2 节点的数据；

linkList

测试代码

// 已有：0a aaa bbb 3b ccc 5c
console.log(link.get(0)) // 0a
console.log(link.get(3)) // 3b

5、indexOf 方法

// 5. indexOf: 返回元素在列表中的索引，如果列表中没有该元素则返回-1
LinkList.prototype.indexOf = function(data) {
	// 5.1 定义变量
	var index = 0
	var current = this.head
	// 5.2 开始查找: 只要current不指向null就一直循环
	while (current) {
		if (current.data === data) {
			return index
		}
		current = current.next
		index += 1
	}
	// 5.3 找到最后没有找到，返回-1
	return -1
}

过程详解

使用变量 current 记录当前指向的节点，使用变量 index 记录当前节点的索引值（注意 index = node 数-1）

linkList

测试代码

// 已有：0a aaa bbb 3b ccc 5c
console.log(link.indexOf("0a")) // 0
console.log(link.indexOf("3b")) // 3

6、update 方法

// 6. update方法：修改某个位置的元素
LinkList.prototype.update = function(position, newData) {
	// 6.1 越界判断: 因为被修改的节点不能为null，所以position不能等于length
	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位置的后一个节点的data修改成newData
	current.data = newData
	// 6.4 返回true表示修改成功
	return true
}

测试代码

// 已有：0a aaa bbb 3b ccc 5c
link.update(0, "mmm")
link.update(3, "nnn")
console.log(link.toString()) // mmm aaa bbb nnn ccc 5c

7、removeAt 方法

// 7. removeAt: 从特定位置移除一项
LinkList.prototype.removeAt = function(position) {
	// 7.1 越界判断：position不能等于length，因为等于length的节点为null
	if (position < 0 || position >= this.length) {
		return null
	}
	// 7.2 删除元素
	var current = this.head
	if (position === 0) {
		// 情况1：position = 0时(删除第一个节点)
		this.head = this.head.next
	} else {
		// 情况2：position > 0时
		var index = 0
		var previous = null
		while (index++ < position) {
			previous = current
			current = current.next
		}
		// 循环结束后，current指向position后一个节点，previous指向current前一个节点
		// 再使前一个节点的next指向current的next即可
		previous.next = current.next
	}
	// 7.3 length要减1
	this.length -= 1
	// 7.4 返回被删除节点的data，为此current定义在最上面
	return current.data
}

过程详解-情况 1：position = 0

通过：this.head = this.head.next，改变指向 1 即可
虽然 Node1 的 next 仍指向 Node2，但是没有引用指向 Node1，则 Node1 会被垃圾回收器自动回收，所以不用处理 Node1 指向 Node2 的引用 next

linkList

过程详解-情况 2：position > 0

比如 pos = 2 即移除第三个节点（Node3）
首先，定义两个变量 previous 和 curent 分别指向需要删除位置 pos = x 的前一个节点和后一个节点
然后，通过：previous.next = current.next，改变指向 1 即可
随后，没有引用指向 Node3，Node3 就会被自动回收，至此成功删除 Node3

linkList

测试代码

// 已有：mmm aaa bbb nnn ccc 5c
console.log(link.removeAt(0)) // mmm
// 已有：aaa bbb nnn ccc 5c
console.log(link.removeAt(3)) // ccc

8、remove|isEmpty|size 方法

// 8. remove方法：从列表移除一项
LinkList.prototype.remove = function(data) {
	// 8.1 获取data在列表中的位置
	var position = this.indexOf(data)
	// 8.2 根据位置信息删除节点
	return this.removeAt(position)
}

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

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

测试代码

// 已有：aaa bbb nnn 5c
console.log(link.remove("nnn")) // nnn

// 已有：aaa bbb 5c
console.log(link.isEmpty()) // false
console.log(link.size()) // 3

9、完整代码

// 封装链表类
function LinkList() {
	// 封装一个内部类：节点类(data:数据)
	function Node(data) {
		this.data = data // 数据
		this.next = null // 下一个指针引用
	}

	/* 属性 */
	// 属性head指向链表的第一个节点，默认为null
	this.head = null
	// 记录链表的长度，默认为0
	this.length = 0

	// 1 toString(): 转化字符串方法
	LinkList.prototype.toString = function(data) {
		// 1.1 定义变量
		var current = this.head
		var resultString = ""

		// 1.2 通过while循环获取一个一个节点
		while (current) {
			resultString += current.data + " "
			// 拼接完一个节点数据之后，让current指向下一个节点
			current = current.next
		}

		// 1.3 返回字符串
		return resultString
	}

	// 2. append(): 添加方法
	LinkList.prototype.append = function(data) {
		// 2.1 创建新节点
		var newNode = new Node(data)

		// 2.2 判断添加的是否是第一个节点
		if (this.length === 0) {
			// 是第一个节点，直接指向新节点
			this.head = newNode
		} else {
			// 不是第一个节点，让current先指向第一个节点
			var current = this.head
			// 通过while循环查找，直到current.next为null停止循环，找到最后一个节点
			while (current.next) {
				current = current.next
			}
			// 最后节点的next指向新的节点
			current.next = newNode
		}

		// 2.3 添加完新结点之后长度+1
		this.length++
	}

	// 3. insert方法: 向特定位置插入一条新的数据
	LinkList.prototype.insert = function(position, data) {
		//理解positon的含义：position=0表示新节点插入后要成为第1个节点，position=2表示新节点插入后要成为第3个节点
		//3.1 对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
		if (position < 0 || position > this.length) {
			return false
		}
		// 3.2 根据data创建新节点newNode
		var newNode = new Node(data)

		// 3.3 判断插入的位置是否是第一个
		if (position === 0) {
			// 情况1：插入位置position=0
			// 让新节点指向第一个节点
			newNode.next = this.head
			// 让head指向新节点
			this.head = newNode
		} else {
			// 情况2：插入位置position > 0(该情况包含position=length)
			var index = 0
			var previous = null
			var current = this.head

			// 步骤1：通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
			while (index++ < position) {
				// 步骤2：让previous指向current当前指向的节点，然后current指向下一个节点
				previous = current
				current = current.next
			}
			// 步骤3：通过变量current，使newNode指向position位置的后一个节点
			newNode.next = current
			// 步骤4：通过变量previous，使position位置的前一个节点指向newNode
			previous.next = newNode

			/*
			启示：
			1.我们无法直接操作链表中的节点，但是可以通过变量指向这些节点，以此间接地操作节点(替身使者)；
			比如current指向节点3，想要节点3指向节点4只需要：current.next = 4即可。
			2.两个节点间是双向的，想要节点2的前一个节点为节点1，可以通过：1.next=2，来实现；
			*/
		}

		// 3.4 新节点插入后要length+1
		this.length += 1
		return true
	}

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

		// 4.2 获取指定的positon位置的后一个节点的data
		var current = this.head
		var index = 0
		// 通过while循环，直到index = position，此时curent表示position后一个节点
		while (index++ < position) {
			current = current.next
		}
		// 4.3 返回data数据
		return current.data
	}

	// 5. indexOf: 返回元素在列表中的索引，如果列表中没有该元素则返回-1
	LinkList.prototype.indexOf = function(data) {
		// 5.1 定义变量
		var index = 0
		var current = this.head
		// 5.2 开始查找: 只要current不指向null就一直循环
		while (current) {
			if (current.data === data) {
				return index
			}
			current = current.next
			index += 1
		}
		// 5.3 找到最后没有找到，返回-1
		return -1
	}

	// 6. update方法：修改某个位置的元素
	LinkList.prototype.update = function(position, newData) {
		// 6.1 越界判断: 因为被修改的节点不能为null，所以position不能等于length
		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位置的后一个节点的data修改成newData
		current.data = newData
		// 6.4 返回true表示修改成功
		return true
	}

	// 7. removeAt: 从特定位置移除一项
	LinkList.prototype.removeAt = function(position) {
		// 7.1 越界判断：position不能等于length，因为等于length的节点为null
		if (position < 0 || position >= this.length) {
			return null
		}
		// 7.2 删除元素
		var current = this.head
		if (position === 0) {
			// 情况1：position = 0时(删除第一个节点)
			this.head = this.head.next
		} else {
			// 情况2：position > 0时
			var index = 0
			var previous = null
			while (index++ < position) {
				previous = current
				current = current.next
			}
			// 循环结束后，current指向position后一个节点，previous指向current前一个节点
			// 再使前一个节点的next指向current的next即可
			previous.next = current.next
		}
		// 7.3 length要减1
		this.length -= 1
		// 7.4 返回被删除节点的data，为此current定义在最上面
		return current.data
	}

	// 8. remove方法：从列表移除一项
	LinkList.prototype.remove = function(data) {
		// 8.1 获取data在列表中的位置
		var position = this.indexOf(data)
		// 8.2 根据位置信息删除节点
		return this.removeAt(position)
	}

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

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

var link = new LinkList()
link.append("aaa")
link.append("bbb")
link.append("ccc")

console.log(link.toString()) // aaa bbb ccc
console.log(link)

// 测试insert
link.insert(0, "0a")
link.insert(3, "3b")
link.insert(5, "5c")
console.log(link.toString()) // 0a aaa bbb 3b ccc 5c

// 已有：0a aaa bbb 3b ccc 5c
console.log(link.get(0)) // 0a
console.log(link.get(3)) // 3b

// 已有：0a aaa bbb 3b ccc 5c
console.log(link.indexOf("0a")) // 0
console.log(link.indexOf("3b")) // 3

// 已有：0a aaa bbb 3b ccc 5c
link.update(0, "mmm")
link.update(3, "nnn")
console.log(link.toString()) // mmm aaa bbb nnn ccc 5c

// 已有：mmm aaa bbb nnn ccc 5c
console.log(link.removeAt(0)) // mmm
// 已有：aaa bbb nnn ccc 5c
console.log(link.removeAt(3)) // ccc

// 已有：aaa bbb nnn 5c
console.log(link.remove("nnn")) // nnn

// 已有：aaa bbb 5c
console.log(link.isEmpty()) // false
console.log(link.size()) // 3

# 单向链表

# 链表和数组优缺点对比

# 数组的缺点：

# 链表的优势：

# 链表的缺点：

# 基本特点

# 结构图例

# 位置图例

# 常用操作

# 代码实现

# 0、创建单向链表类

# 1、toString 方法

# 2、append 方法

# 3、insert 方法

# 4、get 方法

# 5、indexOf 方法

# 6、update 方法

# 7、removeAt 方法

# 8、remove|isEmpty|size 方法

# 9、完整代码

单向链表

链表和数组优缺点对比

数组的缺点：

链表的优势：

链表的缺点：

基本特点

结构图例

位置图例

常用操作

代码实现

0、创建单向链表类

1、toString 方法

2、append 方法

3、insert 方法

4、get 方法

5、indexOf 方法

6、update 方法

7、removeAt 方法

8、remove|isEmpty|size 方法

9、完整代码