TypeScript算法专题 - 基于TypeScript语言的单链表实现
1. 链表的概念
链表是一种物理存储单元上非连续、非顺序的存储结构，它由一系列结点组成，其特点在于结点可以在运行时动态生成。
链表的存储结构特点
链表的每个结点包括两个部分：
- 一个是存储数据元素的数据域；
- 存储下一个结点地址的指针域。
链表可以用任意一组存储单元来存储其中额数据结构，其存储单元可以是不连续的。
单链表
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起构成单链表。单链表即单向链表，单向指的是其指针域所存储的信息只能为一个方向。具体来说，单链表中的每个存储单元中，除了需要存储每个单元的数据外，还必须附带储存其直接后继存储单元的地址信息。如图所示：
双向链表
它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
循环链表
循环的最后一个结点指向头结点从而形成一个环。可想而知，从循环链表中的任何一个结点出发都能找到任何其他结点。
循环单链表
尾元结点的后继指针指向表中的首元结点。其特点为：
- 其每个结点都处于一个循环链中，可以从任何一个位置开始，按照后继方向遍历整个链表。
- 其在合并与分裂时，若非必须从链表头节点开始，可直接在链表指针处进行合并，时间复杂度可达O(1)。
循环双链表
其每个结点包含两个指针指向直接前驱和直接后继，可以在两个方向上遍历某个结点之后以及之前的元素。循环双链表的特点为：
- 每个几点处于2个链中：1为后继方向的循环链链，2为前驱方向的循环链。
- 从某个结点出发进到直接前驱或者直接后继节点，时间复杂度均为O(1)。
- 查找第i个节点、删除第i个节点、在第i个节点处插入，都需要区分时哪一个方向。
- 修改指针要同时考虑在前驱循环链和后继循环链上的修改。
- 某个节点的
直接前驱的直接后继或其直接后继的直接前驱都是该节点本身。
静态链表
用一维数组来进行描述的一种链表，它利益数组下标号来访问下一个节点，因此需要定义一个足够大的节点数组。
概念归纳
| 概念名 | 释义 |
| 节点 | 是链表中的一个存储单元，其包含一块数据存储区域和一块后继信息存储区域 |
| 链表 | 由n个链表单元（节点）连接在一起的存储结构 |
| 首元节点 | 线性链表中第一个元素结点 |
| 尾元节点 | 线性链表中最后一个元素结点 |
| 头节点 | 若链表存在头节点，头节点即链表的第一个节点 |
| 头指针 | 有头单链表的头节点，其指针永远指向链表中头节点的位置 |
| 单链表 | 节点只包含其后继节点信息的链表 |
| 双向链表 | 节点中都有两个指针，分别指向直接后继和直接前驱 |
| 循环链表 | 最后一个结点指向头结点，形成一个环 |
链 表 { 链 表 带 有 【 头 结 点 】 ： { 表 头 指 针 指 示 头 节 点 头 节 点 链 接 指 针 指 示 首 元 结 点 链 表 没 有 【 头 节 点 】 ： 表 头 指 针 指 示 首 元 结 点 链表 \begin{cases} 链表带有【头结点】：\begin{cases}\pmb{表头指针}指示\pmb{头节点}\\\pmb{头节点链接指针}指示\pmb{首元结点}\end{cases}\\ 链表没有【头节点】：\pmb{表头指针}指示\pmb{首元结点} \end{cases}链表⎩⎪⎨⎪⎧链表带有【头结点】：{表头指针表头指针表头指针指示头节点头节点头节点头节点链接指针头节点链接指针头节点链接指针指示首元结点首元结点首元结点链表没有【头节点】：表头指针表头指针表头指针指示首元结点首元结点首元结点
单链表进行插入和删除操作实际上不需要移动数据元素，只需要修改相关指针。
在TypeScript语言中并没有C和C++中那样指针的概念以用过指针的相关操作带出数据，我们只能来模拟这个过程。
与线性表/顺序表相比
由于链表不必须按顺序存储，它在插入的时候可以达到O(1)的复杂度，比线性表和顺序表（时间复杂度O(n)）快得多。但是链表查找一个节点或者访问特定编号的节点却需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
2. 单链表的TypeScript语言实现
2.1 单链表的节点
链表是由一个一个节点通过某种关系建立关联构成的一种数据结构，单链表也是如此。单链表中的所有节点只有一个指向各自直接后继节点的指针域以及各自的数据域：
一个最基本的单链表节点看起来是这个样子的：
class Lnode{ /** * 链表节点类 * @class Lnode * @constructor * @param next {Lnode} 指向下一节点的指针 * @param data {any} 节点的数据 */ next: Lnode | null; // 节点类型（Lnode）的nest也是节点类型Lnode，null是任意类型的子类型也可以不写 data: any; constructor(data:any){ this.data = data; this.next = null; } };
2.2 单链表的基本操作：
2.2.1 增
增指的是为该单链表增添节点。增加元素的方法有很多，如：
pop_left：从链表左端（头）开始增加节点；pop：从链表右端（尾）开始增加；insert：从中间的某个（索引号）位置开始增加；p_insert：在指向链表中的某个指针pointer后面的位置插入新节点；
2.2.2 删
删指的是从链表中删除元素。删的方法同样有很多，比如：
del(index):按照节点的索引号删除链表中的单个节点；drop(index):按照索引号删除链表中某个节点及其之后所有节点；drop(a,b):给定两个索引号a和b，删除从[a,b]的一段节点；clear:删除链表中的所有节点使之成为一个空链表。
2.2.3 改
对链表改是指对链表的节点的内容进行更改。比如：
replace：依据节点的索引值将链表中的某一个节点替换成新的节点；reverse：使链表中的所有节点进行反转。
2.2.4 查
查的最终目的是为了获取链表中的节点元素。我们知道，单链表中的一个节点包含一个指向节点后继的指针域以及一个存储节点数据的数据域，也就是查在很多情况下是为了获取数据域中的信息。不过也不全是，不如当我们指向查看以下链表是否有节点，这时只要查某个域指针是否指向了一个节点。将要实现的与此有关的功能包括：
is_empty：查看头链指针是否为空以判断链表是否为空；top：查看链表头节点的数据内容；
2.3 单链表抽象数据结构
以下是接下来我们在本文以及后续的几篇博客中，基于增删改查将要逐个实现的数据结构。
ADT LinkList{ init(id, name) # 初始化（构造）单链表 is_empty() # 判断单链表是否为空 top() # 获取链表的头部节点 clear() # 清空链表 del(index) # 从中间删除索引为`index`的一个节点 drop(index) # 删除索引为`i`节点及其之后的所有节点 drop(index_1,index_2) # 删除从索引为`index_1`（包含）开始到索引为`index_2`（包含）的一段节点 append(node) # 在链表的最右端嵌入一个新的节点node append_left(node) # 在链表的最左端嵌入新的节点node insert(index, node) # 在链表的第`index`个节的位置挂载新的节点`node` p_insert(pointer) # 在指向链表中的某个指针pointer后面的位置插入新节点 pop() # 弹出链表尾部节点 pop_left() # 弹出链表头节点并返回 toArray() # 获取链表节点依次构成的数组，可以方便用于链表的遍历和后续利用数组随机取值 reverse() # 反转链表，直接将原链表反转而不返回值 getReverse() # 反转链表，返回反转后的链表，不改变原链表 }
2.4 使用TypeScript语言实现一个单链表：
本章（博客）实现一个具有判空、查头、增加节点、转为节点数组功能的简单的单链表。在本专题的后续博客中，将会逐步实现上面提到的其它功能。
这部分的ADT如下：
ADT LinkList{ init(id, name) # 初始化（构造）单链表 is_empty() # 判断单链表是否为空 top() # 获取链表的头部节点 get(index) # 获取索引号为`index`的节点 append(node) # 在链表的最右端挂载一个新的节点node append_left(node) # 在链表的最左端挂载新的节点node toArray() # 获取链表节点依次构成的数组，可以方便链表的遍历
2.4.1 节点类的实现
链表是以节点为基础（元素）构成的节点链。节点可以看作是特殊的链表。
【注意】
TypeScript中没有指针的概念，因此在专题前两篇文章中我们用的是一种比较麻烦的方法去模拟，实际上是建立一个新的结点链来实现功能。
第三篇 《链表实现中的一些问题总结与改进》将讲解在JavaScript和TypeScript中的变量引用，并对我们的链表中的相应内容进行简化。
class Lnode{ /** * 链表结点类，结点是构成链表的基础单元。 * @class Lnode * @constructor * @param next {Lnode} 指向下一结点的指针 * @param data {string | number} 结点的数据。这里只放一些字符串数据或者数字。 */ next: Lnode | undefined | null; // 结点类型（Lnode）的nest也是结点类型Lnode，undefined和null是任意类型的子类型也可以不写 data: any; empty: boolean; // 描述结点是否为空，这个是配合初始化一个空结点使用的 constructor(data?:string | number){ if(data!=undefined){ // 非空结点 this.empty = false; // 空标识置为假 this.data = data; this.next = null; }else{ // 空结点，即值构建结点对象但实际上不存在结点 this.empty = true; // 空标识置为真 this.data = null; this.next = null; } } merge(node: Lnode){ /** * 将另一个结点（链）合并到本结点（或链）的尾部 * @param node {Lnode} 需要插入链表尾部的新结点 */ if(this.empty==true){ // 空结点 this.empty =false; this.data = node.data; }else{ if(this.next == null){ // 没有链接下一个 this.next = node; }else{ // 有链接下一个 this.next.merge(node); } } } }
2.4.2 链表类的实现
基于2.4.1 节中的节点，实现单链表如下：
class LinkList{ /** * 单链表类 * @class LinkList * @constructor * @param head {Lnode} 链表的第一个节点，其`next`用于挂载结点 * @param length {number} 链表的长度 */ head: Lnode | undefined| null; length: number; // 链表所容纳结点的个数 constructor(datas?:any[]){ /**初始化 */ if(datas==undefined){ this.head = null; // 初始化为null算作空链表，不计算长度 this.length = 0; }else{ for(let i=0; i<datas.length; i++){ this.append(new Lnode(datas[i])) } this.length = datas.length; // 指定一组数据初始化则初始后长度为这组数据元素的个数 } } is_empty(){ /** * 判断链表是否为空 * 只需要判断头结点是否为空，若头结点为空则为空链表，否则不是。 * @return {Boolean} true:链表为空; false:链表非空。 */ if(this.head == null){ return true; }else{ return false; } } top():Lnode{ /** * 获取链表头结点 */ let node = this.head; node.next = null; return node; } clear(){ /** * 清空链表，只要把头结点干废，整个链表直接就完蛋（清空）了 */ this.head = null; this.length = 0; } append(node: Lnode){ /** * 将新结点挂载到链表尾部 * @param node {Lnode} 需要插入链表尾部的新结点 */ if(this.head == null){ this.head = node; this.length = this.length + 1; }else{ this.head.merge(node); this.length = this.length + 1; } } append_left(node: Lnode){ /** * 将一个新结点插入到链表首部 * @param node {Lnode} 要从左侧也就是链头插入的新结点 */ if(this.head == null){ this.head = node; // 若为空链表，直接将链表头设置为该结点 this.length = this.length + 1; // 增加结点长度 }else{ // 先将新结点的`next`指向原第一个结点 node.next = this.head; // 再将`head`指向新的结点 this.head = node; this.length = this.length + 1; // 增加结点长度 } } get(index: number):Lnode{ /** * 获取索引号为`index`的结点。 * 索引号是从数字`0`开始计算的 * @param index {number} 索引号 * @return node {Lnode} 索引得到地节点 */ if(index<0){throw "ValueError: Index must be a positive integer!"} else if(index+1 > this.length){throw "ValueError: Index exceeds the maximum value!"} else{ let pointer:Lnode = this.head; // 从头结点开始 range([index]).forEach(() => { pointer = pointer.next; // 逐个指向下一个结点 }); pointer.next = null; // 斩断后继 return pointer; } } get_data(index: number){ /** * 索引节点地数据 * @param index {number} 索引号 * @return data {any} 链表中与索引号对应地节点地数据域内容 */ return this.get(index).data } insert(index:number, node:Lnode){ /** * 在链表的第`index`个节的位置挂载新的结点`node`，其中从结点为`index = 0`开始编号 * 也就是说，新的结点索引号将为`index`，而这个结点将挂载到索引号为`index-1`的结点后面 * * @param index {number} 新结点插入的索引号 */ if(node!=null && node.next==null){node.next = null;}; // 只允许插入单个结点，若有后继直接切断 if(index==0){ node.next = this.head; // 先收小弟 this.head = node; // 再上位 }else{ let pointer: Lnode = this.head; // 从头结点开始 let results: Lnode = new Lnode(); // 空结点 for(let i=0; i<index; i++){ results.merge(new Lnode(pointer.data)); // 逐个记录先驱结点 pointer = pointer.next; // 逐个指向下一个结点 } node.next = pointer; // 先收小弟 results.merge(node); // 再上位 this.length = this.length + 1; // 更新结点长度 this.head = results; } } toArray():Lnode[]{ /** * 获取链表结点依次构成的数组 * @returns elem {Lnode[]} 以此装载了被遍历到的所有结点（这里其中每个结点都是孤立、干掉next的） */ let elm: Lnode[] = []; // 准备好用于容纳所有的结点 let pointer:Lnode = this.head; // 挂载操作一开始时指针指向头部结点、 if(pointer==null){ // 空链表，不仅要返回一个空数组，还要抛出提示 console.warn("Warning: It seems that you hava traversed an empty Linked List!"); return elm; }else{ // 非空链表 while(pointer.next != null){ // 存在下一个结点时 if(pointer == null){ // 停止（拦截）条件：（直到）结点为`null` break; }else{ // 获取当前结点剔除链接关系的`孤立结点`挂载结点数组 elm.push(new Lnode(pointer.data)); } pointer = pointer.next; // 指向后继 } elm.push(new Lnode(pointer.data)); // 最后一个元素 return elm; } } }
2.5 使用单链表
本节主要来测试2.4节中实现的单链表。
2.5.1 编译ts相关问题的说明
由于本博文为专题博文中的第一篇博文，我们简单介绍以下与编译相关地事情。由于目前TypeScript还不能直接被多数浏览器所识别，需要先编译成JavaScript代码。
我们简单给出基于TypeScript包的tsc 命令以及使用webpack编译成.js文件的相关配置。如果你还有没这方面的基础，可以在我的另外一个博客专题 《TypeScript 语言基础专题》 中找到详细的教程。
使用tsc 命令
使用编译时的的一些配置文件tsconfig.json代码：
{ "compilerOptions": { /* Visit https://aka.ms/tsconfig.json to read more about this file */ /* Basic Options */ "target": "es5", /* Specify ECMAScript target version: 'ES3' (default), 'ES5', 'ES2015', 'ES2016', 'ES2017', 'ES2018', 'ES2019', 'ES2020', or 'ESNEXT'. */ "module": "commonjs", /* Specify module code generation: 'none', 'commonjs', 'amd', 'system', 'umd', 'es2015', 'es2020', or 'ESNext'. */ "outDir": "./es5/", /* Redirect output structure to the directory. */ /* Strict Type-Checking Options */ "strict": false, /* Enable all strict type-checking options. */ /* Module Resolution Options */ "moduleResolution": "node", /* Specify module resolution strategy: 'node' (Node.js) or 'classic' (TypeScript pre-1.6). */ "allowSyntheticDefaultImports": true, /* Allow default imports from modules with no default export. This does not affect code emit, just typechecking. */ "esModuleInterop": true, /* Enables emit interoperability between CommonJS and ES Modules via creation of namespace objects for all imports. Implies 'allowSyntheticDefaultImports'. */ /* Experimental Options */ "experimentalDecorators": true, /* Enables experimental support for ES7 decorators. */ // "emitDecoratorMetadata": true, /* Enables experimental support for emitting type metadata for decorators. */ /* Advanced Options */ "skipLibCheck": true, /* Skip type checking of declaration files. */ "forceConsistentCasingInFileNames": true /* Disallow inconsistently-cased references to the same file. */ } }
这样将生成一个与.ts同名的.js文件在目录./es5下。这里，我的.ts文件命名为singly_linked_list_01.ts，对应的，生成的.js文件就是singly_linked_list_01.js。
使用webpack编译
其实我个人更喜欢使用webpack，因为即使使用tsc 编译的代码没有任何问题，但是这样编译的代码由于当前浏览器无法很好地支持impory等一些新的命令，最终将导致程序无法在浏览器中运行。
详细教程也可以在博文专题 《TypeScript 语言基础专题》 中找到，以下是webpack.config.js配置文件
const path = require('path'); // 对Node.js地标准库`path`进行导包 module.exports = { entry:'./singly_linked_list_01.ts', // 打包文件入口 output:{ filename:'singly_linked_list_01_webpack.js', // 输出文件名称 path:path.resolve(__dirname,'es5') // 输出文件夹名为'es5'，需要加上前面地路径构成绝对路径 }, mode: 'development', module:{ rules: [{ test: /\.tsx?$/, use: 'ts-loader', exclude: /node_modules/}] }, resolve: { extensions: ['.ts']}, }
还有就是 node.js 配置文件地script字段更改如下：
"scripts": { "pack": "webpack" },
这样可以通过npm run pack打包生成’.js’文件 singly_linked_list_01_webpack.js 。
在html中引入
你需要在html中引入你生成的.js文件它：
<!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>链表</title> </head> <body> <!-- 这里是直接使用TypeScript编译而成的ts文件 --> <!-- <script src="./es5/singly_linked_list_01.js"></script> --> <!-- 如果要import语法，目前浏览器还不支持，但是可以通过编写webpack配置文件 + 运行`npm link typescript`（由于先前全局安装了typescript） + 引入webpack生成的JavaScript文件 替代由typescript生成的typescript文件来使用 --> <script src="./es5/singly_linked_list_01_webpack.js"></script> </body> </html>
2.5.2 测试：尾部逐个添加节点
// 创建链表 let list: LinkList = new LinkList(); // append()添加元素，数据域为字符串数字 "1"、"2"、"3"、"4"、"5"、"6" for(let i:number =1; i<=6; i++){ list.append( new Lnode(i.toString()) ) }; console.log(list);
2.5.3 测试：将链表转换为节点数组与遍历节点
以下代码中用到了写在另一个文件中的range函数，这个实现比较简单，大家可以自己试试，不过import需要webpack打包。如果不会实现的可以参考博文专题 《TypeScript 语言基础专题》 中TypeScript 重载章节找到源码，也可以采用一般的for循环完成一样的功能。
// range生成序列，与Python的range类似。是一系列重载的range函数。 import {range} from './tools' // 创建链表 let list: LinkList = new LinkList(); // append()添加元素 for(let i:number =1; i<=6; i++){ list.append( new Lnode(i.toString()) ) }; // 转换为数组 console.log(list.toArray()); // 遍历链表 list.toArray().forEach((val, idx) => { console.log(val) // val: 当前值 console.log(idx) // idx: 节点再链表中的位置 });
2.5.4 测试：分别在链表的左右各插入几个节点
// 创建链表 let list: LinkList = new LinkList(); // append()添加元素 for(let i:number =1; i<=3; i++){ list.append( new Lnode(i.toString()) ) }; // append_left()添加元素 for(let i:number =1; i<=3; i++){ list.append_left( new Lnode("向左边插入的第i="+i+"个元素") ) };
2.5.5 测试：在某个链表中，索引为index的位置插入节点
// 创建链表 let list: LinkList = new LinkList(); // append()添加元素 for(let i:number =1; i<=6; i++){ list.append( new Lnode(i.toString()) ) }; // 在索引号为`3`的位置插入节点，其数据为字符串"TypeScript" list.insert(3,new Lnode("TypeScript")); // 转换为数组输出 console.log(list.toArray())
2.5.6 测试：清空链表与链表判空
新建一个列表判断是否为空：
// 创建链表 let list: LinkList = new LinkList(); // 创建链表 let list: LinkList = new LinkList(); console.log(list.is_empty())
清空一个链表，清空后判断是否为空
// append()添加元素 for(let i:number =1; i<=6; i++){ list.append( new Lnode(i.toString()) ) }; list.clear() console.log(list.is_empty())
2.5.7 获取链表长度
// 创建链表 let list: LinkList = new LinkList(); // append_left()添加元素 for(let i:number =1; i<=3; i++){ list.append_left( new Lnode("向左边插入的第i="+i+"个元素") ) }; // 输出链表的长度 console.log("链表的长度为: "+list.length); // 输出链表是否为空 console.log(list.is_empty());
附录：
附录1：使用webpack打包后链表代码singly_linked_list_01_webpack.js
/* * ATTENTION: The "eval" devtool has been used (maybe by default in mode: "development"). * This devtool is neither made for production nor for readable output files. * It uses "eval()" calls to create a separate source file in the browser devtools. * If you are trying to read the output file, select a different devtool (https://webpack.js.org/configuration/devtool/) * or disable the default devtool with "devtool: false". * If you are looking for production-ready output files, see mode: "production" (https://webpack.js.org/configuration/mode/). */ /******/ (() => { // webpackBootstrap /******/ "use strict"; /******/ var __webpack_modules__ = ({ /***/ "./singly_linked_list_01.ts": /*!**********************************!*\ !*** ./singly_linked_list_01.ts ***! \**********************************/ /***/ ((__unused_webpack_module, exports, __webpack_require__) => { eval("\r\n/**\r\n * @author 李俊才 291148484@163.com\r\n * @version 1.0\r\n */\r\nObject.defineProperty(exports, \"__esModule\", ({ value: true }));\r\nvar tools_1 = __webpack_require__(/*! ./tools */ \"./tools.ts\");\r\n// 该函数写在另一个文件中，要让浏览器支持则需要 webpack 打包。其用法如下：\r\n// console.log(range([10])); // [end]\r\n// console.log(range([5,10])); // [start, end]\r\n// console.log(range([0,10,2])); // [start, end, step]\r\nvar Lnode = /** @class */ (function () {\r\n function Lnode(data) {\r\n if (data != undefined) { // 非空节点\r\n this.empty = false; // 空标识置为假\r\n this.data = data;\r\n this.next = null;\r\n }\r\n else { // 空节点，即值构建节点对象但实际上不存在节点\r\n this.empty = true; // 空标识置为真\r\n this.data = null;\r\n this.next = null;\r\n }\r\n }\r\n Lnode.prototype.append = function (node) {\r\n /**\r\n * 将新节点挂载到节点链尾部\r\n * @param node {Lnode} 需要插入链表尾部的新节点\r\n */\r\n if (this.empty == true) { // 空节点\r\n //console.log(\"空节点\")\r\n this.empty = false;\r\n this.data = node.data;\r\n }\r\n else {\r\n //console.log(\"非空节点\")\r\n if (this.next == null) { // 没有链接下一个\r\n this.next = node;\r\n }\r\n else { // 有链接下一个\r\n this.next.append(node);\r\n }\r\n }\r\n };\r\n Lnode.prototype.toString = function () {\r\n return this.data.toString();\r\n };\r\n return Lnode;\r\n}());\r\n;\r\nvar LinkList = /** @class */ (function () {\r\n function LinkList(datas) {\r\n /**初始化 */\r\n if (datas == undefined) {\r\n this.head = null; // 初始化为null算作空链表，不计算长度\r\n this.length = 0;\r\n }\r\n else {\r\n for (var i = 0; i < datas.length; i++) {\r\n this.append(new Lnode(datas[i]));\r\n }\r\n this.length = datas.length; // 指定一组数据初始化则初始后长度为这组数据元素的个数\r\n }\r\n ;\r\n }\r\n LinkList.prototype.is_empty = function () {\r\n /**\r\n * 判断链表是否为空\r\n * 只需要判断头节点是否为空，若头节点为空则为空链表，否则不是。\r\n * @return {Boolean} true:链表为空; false:链表非空。\r\n */\r\n if (this.head == null) {\r\n return true;\r\n }\r\n else {\r\n return false;\r\n }\r\n };\r\n LinkList.prototype.top = function () {\r\n /**\r\n * 获取链表头节点\r\n */\r\n var node = this.head;\r\n node.next = null;\r\n return node;\r\n };\r\n LinkList.prototype.clear = function () {\r\n /**\r\n * 清空链表，只要把头节点干废，整个链表直接就完蛋（清空）了\r\n */\r\n this.head = null;\r\n this.length = 0;\r\n };\r\n LinkList.prototype.append = function (node) {\r\n /**\r\n * 将新节点挂载到链表尾部\r\n * @param node {Lnode} 需要插入链表尾部的新节点\r\n */\r\n if (this.head == null) {\r\n this.head = node;\r\n this.length = this.length + 1;\r\n }\r\n else {\r\n this.head.append(node);\r\n this.length = this.length + 1;\r\n }\r\n };\r\n LinkList.prototype.append_left = function (node) {\r\n /**\r\n * 将一个新节点插入到链表首部\r\n */\r\n if (this.head == null) {\r\n this.head = node; // 若为空链表，直接将链表头设置为该节点\r\n this.length = this.length + 1; // 增加节点长度\r\n }\r\n else {\r\n // 先将新节点的`next`指向原第一个节点\r\n node.next = this.head;\r\n // 再将`head`指向新的节点\r\n this.head = node;\r\n this.length = this.length + 1; // 增加节点长度\r\n }\r\n };\r\n LinkList.prototype.get = function (index) {\r\n /**\r\n * 获取索引号为`index`的节点。\r\n * 索引号是从数字`0`开始计算的\r\n */\r\n var pointer = this.head; // 从头节点开始\r\n tools_1.range([index - 1]).forEach(function () {\r\n pointer = pointer.next; // 逐个指向下一个节点\r\n });\r\n pointer.next = null; // 斩断后继\r\n return pointer;\r\n };\r\n LinkList.prototype.insert = function (index, node) {\r\n /**\r\n * 在链表的第`index`个节的位置挂载新的节点`node`，其中从节点为`index = 0`开始编号\r\n * 也就是说，新的节点索引号将为`index`，而这个节点将挂载到索引号为`index-1`的节点后面\r\n *\r\n * @param index {number} 新节点插入的索引号\r\n */\r\n if (node != null && node.next == null) {\r\n node.next = null;\r\n } // 只允许插入单个节点，若有后继直接切断\r\n if (index == 0) {\r\n node.next = this.head; // 先收小弟\r\n this.head = node; // 再上位\r\n }\r\n else {\r\n var pointer = this.head; // 从头节点开始\r\n var results = new Lnode(); // 空节点\r\n for (var i = 0; i < index; i++) {\r\n results.append(new Lnode(pointer.data)); // 逐个记录先驱节点\r\n pointer = pointer.next; // 逐个指向下一个节点\r\n }\r\n node.next = pointer; // 先收小弟\r\n results.append(node); // 再上位\r\n this.length = this.length + 1; // 更新节点长度\r\n this.head = results;\r\n }\r\n };\r\n LinkList.prototype.toArray = function () {\r\n /**\r\n * 获取链表节点依次构成的数组\r\n * @returns elem {Lnode[]} 以此装载了被遍历到的所有节点（这里其中每个节点都是孤立、干掉next的）\r\n */\r\n var elm = []; // 准备好用于容纳所有的节点\r\n var pointer = this.head; // 挂载操作一开始时指针指向头部节点、\r\n if (pointer == null) { // 空链表，不仅要返回一个空数组，还要抛出提示\r\n console.warn(\"Warning: It seems that you hava traversed an empty Linked List!\");\r\n return elm;\r\n }\r\n else { // 非空链表\r\n while (pointer.next != null) { // 存在下一个节点时\r\n if (pointer == null) { // 停止（拦截）条件：（直到）节点为`null`\r\n break;\r\n }\r\n else { // 获取当前节点剔除链接关系的`孤立节点`挂载节点数组\r\n elm.push(new Lnode(pointer.data));\r\n }\r\n pointer = pointer.next; // 指向后继\r\n }\r\n elm.push(new Lnode(pointer.data)); // 最后一个元素\r\n return elm;\r\n }\r\n };\r\n return LinkList;\r\n}());\r\n\n\n//# sourceURL=webpack://linklist/./singly_linked_list_01.ts?"); /***/ }), /***/ "./tools.ts": /*!******************!*\ !*** ./tools.ts ***! \******************/ /***/ ((__unused_webpack_module, exports) => { eval("\r\n/**\r\n * @author 李俊才 291148484@163.com\r\n * @version 1.0\r\n */\r\nObject.defineProperty(exports, \"__esModule\", ({ value: true }));\r\nexports.range = void 0;\r\nfunction range(x) {\r\n var ar = [];\r\n if (x.length == 1) {\r\n // 重载：传入数组只有1个元素\r\n for (var i = 0; i < x[0]; i++) {\r\n ar.push(i);\r\n }\r\n }\r\n else if (x.length == 2) {\r\n // 重载：传入2元素数组\r\n for (var i = x[0]; i < x[1]; i++) {\r\n ar.push(i);\r\n }\r\n }\r\n else if (x.length == 3) {\r\n // 重载：传入3元素数组\r\n for (var i = x[0]; i < x[1]; i += x[2]) {\r\n ar.push(i);\r\n }\r\n }\r\n return ar;\r\n}\r\nexports.range = range;\r\n;\r\n// console.log(range(\r\n// [5]\r\n// ));\r\n// console.log(range(\r\n// [5,10]\r\n// ));\r\n// console.log(range(\r\n// [0,10,2]\r\n// ));\r\n\n\n//# sourceURL=webpack://linklist/./tools.ts?"); /***/ }) /******/ }); /************************************************************************/ /******/ // The module cache /******/ var __webpack_module_cache__ = {}; /******/ /******/ // The require function /******/ function __webpack_require__(moduleId) { /******/ // Check if module is in cache /******/ var cachedModule = __webpack_module_cache__[moduleId]; /******/ if (cachedModule !== undefined) { /******/ return cachedModule.exports; /******/ } /******/ // Create a new module (and put it into the cache) /******/ var module = __webpack_module_cache__[moduleId] = { /******/ // no module.id needed /******/ // no module.loaded needed /******/ exports: {} /******/ }; /******/ /******/ // Execute the module function /******/ __webpack_modules__[moduleId](module, module.exports, __webpack_require__); /******/ /******/ // Return the exports of the module /******/ return module.exports; /******/ } /******/ /************************************************************************/ /******/ /******/ // startup /******/ // Load entry module and return exports /******/ // This entry module can't be inlined because the eval devtool is used. /******/ var __webpack_exports__ = __webpack_require__("./singly_linked_list_01.ts"); /******/ /******/ })() ;
编译的JavaScript
Sources
/** * @author 李俊才 291148484@163.com * @version 1.0 */ Object.defineProperty(exports, "__esModule", ({ value: true })); var tools_1 = __webpack_require__(/*! ./tools */ "./tools.ts"); // 该函数写在另一个文件中，要让浏览器支持则需要 webpack 打包。其用法如下： // console.log(range([10])); // [end] // console.log(range([5,10])); // [start, end] // console.log(range([0,10,2])); // [start, end, step] var Lnode = /** @class */ (function () { function Lnode(data) { if (data != undefined) { // 非空节点 this.empty = false; // 空标识置为假 this.data = data; this.next = null; } else { // 空节点，即值构建节点对象但实际上不存在节点 this.empty = true; // 空标识置为真 this.data = null; this.next = null; } } Lnode.prototype.append = function (node) { /** * 将新节点挂载到节点链尾部 * @param node {Lnode} 需要插入链表尾部的新节点 */ if (this.empty == true) { // 空节点 //console.log("空节点") this.empty = false; this.data = node.data; } else { //console.log("非空节点") if (this.next == null) { // 没有链接下一个 this.next = node; } else { // 有链接下一个 this.next.append(node); } } }; Lnode.prototype.toString = function () { return this.data.toString(); }; return Lnode; }()); ; var LinkList = /** @class */ (function () { function LinkList(datas) { /**初始化 */ if (datas == undefined) { this.head = null; // 初始化为null算作空链表，不计算长度 this.length = 0; } else { for (var i = 0; i < datas.length; i++) { this.append(new Lnode(datas[i])); } this.length = datas.length; // 指定一组数据初始化则初始后长度为这组数据元素的个数 } ; } LinkList.prototype.is_empty = function () { /** * 判断链表是否为空 * 只需要判断头节点是否为空，若头节点为空则为空链表，否则不是。 * @return {Boolean} true:链表为空; false:链表非空。 */ if (this.head == null) { return true; } else { return false; } }; LinkList.prototype.top = function () { /** * 获取链表头节点 */ var node = this.head; node.next = null; return node; }; LinkList.prototype.clear = function () { /** * 清空链表，只要把头节点干废，整个链表直接就完蛋（清空）了 */ this.head = null; this.length = 0; }; LinkList.prototype.append = function (node) { /** * 将新节点挂载到链表尾部 * @param node {Lnode} 需要插入链表尾部的新节点 */ if (this.head == null) { this.head = node; this.length = this.length + 1; } else { this.head.append(node); this.length = this.length + 1; } }; LinkList.prototype.append_left = function (node) { /** * 将一个新节点插入到链表首部 */ if (this.head == null) { this.head = node; // 若为空链表，直接将链表头设置为该节点 this.length = this.length + 1; // 增加节点长度 } else { // 先将新节点的`next`指向原第一个节点 node.next = this.head; // 再将`head`指向新的节点 this.head = node; this.length = this.length + 1; // 增加节点长度 } }; LinkList.prototype.get = function (index) { /** * 获取索引号为`index`的节点。 * 索引号是从数字`0`开始计算的 */ var pointer = this.head; // 从头节点开始 tools_1.range([index - 1]).forEach(function () { pointer = pointer.next; // 逐个指向下一个节点 }); pointer.next = null; // 斩断后继 return pointer; }; LinkList.prototype.insert = function (index, node) { /** * 在链表的第`index`个节的位置挂载新的节点`node`，其中从节点为`index = 0`开始编号 * 也就是说，新的节点索引号将为`index`，而这个节点将挂载到索引号为`index-1`的节点后面 * * @param index {number} 新节点插入的索引号 */ if (node != null && node.next == null) { node.next = null; } // 只允许插入单个节点，若有后继直接切断 if (index == 0) { node.next = this.head; // 先收小弟 this.head = node; // 再上位 } else { var pointer = this.head; // 从头节点开始 var results = new Lnode(); // 空节点 for (var i = 0; i < index; i++) { results.append(new Lnode(pointer.data)); // 逐个记录先驱节点 pointer = pointer.next; // 逐个指向下一个节点 } node.next = pointer; // 先收小弟 results.append(node); // 再上位 this.length = this.length + 1; // 更新节点长度 this.head = results; } }; LinkList.prototype.toArray = function () { /** * 获取链表节点依次构成的数组 * @returns elem {Lnode[]} 以此装载了被遍历到的所有节点（这里其中每个节点都是孤立、干掉next的） */ var elm = []; // 准备好用于容纳所有的节点 var pointer = this.head; // 挂载操作一开始时指针指向头部节点、 if (pointer == null) { // 空链表，不仅要返回一个空数组，还要抛出提示 console.warn("Warning: It seems that you hava traversed an empty Linked List!"); return elm; } else { // 非空链表 while (pointer.next != null) { // 存在下一个节点时 if (pointer == null) { // 停止（拦截）条件：（直到）节点为`null` break; } else { // 获取当前节点剔除链接关系的`孤立节点`挂载节点数组 elm.push(new Lnode(pointer.data)); } pointer = pointer.next; // 指向后继 } elm.push(new Lnode(pointer.data)); // 最后一个元素 return elm; } }; return LinkList; }());
