【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

本文将来讲解一下一种常见的线性数据结构—链表,因为链表和数组一样都是一种线性的数据结构,但是它俩的实现原理是完全不同的,所以在讲解链表之前,我们来回顾一下数组结构。

数组 几乎是每一种编程语言中都自带的一种常用的数据存储结构,我们可以很方便的通过下标值来获取到我们想要的数组中的元素。

但是数组也还是有很大的缺点的,例如现在有一个长度为10的数组,那么数组中的每个元素都对应着各自的下标值,范围为 0~9 ,现在我们要往下标值为 2 的位置插入一个新的元素,我们需要做的就是先把数组的长度变成11,然后将数组中原本下标值为 2 以及之后的所有元素都向后移动一个位置,即下标值 +1,最后再将我们要插入的新元素放到下标值为 2 的位置。

同样的,如果我们要删除数组中的某个元素,也是一样的道理,先删除要删除的元素,然后把被删除元素后面的所有元素往前移动一个位置,即下标值 -1,最后把数组的长度 -1

由上面两个例子可以看出,数组的 添加元素删除元素 非常消耗性能,可谓牵一发而动全身,这就是数组最大的缺点,所以 链表 的出现就弥补了数组的这一缺点。本文就来详细讲解一下链表的概念以及如何实现一个链表。

公众号:Lpyexplore的编程小屋
关注我,每天更新,带你在python爬虫的过程中学习前端,还有更多电子书和面试题等你来拿

【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

数据结构——链表一、什么是链表二、链表的方法三、用代码实现链表(1)创建一个构造函数(2)创建内部构造函数(3)实现append()方法(4)实现insert()方法(5)实现get()方法(6)实现indexOf()方法(7)实现update()方法(8)实现removeAt()方法(9)实现remove()方法(10)实现isEmpty()方法(11)实现size()方法(12)实现toString()方法(13)完整的代码四、总结

一、什么是链表

上面刚提到,链表 弥补了数组的一些缺点,那么是如何做到的呢?链表到底是什么样的呢?接下来我们就用一个简单的例子来解释一下链表的概念

假设在一个教室中,所有学生的座位都排成一列,这一列就可以看成是一个 链表,如图所示
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
每个座位上坐着的学生就相当于链表中的一个 元素 。假如老师记性不好,学生记性也不好,所以他们就很难记住自己的座位到底是哪一个。因此老师想了一个好办法,老师就只记住座位的第一个是谁,然后每一个学生都只要记住自己的后桌是谁就好了。

每次刚进教室准备找座位坐下,老师就告诉学生们说,小5 是坐在第一个的,然后 小5 记得他的后桌是 小1,于是 小1 也找到了座位坐下,因为 小1 记得他的后桌是 小8,所以 小8 也找到自己的座位了……以此类推,一直到坐在最后一个的 小2,就这样大家就都可以找到自己的座位了,如图:
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
有一天, 小8 同学要转学了,所以座位有变动,为了保证座位不空着,小8 走了以后,把他的座位也搬走,以免占用教室空间。此时要让其余同学仍然能正确找到自己的座位的方式就很简单,那就是让原本 小8 的前桌记住,他现在的后桌是 小6了,不再是 小8 了,所以现在的情况如图所示:
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
像这样的记忆自己座位的方式非常的好,因为一个同学转学,只需要让一个人重新记忆自己的后桌是谁即可,而不需要让所有的同学重新记忆。

同理,比如突然有一天,有一个新同学 小7 到了这个班级,老师安排她坐在 小5 后面,此时 小5 就需要记住,他的后桌换成了 小7,而这个新来的同学 小7 也像其他同学一样要记住自己的后桌为 小1,此时的情况是这样的,如图:
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
同样的,新来一个同学造成的位置变动,只让一个同学重新记忆自己的后桌是谁,还同时让新来的同学记住自己的后桌是谁,而没有让所有的同学全部重新记忆,这无疑是一个非常高效的方式。

例子讲完了,接下来进入正题,链表 的实现就像我们刚才讲的那个例子。在链表中,每一个元素都包含两个属性,即 该元素的值item下一个元素next,其中,item 就像我们刚才例子中的同学;next 就像同学记住的他们的后桌是谁。同时链表中有一个指针 head 指向链表第一个元素,这个 head 就好比老师记住的坐在第一个的是谁。

接下来我们来看一下链表的结构
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
这整体看上去就像一个链子,所以叫做链表,每一个 itemnext 组合起来称作是一个元素,再补充一下,最后一个元素指向 null,就相当于例子中坐在最后一个的同学说他没有后桌一样。

