前言
链表和数组一样, 可以用于存储一系列的元素, 但是链表和数组的实现机制完全不同.
这一章中, 我们就来学习一下另外一种非常常见的用于存储数据的线性结构: 链表.
单向链表
一. 认识链表
我们先来认识一下链表, 看一下它大概的机制和原理, 以及和数组的对比.
链表和数组
- 数组:
- 要存储多个元素，数组（或列表）可能是最常用的数据结构。
- 我们之前说过, 几乎每一种编程语言都有默认实现数组结构, 这种数据结构非常方便，提供了一个便利的[]语法来访问它的元素。
- 但是数组也有很多缺点:
- 数组的创建通常需要申请一段连续的内存空间(一整块的内存), 并且大小是固定的(大多数编程语言数组都是固定的), 所以当当前数组不能满足容量需求时, 需要扩容. (一般情况下是申请一个更大的数组, 比如2倍. 然后将原数组中的元素复制过去)
- 而且在数组开头或中间位置插入数据的成本很高, 需要进行大量元素的位移.（尽管我们已经学过的JavaScript的Array类方法可以帮我们做这些事，但背后的原理依然是这样）。
- 链表
- 要存储多个元素, 另外一个选择就是使用链表.
- 但不同于数组, 链表中的元素在内存中不必是连续的空间.
- 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针或者链接)组成.
- 相对于数组, 链表有一些优点:
- 内存空间不是比是连续的. 可以充分利用计算机的内存. 实现灵活的内存动态管理.
- 链表不必在创建时就确定大小, 并且大小可以无限的延伸下去.
- 链表在插入和删除数据时, 时间复杂度可以达到O(1). 相对数组效率高很多.
- 相对于数组, 链表有一些缺点:
- 链表访问任何一个位置的元素时, 都需要从头开始访问.(无法跳过第一个元素访问任何一个元素).
- 无法通过下标直接访问元素, 需要从头一个个访问, 直到找到对应的位置.
链表的数据结构
二. 链表封装
我们先来创建一个链表类
// 封装链表的构造函数
function LinkedList() {
// 封装一个Node类, 用于保存每个节点信息
function Node(element) {
this.element = element
this.next = null
}
// 链表中的属性
this.length = 0 // 链表的长度
this.head = null // 链表的第一个节点
// 链表中的方法
}
代码解析:
- 封装LinkedList的类, 用于表示我们的链表结构. (和Java中的链表同名, 不同Java中的这个类是一个双向链表, 后面我们会讲解双向链表)
- 在LinkedList类中有一个Node类, 用于封装每一个节点上的信息.(和优先级队列的封装一样)
- 链表中我们保存两个属性, 一个是链表的长度, 一个是链表中第一个节点.
我们先来认识一下, 链表中应该有哪些常见的操作
- append(element)：向列表尾部添加一个新的项
- insert(position, element)：向列表的特定位置插入一个新的项。
- remove(element)：从列表中移除一项。
- indexOf(element)：返回元素在列表中的索引。如果列表中没有该元素则返回-1。
- removeAt(position)：从列表的特定位置移除一项。
- isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0则返回false。
- size()：返回链表包含的元素个数。与数组的length属性类似。
- toString()：由于列表项使用了Node类，就需要重写继承自JavaScript对象默认的toString方法，让其只输出元素的值。
完整代码：
<script>
// 封装链表的构造函数
function LinkedList() {
// 封装一个Node类, 用于保存每个节点信息
function Node(element) {
this.element = element
this.next = null
}
// 链表中的属性
this.length = 0
this.head = null
// 链表尾部追加元素方法
// 向链表尾部追加数据可能有两种情况:
//链表本身为空, 新添加的数据时唯一的节点.
//链表不为空, 需要向其他节点后面追加节点.
LinkedList.prototype.append = function (element) {
// 1.根据新元素创建节点
var newNode = new Node(element)
// 2.判断原来链表是否为空
if (this.head === null) { // 链表尾空
this.head = newNode
} else { // 链表不为空
// 2.1.定义变量, 保存当前找到的节点
var current = this.head
while (current.next) {
current = current.next
}
// 2.2.找到最后一项, 将其next赋值为node
current.next = newNode
}
// 3.链表长度增加1
this.length++
}
// 链表的toString方法
//该方法比较简单, 主要是获取每一个元素
// 还是从head开头, 因为获取链表的任何元素都必须从第一个节点开头.
// 循环遍历每一个节点, 并且取出其中的element, 拼接成字符串.
// 将最终字符串返回.
LinkedList.prototype.toString = function () {
// 1.定义两个变量
var current = this.head
var listString = ""
// 2.循环获取链表中所有的元素
while (current) {
listString += "," + current.element
current = current.next
}
// 3.返回最终结果
return listString.slice(1)
}
//添加到其他位置:
//如果是添加到其他位置, 就需要先找到这个节点位置了.
//我们通过while循环, 一点点向下找. 并且在这个过程中保存上一个节点和下一个节点.
//找到正确的位置后, 将新节点的next指向下一个节点, 将上一个节点的next指向新的节点.
// 添加到第一个位置:
// 添加到第一个位置, 表示新添加的节点是头, 就需要将原来的头节点, 作为新节点的next
//另外这个时候的head应该指向新节点.
// 根据下标删除元素
LinkedList.prototype.insert = function (position, element) {
// 1.检测越界问题: 越界插入失败
if (position < 0 || position > this.length) return false
// 2.定义变量, 保存信息
var newNode = new Node(element)
var current = this.head
var previous = null
index = 0
// 3.判断是否列表是否在第一个位置插入
if (position == 0) {
newNode.next = current
this.head = newNode
} else {
while (index++ < position) {
previous = current
current = current.next
}
newNode.next = current
previous.next = newNode
}
// 4.length+1
this.length++
return true
}
//移除数据有两种常见的方式:
//根据位置移除对应的数据
//根据数据, 先找到对应的位置, 再移除数据
// 根据位置移除节点
LinkedList.prototype.removeAt = function (position) {
// 1.检测越界问题: 越界移除失败, 返回null
if (position < 0 || position >= this.length) return null
// 2.定义变量, 保存信息
var current = this.head
var previous = null
var index = 0
// 3.判断是否是移除第一项
if (position === 0) {
this.head = current.next
} else {
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
// 4.length-1
this.length--
// 5.返回移除的数据
return current.element
}
// 根据元素获取链表中的位置
LinkedList.prototype.indexOf = function (element) {
// 1.定义变量, 保存信息
var current = this.head
index = 0
// 2.找到元素所在的位置
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
// 3.来到这个位置, 说明没有找到, 则返回-1
return -1
}
// 根据元素删除信息
LinkedList.prototype.remove = function (element) {
var index = this.indexOf(element)
return this.removeAt(index)
}
// 判断链表是否为空
LinkedList.prototype.isEmpty = function () {
return this.length == 0
}
// 获取链表的长度
LinkedList.prototype.size = function () {
return this.length
}
// 获取第一个节点
LinkedList.prototype.getFirst = function () {
return this.head.element
}
}
</script>