# javascript探秘之从零到一实现单向 & 双向链表

## 你将收获

• 链表的概念和应用
• 原生javascript实现一条单向链表
• 原生javascript实现一条个双单向链表
• 链表和数组的对比及优缺点

## 正文

### 2.原生javascript实现一条单向链表

#### 2.1 定义链表结构

```let Node = function(el) {
this.el = el;
this.next = null;
}

```// 单向链表, 每一个元素都有一个存储元素自身的节点和一个指向下一个元素引用的节点组成
function linkedList() {
let Node = function(el) {
this.el = el;
this.next = null;
}
let length = 0
let head = null  // 用来存储第一个元素的引用

// 尾部添加元素
this.append = (el) => {};
//插入元素
this.insert = (pos, el) => {};
// 移除指定位置的元素
this.removeAt = (pos) => {};
// 移除指定节点
this.remove = (el) => {};
// 查询节点所在位置
this.indexOf = (el) => {};
// 判断链表是否为空
this.isEmpty = () => {};
// 返回链表长度
this.size = () => {};
// 将链表转化为数组返回
this.toArray = () => {};
}

#### 2.2 实现添加节点

```// 尾部添加元素
this.append = (el) => {
let node = new Node(el),
current;
if(!head) {
head = node
}else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}
length++
};

#### 2.3 实现插入节点

```//插入元素
this.insert = (pos, el) => {
if(pos >=0 && pos <= length) {
let node = new Node(el),
previousNode = null,
current = head,
curIdx = 0;
if(pos === 0) {
node.next = current;
head = node;
}else {
while(curIdx++ < pos) {
previousNode = current;
current = current.next;
}
node.next = current;
previousNode.next = node;
length++;
return true
}
}else {
return false
}
};  复制代码```

#### 2.4 根据节点的值查询节点位置

```// 查询节点所在位置
this.indexOf = (el) => {
let idx = -1,
curIdx = -1,
current = head;
while(current) {
idx++
if(current.el === el) {
curIdx = idx
break;
}
current = current.next;
}
return curIdx
};

#### 2.5 移除指定位置的节点

```// 移除指定位置的元素
this.removeAt = (pos) => {
// 检测边界条件
if(pos >=0 && pos < length) {
let previousNode = null,
current = head,
curIdx = 0;
if(pos === 0) {
// 如果pos为第一个元素
head = current.next
}else {
while(curIdx++ < pos) {
previousNode = current;
current = current.next;
}
previousNode.next = current.next;
}
length --;
return current.el
}else {
return null
}
};复制代码```

#### 2.6 移除指定节点

```// 移除指定节点
this.remove = (el) => {
let idx = this.indexOf(el);
this.removeAt(idx);
};

#### 2.7 获取节点长度

```// 返回链表长度
this.size = () => {
return length
};

#### 2.8 判断链表是否为空

```// 返回链表长度
this.size = () => {
return length
};

#### 2.9 打印节点

```// 将链表转化为数组返回
this.toArray = () => {
let current = head,
results = [];
while(current) {
results.push(current.el);
current = current.next;
}
return results
};

```let link = new linkedList()
// 添加节点
link.append(1)
link.append(2)
// 查找节点
link.indexOf(2)
// ...

### 3.原生javascript实现一条个双单向链表

```let Node = function(el) {
this.el = el;
this.previous = null;
this.next = null;
}
let length = 0
let head = null  // 用来存储头部元素的引用
let tail = null  // 用来存储尾部元素的引用