此时我们要删除第二个元素,链表结构就会变成这个样子
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
大家可以根据这个结构比对一下刚刚我举得例子,好好理解一下链表的结构形式和实现原理。

二、链表的方法

因为链表是弥补数组缺点而形成的一种数据结构,所以链表也有像数组一样多的方法,这里我们就来看一下链表都有哪些方法吧

方法 含义

append()
向链表尾部追加元素

insert()
在链表的某个位置插入元素

get()
获取链表对应位置的元素

indexOf()
获取某元素在链表中的索引

update()
修改链表中某个位置上的元素的值

removeAt()
移除链表中某位置上的某元素

remove()
移除链表中的某元素

isEmpty()
判断链表内是否为空

size()
返回链表内元素个数

toString()
以字符串的形式展示链表内的所有元素

三、用代码实现链表

根据上面对链表的讲解,我们知道,我们无论是要删除元素还是添加元素,每次都是要从 head 开始,依次往后查找元素,所以对于链表的每一个方法,我们每次做的就是从 head 开始遍历,并通过 next 找到每一个元素的下一个元素是谁。

(1)创建一个构造函数

首先创建一个大的构造函数,用于存放链表的一些属性和方法。

function LinkedList() {
//属性
this.head = null
this.length = 0
}

其中定义了属性 head,并赋值了一个 null,表示现在链表内没有元素;而属性 length则是为了储存链表内的元素个数,这是为了提高链表一些方法的性能,例如之后要写的 size()方法,我们每次调用该方法时,都要遍历整个链表,然后统计元素个数,那么还不如有一个属性记录着元素个数,只需要在添加元素的方法里给 length + 1,在删除元素的方法里给 length - 1

(2)创建内部构造函数

链表的每一个元素都有两个属性,即 itemnext,分别表示存储着该元素的值和该元素的后一个元素是谁。所以我们就在链表的构造函数内部创建一个内部构造函数用于之后创建元素的实例对象

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}
}

之后要如果要添加新元素,我们只需要 new Node(item),并把元素的值传入就可以创建一个元素的实例对象了,这里默认是给每个新创建的元素实例的 next 属性设置为 null,是因为刚开始我们并不知道它被添加到链表里以后,后一个元素是谁,当然,我们只需要在知道了后一个元素是谁的情况下设置一下这个属性即可。

(3)实现append()方法

append()方法就是将元素添加到链表的最后一个。

实现思路:

    创建新的元素实例对象 node
    判断 length 是否为0,若为0,则直接将 head 指向 node
    length 不为0,则根据每个元素的 next 属性遍历链表
    若元素的 next 的值不等于 null,继续遍历
    若元素的 next 的值等于 null,则表示已经查找到链表的最后一个元素,所以直接将该元素的 next 值设置成 node 即可
    属性 length + 1

为了方便你们理解这个实现思路,我做了个动图展示一下思路
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
思路讲完了,我们直接来看代码

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//在链表尾部追加元素
LinkedList.prototype.append = function (item) {
// 1.创建新的元素实例对象
let node = new Node(item)

// 2.判断链表是否为空
if(this.length === 0) {
this.head = node
}
else {
let current = this.head
// 3.遍历链表,找到最后一个元素
while(current.next) {
current = current.next
}
// 4.将我们要添加的元素赋值给原本链表中的最后一个元素
current.next = node
}

//链表元素+1
this.length ++
}
}

我们来使用一下该方法

刚开始的链表是这个样子的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
然后我们使用一下 append()方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')

此时的链表是这样的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

(4)实现insert()方法

insert()方法就是在指定的索引位置插入元素。一共需要传入两个参数,第一个是 position,表示需要插入元素的位置;第二个参数是 item,表示元素的值

实现思路:

    创建新的元素实例对象 node
    判断指定的索引位置 position 是否越界,即是否小于0,或者大于链表的长度。若越界了,则直接返回false
    判断 position 是否为0。若为0,则直接将链表原本的第一个元素,也就是 head所对应的元素赋值给 nodenext属性,然后将 node赋值给 head,表示现在链表的第一个元素为 node
    position 不为0,则遍历链表,同时记录遍历的索引 index 和遍历的上一个元素 prev,当 index == position时,将链表在 index索引位置上的元素赋值给 nodenext属性,再将 node赋值给 prevnext属性
    属性 length + 1

