一、什么是链表
链表包括
数据
和指向下一个连接点的对象的引用
,类似火车的结构
数组结构的缺点:
- 创建数组需要申请
连续的内存空间
,并且在大多数编程语言中大小都是固定的 - 扩容数组则非常消耗性能
- 在数组的开头或中间插入和删除数据的成本很高,要进行大量数据的位移
链表结构的特点:
- 链表的的元素在内存中不必是连续的空间,实现灵活的
内存动态管理
- 不必在创建时确定大小,可以
无限延伸
- 链表插入和删除数据的效率很高,时间复杂度可以达到O(1)
链表结构的缺点:
- 访问任何一个元素都要从头开始
- 无法通过下标直接访问元素,无法直接找到对应元素
综上所述,频繁插入删除操作就使用链表,如果需要使用下标查找元素,就使用数组
二、链表结构的封装
1、链表的相关操作
append(data)
:向链表尾部添加一个新的项
insert(position, data)
:向链表的特定位置插入一个新的项
remove(data)
:从列表中移除一项
get(position)
:获取对应位置的元素
update(positon,newData)
:修改每个位置的元素
indexOf(data)
:返回元素在列表中的索引。如果列表中没有该元素则返回-1
removeAt(data)
:从链表的特定位置移除一项
isEmpty()
:如果链表中不包含任何元素则返回true
,否则则返回false
size()
:返回链表包含的元素个数
toString()
:由于链表项使用了Node
类,就需要重写继承自JavaScript对象默认的toString
方法,让其只输出元素的值
2、实现封装
/**
* 封装一个链表类
*/
function LinkedList() {
// 内部类,保存数据和下一个节点的指向
function Node(data) {
this.data = data
this.next = null // 先不传入节点引用
}
// 属性
this.head = null // 链表的开头,指向第一个节点
this.length = 0 // 记录链表的长度
// 1、节点追加的方法
LinkedList.prototype.append = function (data) {
// 创建新节点
let newNode = new Node(data)
// 判断是否添加的是第一个节点
if (this.length == 0) {
this.head = newNode
} else {
let flag = this.head // 第一个节点地址
// 找到现有的最后一个节点
while (flag.next) {
flag = flag.next // 只有最后一个节点的next属性才null
}
// 添加节点,并将节点的地址储存到上一个节点的next属性中
flag.next = newNode
}
// 修改节点的长度
this.length += 1
}
// 2、toString方法
LinkedList.prototype.toString = function () {
// 从第一个节点开始获取所有的data
let flag = this.head
let result = ''
while (flag) {
result += flag.data + ' '
flag = flag.next
}
return result
}
// 3、insert方法
LinkedList.prototype.insert = function (position, data) {
// 根据位置插入,先判断位置是否合理
if (position < 0 || position > this.length) return false
// 创建节点
let newNode = new Node(data)
// 判断是否是插入到第一个节点
if (position == 0) {
// 将原本第一个节点的位置保存到新节点,新节点的位置保存到head
newNode.next = this.head
this.head = newNode
} else {
let index = 0
// 待插入位置的原节点默认值(head)
let flag = this.head
// 待插入位置的前一个节点(默认为空)
let previous = null
// 找到对应位置的节点和对应位置的上一个节点
while (index++ < position) {
previous = flag
flag = flag.next
}
newNode.next = flag
previous.next = newNode
}
this.length += 1
return true
}
// 4、get方法
LinkedList.prototype.get = function (position) {
// 根据位置插入,先判断位置是否合理
if (position < 0 || position >= this.length) return null
// 获取对应索引的数据
let flag = this.head
let index = 0
while (index < position) {
flag = flag.next
index++
}
return flag.data
}
// 5、indexOf方法
LinkedList.prototype.indexOf = function (data) {
let flag = this.head
let index = 0
while (flag) {
if (flag.data == data) {
return index
}
flag = flag.next
index += 1
}
return -1 // 没有找到
}
// 6、update方法
LinkedList.prototype.update = function (position, newData) {
// 根据位置插入,先判断位置是否合理
if (position < 0 || position >= this.length) return false
// 查找节点
let flag = this.head
let index = 0
while (index < position) {
flag = flag.next
index++
}
// 修改对应的data
flag.data = newData
return true
}
// 7、removeAt方法(通过索引删除)
LinkedList.prototype.removeAt = function (position) {
// 根据位置插入,先判断位置是否合理
if (position < 0 || position >= this.length) return null
// 判断是否删除第一个节点
let flag = this.head // 当前遍历到的节点
if (position == 0) {
this.head = this.head.next
} else {
let index = 0 // 索引
let previous = null // 当前遍历节点的前一个节点
while (index < position) {
previous = flag
flag = flag.next
index++
}
previous.next = flag.next
}
// 修改长度
this.length -= 1
return flag.data
}
// 8、remove方法(通过数据删除)
LinkedList.prototype.remove = function (data) {
// 获取data所在的位置
let position = this.indexOf(data)
// 根据位置信息删除节点
return this.removeAt(position)
}
// 9、isEmpty方法
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
// 10、size方法
LinkedList.prototype.size = function (data) {
return this.length
}
}
3、运行结果
let res = new LinkedList()
// 插入数据
res.append('a')
res.append('b')
res.append('c')
res.append('d')
// 返回字符串
console.log(res.toString()) // a b c d
// 在索引为2的位置插入'ok'
res.insert(2, 'ok')
console.log(res.toString()) // a b ok c d
// 在链表末尾插入'我'
res.insert(res.length, '我')
console.log(res.toString()) // a b ok c d 我
// 根据索引获取数据
console.log(res.get(0)) // a
console.log(res.get(res.length - 1)) // 我
// 找到数据对应的索引
console.log(res.indexOf('a')) // 0
console.log(res.indexOf('ok')) // 2
// 修改索引为2的值为'no'
res.update(2, 'no')
console.log(res.toString()) // a b no c d 我
// 删除索引为3的值
console.log(res.removeAt(3)) // c
console.log(res.toString()) // a b no d 我
// 删除'我'
console.log(res.remove('我')) // 我
console.log(res.toString()) // a b no d
// 删除一个不存在的'中国'
console.log(res.remove('中国')) // null
// 判断链表是否为空
console.log(res.isEmpty()) // false
// 链表长度
console.log(res.size()) // 4
文章评论