```// 双向链表, 每一个元素都有一个存储元素自身的节点和指向上一个元素引用以及下一个元素引用的节点组成
function doubleLinkedList() {
let Node = function(el) {
this.el = el;
this.previous = null;
this.next = null;
}
let length = 0
let head = null  // 用来存储头部元素的引用
let tail = null  // 用来存储尾部元素的引用

// 尾部添加元素
this.append = (el) => {
let node = new Node(el)
if(!head) {
head = node
}else {
tail.next = node;
node.previous = tail;
}
tail = node;
length++
};
// 插入元素
this.insert = (pos, el) => {
if(pos >=0 && pos < length) {
let node = new Node(el);
if(pos === length - 1) {
// 在尾部插入
node.previous = tail.previous;
node.next = tail;
tail.previous = node;
length++;
return true
}
let current = head,
i = 0;
while(i < pos) {
current = current.next;
i++
}
node.next = current;
node.previous = current.previous;
current.previous.next = node;
current.previous = node;
length ++;
return true
}else {
throw new RangeError(`插入范围有误`)
}
};
// 移除指定位置的元素
this.removeAt = (pos) => {
// 检测边界条件
if(pos < 0 || pos >= length) {
throw new RangeError(`删除范围有误`)
}else {
if(length) {
if(pos === length - 1) {
// 如果删除节点位置为尾节点,直接删除,节省查找时间
let previous = tail.previous;
previous.next = null;
length --;
return tail.el
}else {
let current = head,
previous = null,
next = null,
i = 0;
while(i < pos) {
current = current.next
i++
}
previous = current.previous;
next = current.next;
previous.next = next;
length --;
return current.el
}
}else {
return null
}
}
};
// 移除指定节点
this.remove = (el) => {
let idx = this.indexOf(el);
this.removeAt(idx);
};
// 查询指定位置的链表元素
this.get = (index) => {
if(index < 0 || index >= length) {
return undefined
}else {
if(length) {
if(index === length - 1) {
return tail.el
}
let current = head,
i = 0;
while(i < index) {
current = current.next
i++
}
return current.el
}else {
return undefined
}
}
}
// 查询节点所在位置
this.indexOf = (el) => {
let idx = -1,
current = head,
curIdx = -1;
while(current) {
idx++
if(current.el === el) {
curIdx = idx;
break;
}
current = current.next;
}
return curIdx
};
// 判断链表是否为空
this.isEmpty = () => {
return length === 0
};
// 返回链表长度
this.size = () => {
return length
};
// 将链表转化为数组返回
this.toArray = () => {
let current = head,
results = [];
while(current) {
results.push(current.el);
current = current.next;
}
return results
};
}

• 插入删除性能
• 查询性能
• 内存占用

0 条评论

• ### 3分钟教你用原生js实现具有进度监听的文件上传预览组件

本文主要介绍如何使用原生js，通过面向对象的方式实现一个文件上传预览的组件，该组件利用FileReader来实现文件在前端的解析，预览，读取进度等功能，...

• ### 15分钟带你了解前端工程师必知的javascript设计模式(附详细思维导图和源码)

设计模式是一个程序员进阶高级的必备技巧,也是评判一个工程师工作经验和能力的试金石.设计模式是程序员多年工作经验的凝练和总结,能更大限度的优化代码以及对已有代码的...

• ### 基于jsoneditor二次封装一个可实时预览的json编辑器组件(react版)

做为一名前端开发人员,掌握vue/react/angular等框架已经是必不可少的技能了,我们都知道,vue或react等MVVM框架提倡组件化开发,这样一方面...

• ### 《javascript数据结构和算法》读书笔记（3）：链表

储存多个元素，数组是最常用的。无论何种语言，都实现了数组。但是大多数语言中，数组的长度是固定的。数组修改操作的成本非常高。

• ### 2-5 线性表之循环链表

为了方便，我这里使用带头结点的单链表来构建循环链表，至于单链表带不带头结点的异同，我在前面的线性表之链表那篇文章中已经做过分析，就不再赘述。

• ### 《剑指offer》分解让复杂问题更简单

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中...

• ### 重读《学习JavaScript数据结构与算法-第三版》- 第6章 链表（一）

本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。

• ### 数据结构知否知否系列之 — 线性表的顺序与链式存储篇（8000 多字长文）

线性表是由 n 个数据元素组成的有限序列，也是最基本、最简单、最常用的一种数据结构。

• ### 用js来实现那些数据结构08（链表02-双向链表）

其实无论在任何语言中，一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝...

• ### 推力达1牛，我国首款牛级霍尔推力器完成点火试验

近日，航天集团六院801所成功研制出了我国首款20千瓦大功率霍尔推力器，并完成点火试验，实现了我国自研推力器推力从毫牛级向牛级的跨越。