为了方便你们理解这个实现思路,我做了个动图展示一下思路
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
思路讲完了,我们直接来看代码

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//在某个位置插入新的元素
LinkedList.prototype.insert = function (position, item) {
// 1.创建新的元素实例对象
let node = new Node(item)

// 2.判断是否越界
if(position < 0 || position > this.length) return false

// 3.判断插入的位置是否为 0
if(position === 0) {
node.next = this.head
this.head = node
}
else {
// 4.遍历链表,找到索引等于position的元素
let current = this.head
let prev = null
let index = 0
while (index++ < position) {
prev = current
current = current.next
}
// 5.插入元素
prev.next = node
node.next = current

}
// 6.链表元素 +1
this.length ++
return true

}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.insert(1, 'c++')

此时的链表是这样的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

(5)实现get()方法

get()方法就是获取对应位置上的元素。需要传入一个参数,即 position,表示需要获取元素的索引

实现思路:

    判断 position 是否越界。若越界,则直接返回false
    遍历链表,同时记录当前索引 index,当 index == position时,返回当前位置上的元素

接下来我们来单独实现一下该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//获取对应位置的元素
LinkedList.prototype.get = function (position) {
// 1.判断是否越界
if(position < 0 || position >= this.length) return false

let current = this.head
let index = 0
// 2.遍历链表,直到 index == position
while (index++ < position) {
current = current.next
}
// 3.返回当前索引位置的元素
return current.item

}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.get(2) //返回 java

(6)实现indexOf()方法

indexOf()方法就跟数组的一样,获取某元素在链表中的索引值,若链表中不存在该元素,则返回 -1

