JS数据结构之JS实现链表
开头
以本文来复习《学习JavaScript数据结构与算法》一书中链表相关知识。
何为链表
链表储存有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个储存元素本身的节点和一个指向下一个元素的引用组成。
与数组的不同
对比数组，链表的好处在于：当添加或移除元素的时候不需要移动其他元素。
另一个不同点：数组可以直接访问任何位置的元素，而访问链表中的元素，需要从链表的head开始迭代列表直到找到所需的元素。
使用JavaScript实现链表
《学习JavaScript数据结构与算法》一书中的代码实现为ES5，本文将尝试使用ES6语法实现链表。
function LinkedList() {
class Node{
constructor(element) {
this.element = element
this.next = null
}
}
let length = 0
let head = null
this.append = element => {
let node = new Node(element),
current
if (head === null){
head = node
} else {
current = head
// 循环列表，知道找到最后一项
while(current.next){
current = current.next
}
// 找到最后一项，将其next赋值为node，建立链接
current.next = node
}
length ++
}
this.insert = (position, element) => {
// todo
// 检查越界值
if (position >=0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
// 在第一个位置添加
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
length++
return true
} else {
return false
}
}
this.removeAt = position => {
// 检查越界值
if(position > -1 && position < length) {
let current = head,
previous,
index = 0
// 移除第一项
if (position === 0) {
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
// 将previous与current的下一项链接起来：跳过current，从而移除它
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
this.remove = element => {
let index = this.indexOf(element)
return this.removeAt(index)
}
this.indexOf = element => {
let current = head,
index = 0
while (current) {
if (element === current.element) {
return index
}
index ++
current = current.next
}
return -1
}
this.isEmpty = () =>{
return length === 0
}
this.size = () => {
// todo
return length
}
this.toString = () => {
// todo
let current = head,
string = ''
while (current) {
string += ',' + current.element
current = current.next
}
return string.slice(1)
}
this.getHead = () => {
return head
}
}
Node辅助类
Node辅助类表示需要加入列表的项。包含：
- element属性，指将要添加到列表中的值
- next属性，一个指向下一个节点的指针
两个储存变量
- length属性，储存列表项的数量
- head属性，储存第一个节点的引用
append方法
append方法向列表末尾添加一个元素，有两种场景：
- 列表为空，此时添加的是第一个元素
- 列表不为空，此时向列表追加元素
this.append = element => {
let node = new Node(element),
current
if (head === null){
head = node
} else {
current = head
// 循环列表，知道找到最后一项
while(current.next){
current = current.next
}
// 找到最后一项，将其next赋值为node，建立链接
current.next = node
}
length ++
}
首先将实例化node。
当列表为空，也就是传入的元素为第一个元素时，将head指向node。
当列表不为空，要向列表尾部添加元素时，我们需要一个指向当前元素的current的变量。之后循环访问列表，直到current.next为null，此时表示已到达列表尾部。将current.next指向node就能实现在尾部添加元素了。
最后，每次append都会使实例的length+1。
toString方法
先写toString方法可以有助于测试代码。
toString方法会将LinkedList对象转换成字符串。
this.toString = () => {
// todo
let current = head,
string = ''
while (current) {
string += ',' + current.element
current = current.next
}
return string.slice(1)
}
从head开始遍历每个元素，从头开始循环直到current为null，在循环中通过,拼接元素,同时指向先一个元素。最后返回字符串。
// 测试
var list = new LinkedList()
list.append(11)
list.append(22)
list.toString() // "11,22"
点我，在线测试。
removeAt方法
removeAt方法接收一个position来根据指定位置移除元素。
this.removeAt = position => {
// 检查越界值
if (position > -1 && position < length) {
let current = head,
previous,
index = 0
// 移除第一项
if (position === 0) {
head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
// 将previous与current的下一项链接起来：跳过current，从而移除它
previous.next = current.next
}
length--
return current.element
} else {
return null
}
}
首先需要验证这个position是否有效。无效时返回null。
当这个position有效时，需要从head开始，故将head赋值给current,同时也需要一个previous变量以及一个index索引。
当position === 0时，表示我们需要移除第一项，因为当前current元素就是head，所以需要将head通过current.next指向下一个元素。这样就会移除第一个元素。
当需要移除中间或者最后一个元素时，循环直到index === position,此时到达目标位置。将当前值current赋值给previous变量，将当前值的下一个node赋值给当前值。然后通过将previous与current的下一项链接起来：跳过current，从而移除它。
最后，每次removeAt都会使实例的length-1，并返回被删除的元素。
// 测试
list.toString() // "11,22"
list.removeAt(0) // 11
list.toString() // "22"
点我，在线测试。
insert方法
insert方法可以在任意位置插入一个元素。
this.insert = (position, element) => {
// todo
// 检查越界值
if (position >=0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0
if (position === 0) {
// 在第一个位置添加
node.next = current
head = node
} else {
while (index++ < position) {
previous = current
current = current.next
}
node.next = current
previous.next = node
}
length++
return true
} else {
return false
}
}
同样的需要检查position是否有效。无效时返回false。
当有效时，将element实例化为node,其余变量设置与removeAt方法类似。
当在第一个位置添加元素时，将node的next指向current,同时head指向node。
若是其他场景，同样需要循环列表，找到目标位置。当跳出循环后，node.next指向当前元素，previous.next指向node。这样就在当current元素与previous元素之间插入了node。
最后每次插入元素列表的长度都需要+1，同时返回true作为信号。
// 测试
list.toString() // "22"
list.insert(2,33) // false
list.insert(1,22) // true
list.toString() // "22,33"
list.insert(1,44) // true
list.toString() // "22,44,33"
点我，在线测试。
indexOf方法
indexOf方法接收一个值，如果这个值存在于列表中，就返回元素的位置，否则就返回-1。
this.indexOf = element => {
let current = head,
index = -1 // 此处书中为 index = -1
while (current) {
if (element === current.element) {
return index
}
index ++
current = current.next
}
return -1
}
变量的定义类似之前的方法。
循环止于current为null。
当元素为我们要找的元素时，返回index。否则就计数，检查下一个node。
// 测试
list.toString() // "22,44,33"
list.indexOf(100) // -1
list.indexOf(22) // 0
点我，在线测试。
其余方法不再赘述
其余几个方法比较简单，故此处不再赘述。
本文所使用的链表类为单向链表。
其他种类链表将在之后补充。
本文参考
- 头图画师: hakusai
- 《学习JaveScript数据结构与算法》
作者：hayato
文章版权：本站所有文章版权依赖于 CC BY-NC-SA 3.0 Unported License
本文链接：https://blog.axis-studio.org/2017/11/26/JS数据结构之JS实现链表/