单向链表是什么,前端如何实现(数据结构系列)
1. 什么是链表
- 链表类似于火车:有一个火车头,一堆车厢。火车头会通过节点连接车厢,车厢间也会使用节点依次串联起来。
- 链表的数据结构
2. 链表与数组对比
共同点
- 都是用于存储一系列元素
不同点
-
数组
-
优点:
- 编程语言基本都会内置数组结构,使用简单方便
- 用
[]
访问对应的元素,访问的时间复杂度为O(1)
-
* 缺点:
* 固定大小:大多数编程语言定义数组时,需要先声明大小。(js不需要,js底层会根据数组大小,自动伸缩管理容量)
* 连续空间:在开辟内存时,需要申请连续的空间
* 数组越往前`` 增删 ``元素时,时间复杂度越高。(js底层为保证连续性,需要移动增删位置之后的元素)
-
链表
-
优点:
- 申请空间时不需要事先确定大小
- 不需要申请连续的内存空间,内存利用率更高
- 越往前对链表增删,时间复杂度越低,增删开头时间复杂度为O(1)
-
* 缺点
* 访问任意位置元素时,需要从头开始遍历,时间复杂度为O(N)
3. 链表代码的实现
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.count = 0;
this.head = null;
}
// 链表尾部追加元素
append(value) {
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
} else {
let currentNode = this.getElementAt(this.count - 1);
currentNode.next = newNode;
}
this.count++;
}
// 在指定位置插入元素,越界返回false,表示插入失败
insert(index, value) {
if (index < 0 || index > this.count) {
return false;
}
let newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
} else if (index === 0) {
newNode.next = this.head;
this.head = newNode;
} else {
let lastNode = this.getElementAt(index - 1);
newNode.next = lastNode.next;
lastNode.next = newNode;
}
this.count++;
return true;
}
// 移除指定元素。若找不到该元素,则返回false,表示移除失败
remove(value) {
let lastNode = null;
let currentNode = this.head;
while (currentNode) {
if (currentNode.value === value) {
if (lastNode === null) {
this.head = this.head.next;
} else {
lastNode.next = currentNode.next;
}
this.count--;
return true;
}
lastNode = currentNode;
currentNode = currentNode.next;
}
return false;
}
// 移除指定位置上的元素。若找不到该位置,则返回false,表示移除失败
removeAt(index) {
if (index < 0 || index > this.count - 1) {
return false;
}
if (index === 0) {
this.head = this.head.next;
} else {
let lastNode = this.getElementAt(index - 1);
lastNode.next = lastNode.next.next;
}
this.count--;
return true;
}
// 返回指定位置的节点,越界返回undefined
getElementAt(index) {
if (index < 0 || index >= this.count) {
return undefined;
}
let currentNode = this.head;
for (let i = 0; i < index; i++) {
currentNode = currentNode.next;
}
return currentNode;
}
// 返回元素的索引值,若没改元素则返回-1
indexOf(value) {
let currentNode = this.head;
let index = 0;
while (currentNode) {
if (currentNode.value === value) {
return index;
}
currentNode = currentNode.next;
index++;
}
return -1;
}
// 返回链表元素个数
size() {
return this.count;
}
// 返回当前是否为空链表
isEmpty() {
return this.count === 0
}
// 清空链表
clear() {
this.count = 0;
this.head = null;
}
// 输出链表每项元素
toString() {
let arr = [];
let currentNode = this.head;
while (currentNode) {
arr.push(currentNode.value);
currentNode = currentNode.next;
}
return arr.join(",")
}
}
4. 线上代码
5. 应用场景
- 结合数组缺点、链表优点,可得出当频繁对数据增删的话,用链表效率更高;若是频繁读取数据,则数组更优。
- 队列数据结构,之前是基于数组,在出栈时效率没有基于链表的效率高,后面基于双向链表再实现队列。
6. 相关文章
- 上一篇:前端es6实现优先级队列
- 下一篇:双向链表(暂未更新)
- 相关篇:es6实现队列数据结构(基于数组)