因为比较简单,这里就不讲解思路了,我们直接用代码来实现这个方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//获取元素的索引
LinkedList.prototype.indexOf = function (item) {
let current = this.head
let index = 0
while (index < this.length) {
if(current.item === item) {
return index
}
else {
current = current.next
index ++
}
}
return -1
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.indexOf('python') //返回 1
linkedlist.indexOf('c++') //返回 -1

(7)实现update()方法

update()方法就是用于修改链表中某位置上的元素的值。因此该方法需要传入两个参数,第一个参数是 position,表示需要修改的元素的索引;第二个参数是 NewItem,表示修改后的值

这里就简单讲下思路吧,首先要先判断 position 是否越界,若越界直接返回 false表示修改失败,若没有越界就遍历链表,同时记录当前索引 index,当 index == position时,就将当前索引位置上的元素的值 item修改成 NewItem

接下来我们来单独实现一下该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//修改某位置上的元素
LinkedList.prototype.update = function (position, NewItem) {
// 1.判断是否越界
if(position < 0 || position >= this.length) return false
else {
let current = this.head
let index = 0

// 2.遍历链表,找到索引等于position的元素对象
while (index < position) {
current = current.next
index ++
}

// 3.将索引等于position的元素的值改为NewItem
current.item = NewItem
return true
}
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.update(2, 'c++')

此时的链表是这样的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

(8)实现removeAt()方法

removeAt()方法就是用于移除链表中某位置上的某元素。该方法只需要传入一个参数 position,表示需要移除元素的索引

实现思路:

    判断 position 是否越界,若越界,则直接返回 false 表示移除元素失败
    若没有越界,判断 position 是否等于 0,若等于 0,则直接将链表第一个元素的 next 值赋值给 head,然后 length - 1
    position 不等于 0,则遍历链表,同时记录当前索引 index,遍历的当前元素 currentcurrent的上一个元素 prev
    index === position时,则将 currentnext 值赋值给 prevnext 值即可,同时 length - 1

为了让大家更好地理解该方法的实现思路,我制作了一个动图来帮助大家理解,如图
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
思路讲完了,我们直接来看代码

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//移除某位置上的元素
LinkedList.prototype.removeAt = function (position) {
// 1.判断是否越界
if(position < 0 || position >= this.length) return false

let current = this.head
let prev = null
let index = 0

// 2.判断position是否等于 0
if(position === 0) {
this.head = current.next
}
else {
// 3.遍历链表
while (index < position) {
prev = current
current = current.next
index ++
}
// 4.移除对应元素
prev.next = current.next
}

// 5.链表元素 -1
this.length --
return true

}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.removeAt(2) //返回 true
linkedlist.removeAt(3) //返回 false,表示删除失败

此时的链表是这样的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

(9)实现remove()方法

remove()方法就是用于移除链表中的某元素,并返回被删除元素所在的索引位置,若链表中没有对应元素,则返回 false 。该方法需要传入一个参数 data用于查找链表中对应的元素

实现思路:

    利用上面封装的 indexOf()方法,将 data 作为参数传入,获取到 data 在链表中的索引 index
    再利用上面封装的 removeAt()方法,将 index 作为参数传入,就可以实现 remove()方法的功能了。

我们简单来写一下代码实现该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//移除某元素
LinkedList.prototype.remove = function (data) {
// 1.获取data在链表中的索引
let index = this.indexOf(data)

// 2.利用removeAt()方法删除链表中的data
this.removeAt(index)

// 3.返回被删除元素data在链表中的索引
return index
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.remove('javascript') //返回 0

此时链表是这个样子的
【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

(10)实现isEmpty()方法

isEmpty()方法就是判断链表中是否有元素。若有元素,则返回 false;反之,返回 true

该方法的实现思路很简单,直接判断属性 length 是否等于 0 就可以了。

话不多说,我们赶紧写代码实现一下该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//判断链表是否为空
LinkedList.prototype.isEmpty = function () {
if(this.length === 0) {
return true
}
else {
return false
}
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.isEmpty() //返回 true,此时链表中无元素

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.inEmpty() //返回 false,此时链表中有三个元素

(11)实现size()方法

szie()方法就是返回链表内的元素个数

我们来实现一下该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//返回链表的元素个数
LinkedList.prototype.size = function () {
return this.length
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.size() //返回 0,此时链表中无元素

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.size() //返回 3,此时链表中有三个元素

(12)实现toString()方法

toString()方法就是以字符串的形式展示链表内的所有元素

实现思路很简单,就是遍历链表中的每一个元素,并将每个元素以字符串的形式连接起来即可

我们来实现一下该方法

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//展示整个链表
LinkedList.prototype.toString = function () {
let string = ''
let current = this.head
while (current) {
string += `${current.item} `
current = current.next
}
return string
}
}

我们来使用一下该方法

let linkedlist = new LinkedList()

linkedlist.append('javascript')
linkedlist.append('python')
linkedlist.append('java')

linkedlist.toString() //返回 javascript python java

(13)完整的代码

function LinkedList() {
//属性
this.head = null
this.length = 0

//每个元素的定义类
function Node(item) {
this.item = item
this.next = null
}

//方法
//在链表尾部追加元素
LinkedList.prototype.append = function (item) {
let node = new Node(item)
if(this.length === 0) {
this.head = node
}
else {
let current = this.head
while(current.next) {
current = current.next
}
current.next = node
}

this.length ++
}

//展示整个链表
LinkedList.prototype.toString = function () {
let string = ''
let current = this.head
while (current) {
string += `${current.item} `
current = current.next
}
return string
}

//在某个位置插入新的元素
LinkedList.prototype.insert = function (position, item) {
let node = new Node(item)

if(position < 0 || position > this.length) return false

if(position === 0) {
node.next = this.head
this.head = node
}
else {
let current = this.head
let prev = null
let index = 0
while (index++ < position) {
prev = current
current = current.next
}

prev.next = node
node.next = current

}
this.length ++
return true

}

//获取对应位置的元素
LinkedList.prototype.get = function (position) {
if(position < 0 || position >= this.length) return false

let current = this.head
let index = 0
while (index++ < position) {
current = current.next
}
return current.item

}

//获取元素的索引
LinkedList.prototype.indexOf = function (item) {
let current = this.head
let index = 0
while (index < this.length) {
if(current.item === item) {
return index
}
else {
current = current.next
index ++
}
}
return -1
}

//修改某位置上的元素
LinkedList.prototype.update = function (position, NewItem) {
if(position < 0 || position >= this.length) return false
else {
let current = this.head
let index = 0
while (index < position) {
current = current.next
index ++
}
current.item = NewItem
return true
}
}

//移除某位置上的元素
LinkedList.prototype.removeAt = function (position) {
if(position < 0 || position >= this.length) return false

let current = this.head
let prev = null
let index = 0
if(position === 0) {
this.head = current.next
}
else {
while (index < position) {
prev = current
current = current.next
index ++
}
prev.next = current.next
}

this.length --
return true

}

//移除某元素
LinkedList.prototype.remove = function (data) {
let index = this.indexOf(data)

this.removeAt(index)
return index
}

//判断链表是否为空
LinkedList.prototype.isEmpty = function () {
if(this.length === 0) {
return true
}
else {
return false
}
}

//返回链表的元素个数
LinkedList.prototype.size = function () {
return this.length
}
}

四、总结

链表结构的讲解就到这里了,希望大家对链表有了更深一层的理解。下一篇文章我将讲解一下另一种链表结构,叫做 双向链表 。

大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

然后大家可以关注一下我的微信公众号:Lpyexplore的编程小屋,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 【数据结构与算法】详解什么是链表,并用代码手动实现一个链表结构
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