theme: channing-cyan
二者都用于存储一系列的元素,但是实现机制又完全不同。
数组是我们存储多个元素时,最常用的数据结构。但是有以下缺点
如果我频繁的在头部或中间插入数据,此时选择链表。但频繁使用下标操作时,就选择数组。
这里有个形象的比喻:火车🚄
有一个火车头,火车头会连接一节车厢【元素】,车厢上有乘客【类似于数据】,这节车厢连接下一节车厢,以此类推。
从头部header开始,指向第一个节点,item是具体的数据、next是指向下一个节点的指针。以此类推,最后一个节点的指针指向null。如果是一个空链表,那么header直接指向null
<script>
function LinkedList() {
// 内部节点类
function Node(data) {
this.data = data;
this.next = null
}
this.header = null
// 记录链表的长度
this.length = 0
</script>
那么定义完一个链表结构了,我们再看一下链表都需要哪些常见的操作。我们再去完善这些操作方法。
然后,以下的操作方法。可以按照增删改查的顺序来看:
增
删
改
查
主要实现 向末尾添加元素。
1.刚开始,header并没有指向任何节点,所以指向null。
2.加入第一个节点。
使用Node方法(上面链表结构中定义的)创建节点,此时我们判断其是第一个节点,然后就需要把header的指针指向这个节点。 我们这里对第一个节点的next并不需要做指向null
的处理,因为我们在初始化链表结构的时候next就是null。
3.添加第二个节点
使用Node方法创建节点,然后找到上一个节点,并把上一个节点的指针指向此节点。
追加方法
向LinkedList
原型上添加append
方法
LinkedList.prototype.append = function (data) {
}
判断添加的是否是第一个节点,(我们通过length是否为0,来判断是否是第一个节点)。然后创建节点,并将header指向这个节点
// 如果是第一个节点
if (this.length == 0) {
// 创建节点
var newNode = new Node(data)
// head指针指向 第一个节点
this.header = newNode
} else {
}
当节点不是第一个节点,也就是else中的内容: 首先创建一个节点,我们要做的是把我们没添加这个节点前的最后一个节点的next指向我们创建的这个节点。
这里通过一个current变量,首先将header赋值给它(此时的header指向第一个节点),然后向下寻找,当current.next
不为空,则说明就不是最后一个节点,我们就把current.next
赋值给current。直到 current.next
为空(指向null),我们再把最后一个节点的next指向 我们 新创建的节点。
else {
// 创建节点
var newNode = new Node(data)
var current = this.header
// 判断current.next不为空,不为空就说明不是最后一个节点。因为最后一个节点的next指向null
while (current.next) {
current = current.next
}
current.next = newNode
}
最后不要忘记给length+1
this.length += 1
这里在判断是第一个节点和不是第一个节点的方法中都创建了节点,所以我们把创建节点的代码 var newNode = new Node(data)
提取出来了。
function LinkedList() {
// 内部节点类
function Node(data) {
this.data = data;
this.next = null
}
this.header = null
// 记录链表的长度
this.length = 0
LinkedList.prototype.append = function (data) {
// 1.创建新节点
var newNode = new Node(data)
// 2.1 如果是第一个节点
if (this.length == 0) {
// header指针指向 第一个节点
this.header = newNode
// 2.2 不是第一个节点
} else {
// 2.3 找到最后一个节点
// 定义一个变量current,将header赋值给它,此时header是已经指向了第一个节点
var current = this.header
// 判断current.next不为空,不为空就说明不是最后一个节点。因为最后一个节点的next指向null
while (current.next) {
current = current.next
}
current.next = newNode
}
this.length += 1
}
}
/**
* toString() 找到所有节点
* */
LinkedList.prototype.toString = function () {
// 1.定义变量
var current = this.header
var listString = ""
// 2.循环获取一个个节点
while (current) {
listString += current.data + " "
// 依次向后面找
current = current.next
}
return listString
}
这里用到了我们之前写好的append方法,写好toString方法后就可以测试其他方法是否有问题了。
var list = new LinkedList()
list.append('abc')
list.append('fgd')
list.append('dds')
console.log(list.toString())
我们需要两个参数:位置(position)和数据(data)
LinkedList.prototype.insert = function (position,data) {
}
我们需要对position进行越界的判断,比如 -100,正常对于数组来说负数代表从数组尾部开始计算。这里我们就不做这种处理了。我们这里只要是负数,就返false。
LinkedList.prototype.insert = function (position, data) {
if (position < 0) {
return fasle
}
}
并且,比如现在有abc cba nba fbi
四个元素,此时的length是4、下标是3。我们再插入新的节点,可以插到下标是 0 1 2 3 4的位置。
所以再添加一个判断条件
LinkedList.prototype.insert = function (position, data) {
// 对position进行越界判断
if (position < 0 || position > this.length) {
return fasle
}
}
// 创建新节点
var newNode = new Node(data)
判断插入位置是否是第一个
如果是第一个如下图:先将这个节点的next指向原来的第一个节点。然后再将header指向我们的新节点。那么,怎么获得原来的第一个节点呢?header指向的就是原来的第一个节点。
// 判断插入的位置
if (position == 0) {
// 新节点的next指向原来的第一个节点
newNode.next = this.header
// 再把header指向新节点
this.header = newNode
}
插入其他的位置
这里以下标为2为例。
我们首先要做的就是找到下标为2的节点,如下从头依次寻找,直到第三次找到了下标为2的节点(这里定义了两个变量previous和current分别记录目标节点的上一个节点和目标节点)。然后我们将新节点的next指向我们之前下标是2的节点。但是现在我们发现,之前下标是1的节点的next也指向着原来下标是2的节点。
// position = 2
var index = 0;
var current = this.header
var previous = null
while (index++ < position) {
// 记录当前节点的上一个节点
previous = current
// current.next指向的是下一个元素
current = current.next
}
// 新节点指向原来的节点
newNode.next = current
// 原来节点的上一个节点的next指向新节点
previous.next = newNode
}
最后不要忘了给length+1
LinkedList.prototype.insert = function (position, data) {
// 对position进行越界判断
if (position < 0 || position > this.length) {
return fasle
}
// 创建新节点
var newNode = new Node(data)
// 判断插入的位置
if (position == 0) {
// 新节点的next指向原来的第一个节点
newNode.next = this.header
// 再把header指向新节点
this.header = newNode
} else {
// position = 2
var index = 0;
var current = this.header
var previous = null
while (index++ < position) {
// 记录当前节点的上一个节点
previous = current
// current.next指向的是下一个元素
current = current.next
}
// 新节点指向原来的节点
newNode.next = current
// 原来节点的上一个节点的next指向新节点
previous.next = newNode
}
this.length += 1
return true
}
持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第4天,点击查看活动详情
根据位置获取相应的元素。
current
指向current.next
向下寻找,同时增长index。 /**
* 4.get()
* */
LinkedList.prototype.get = function (position) {
// 越界判断
if (position < 0 || position >= this.length) {
return null
}
// 获取相应的data
var current = this.header
var index = 0
while (index < position) {
current = current.next
// 为了让current后移
index++
}
return current.data
}
复制代码
console.log(list.toString())
console.log(list.get(0))
console.log(list.get(3))
根据元素,获取元素所在位置的索引。
如下图,传入的data是dfg
还是上面的,假如传入data是hhh
一直查找,直到current指向null,说明链表中没有此元素,返回-1
/**
* 5.indexOf()
* */
LinkedList.prototype.indexOf = function (data) {
// 定义变量
var current = this.header
var index = 0
// 开始查找
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}
// 向后查找,没找到返回-1
return -1
}
console.log(list.indexOf('fgd'))
console.log(list.indexOf('hhh'))
更改相应位置的元素,传入位置和新的元素数据。传入两个参数:位置索引和新的数据
index==position
,将newData赋值给current的data /**
* 6.update()
* */
LinkedList.prototype.update = function (position, newData) {
// 越界判断
if (position < 0 || position >= this.length) {
return false
}
// 查找正确节点
var current = this.header
var index = 0
while (index++ < position) {
current = current.next
}
//将position位置的node的data改为newData
current.data = newData
return true
}
list.update(0, 'mmm')
list.update(3, 'nnn')
console.log(list.toString())
从链表中移除
当position是0的时候
只需要将header指向下一个节点(索引为1)即可。然后,之前的第一个节点就会因为没有指针指向它而被垃圾回收机制回收。
当position不是0的时候
我们拿2举例子,找到索引是2的元素。定义两个变量previous和current分别记录当前元素的上一个和当前元素。然后将索引是2的元素的上一个元素的next指向索引是2的元素的下一个元素。
/**
* 7.removeAt()
* */
LinkedList.prototype.removeAt = function (position) {
// 越界判断
if (position < 0 || position >= this.length) {
return false
}
// 放到外面 为了能返回删除的元素
var current = this.header
// 是否删除的是第一个节点
if (position == 0) {
this.header = this.header.next
} else {
var index = 0
// 前一个 默认是null
var previous = null
while (index++ < position) {
previous = current
current = current.next
}
// 让前一个节点的next指向,current的next
previous.next = current.next
}
// length不要忘记-1
this.length -= 1
return current.data
}
复制代码
list.removeAt(0)
console.log(list.toString())
移除传入的元素。
这里,我们先通过之前写好的indexOf()找到这个元素所在的位置。然后再通过removeAt(position)方法来移除这个元素。
/**
* 8.remove() = indexOf + removeAt
* */
LinkedList.prototype.remove = function (data) {
// 获取data在链表中的位置
var position = this.indexOf(data)
// 根据位置信息删除节点
return this.removeAt(position)
}
这里用的是之前的数据
list.remove('nnn')
console.log(list.toString())
如果链表中不包含任何元素,返回true,否则返回false。
返回 this.length==0
,如果不为0,则返回false,为0则返回true。
/**
* 9.isEmpty
* */
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
console.log(list.isEmpty()) // false
返回链表中元素的个数,也就是length。
直接返回长度
/**
* 10.size()
* */
LinkedList.prototype.size = function () {
return this.length
}
console.log(list.size()) // 5
<script>
function LinkedList() {
// 1.内部节点类
function Node(data) {
this.data = data;
this.next = null
}
this.header = null
// 记录链表的长度
this.length = 0
LinkedList.prototype.append = function (data) {
// 1.创建新节点
var newNode = new Node(data)
// 2.1 如果是第一个节点
if (this.length == 0) {
// header指针指向 第一个节点
this.header = newNode
// 2.2 不是第一个节点
} else {
// 2.3 找到最后一个节点
// 定义一个变量current,将header赋值给它,此时header是已经指向了第一个节点
var current = this.header
// 判断current.next不为空,不为空就说明不是最后一个节点。因为最后一个节点的next指向null
while (current.next) {
current = current.next
}
current.next = newNode
}
this.length += 1
}
/**
* 2.toString() 找到所有节点
* */
LinkedList.prototype.toString = function () {
// 1.定义变量
var current = this.header
var listString = ""
// 2.循环获取一个个节点
while (current) {
listString += current.data + " "
// 依次向后面找
current = current.next
}
return listString
}
/**
* 3.insert( )
* */
LinkedList.prototype.insert = function (position, data) {
// 对position进行越界判断
if (position < 0 || position > this.length) {
return fasle
}
// 创建新节点
var newNode = new Node(data)
// 判断插入的位置
if (position == 0) {
// 新节点的next指向原来的第一个节点
newNode.next = this.header
// 再把header指向新节点
this.header = newNode
} else {
// position = 2
var index = 0;
var current = this.header
var previous = null
while (index++ < position) {
// 记录当前节点的上一个节点
previous = current
// current.next指向的是下一个元素
current = current.next
}
// 新节点指向原来的节点
newNode.next = current
// 原来节点的上一个节点的next指向新节点
previous.next = newNode
}
this.length += 1
return true
}
/**
* 4.get()
* */
LinkedList.prototype.get = function (position) {
// 越界判断
if (position < 0 || position >= this.length) {
return null
}
// 获取相应的data
var current = this.header
var index = 0
while (index < position) {
current = current.next
// 为了让current后移
index++
}
return current.data
}
/**
* 5.indexOf()
* */
LinkedList.prototype.indexOf = function (data) {
// 定义变量
var current = this.header
var index = 0
// 开始查找
while (current) {
if (current.data == data) {
return index
}
current = current.next
index += 1
}
// 向后查找,没找到返回-1
return -1
}
/**
* 6.update()
* */
LinkedList.prototype.update = function (position, newData) {
// 越界判断
if (position < 0 || position >= this.length) {
return false
}
// 查找正确节点
var current = this.header
var index = 0
while (index++ < position) {
current = current.next
}
//将position位置的node的data改为newData
current.data = newData
return true
}
/**
* 7.removeAt()
* */
LinkedList.prototype.removeAt = function (position) {
// 越界判断
if (position < 0 || position >= this.length) {
return false
}
// 放到外面 为了能返回删除的元素
var current = this.header
// 是否删除的是第一个节点
if (position == 0) {
this.header = this.header.next
} else {
var index = 0
// 前一个 默认是null
var previous = null
while (index++ < position) {
previous = current
current = current.next
}
// 让前一个节点的next指向,current的next
previous.next = current.next
}
// length不要忘记-1
this.length -= 1
return current.data
}
/**
* 8.remove() = indexOf + removeAt
* */
LinkedList.prototype.remove = function (data) {
// 获取data在链表中的位置
var position = this.indexOf(data)
// 根据位置信息删除节点
return this.removeAt(position)
}
/**
* 9.isEmpty
* */
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
/**
* 10.size()
* */
LinkedList.prototype.size = function () {
return this.length
}
}
var list = new LinkedList()
list.append('abc')
list.append('fgd')
list.append('dds')
list.insert(0, 'insert')
list.insert(3, 'bbb')
list.insert(5, 'cccc')
// console.log(list.toString())
// console.log(list.get(0))
// console.log(list.get(3))
// console.log(list.indexOf('fgd'))
// console.log(list.indexOf('hhh'))
list.update(0, 'mmm')
list.update(3, 'nnn')
console.log(list.toString())
list.remove('nnn')
console.log(list.size())
</script>