TypeScript算法专题 -
[双链表1] 双链的概念及其实现
【导读】本文开始，练习双链表相关数据结构与算法。文中实现了一个简单的双链表。
1. 双链表的概念
双链表即所谓双向链表，所谓双向，指的是它的结点有2个指针——其中一个结点指向其直接前驱、另一个指向它的直接后继。
从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
2. 双链表结点的实现
使用类来描述和实现双向链表的结点。那么，结点需要包含两块三个因素。第一块是其指针域，指针域中需要考虑两个方向的指针，一个是前驱指针、另一个是后继指针。对于一个在双向链表中的结点，每每两个之间的连接不是单向的，它一方面通过一个指针指向它的先驱结点，一方面通过一个指针指向它的后继结点，两个指针分别用属性pre、next来表示。另一块是数据域，数据域中存储各种不确定形式的数据，我们预设其类型为any类型。
class Dnode{ /** * 双向链表的结点，相比单向链表它有两个方向 * @class Dnode * @constructor * @param pre {Lnode} 指前驱结点的指针 * @param next {Lnode} 指向后继结点的指针 */ pre: Dnode | undefined | null; // 指向先驱结点 next: Dnode | undefined | null; // 指向后继结点 data:any; // 数据域 constructor(data?:any){ if(data){ this.data = data; this.pre = null; this.next = null; }else{ this.data = null; this.pre = null; this.next = null; } } }
3. 头指针
实话说想实现一个链表，其实真的也未必需要一个头指针，比如我之前的单链表博文给出过头指针也没有的链表的TypeScript的实现。这里设计一个头指针，实际上就是链表结点的挂载点，它用来指向头节点。也就是说，我们认为头指针指向的第一个结点为首元结点。之前的博文已经说过，TypeScript没有C语言中那样的指针的概念，但是可以使用变量建立对对象的引用。我们使用一个类型为链表结点的属性head的next属性来假装头指针，这样我们就可以像对操作其它结点那样来操作首元结点，这也就是头指针的意义，否则，即没有头指针时，我们可能在某些方法中，又需要认为在链表外增加一个挂载点来挂载头节点进行操作。
4. 连接结点，实现双链表
和创建单链表不同的是创建双向链表的过程中每一个新节点都要和前驱节点之间建立两次链接即：
- 将新节点的 pre 指针指向直接前驱节点；
- 将直接前驱节点的 next 指针指向新节点；
export class LinkList{ /** * 双链表类 * @class LinkList * @constructor * @param head {Dnode} 头指针 * @param length {number} 链表的长度 */ head: Dnode | null; // 头指针，只指向一个结点 private length: number; // 链表所容纳结点的个数 constructor(); // 重载：若不传参数则构造一个空链表 constructor(datas:any[]); // 重载：若给定一个数组则将数组中的元素依次放在链表中构造链表 constructor(datas?){ this.head = new Dnode(); this.length = 0; // 初始化长度 if(typeof datas == "object"){ /** * 如果有给定了参数data */ this.head.next = null; for(let i=0; i<datas.length; i++){ this.append(datas[i]) } }else{ /** * 如果没有给定data参数，则构造一个空列表 */ this.head.next = null; } } is_empty():boolean{ /** * 判断是否是空链表 */ if(this.head.next){return true} else{return false} } top(){ /** * 查看链表头部结点（的数据） */ if(this.head.next){ return this.head.next.data }else{ return null } } top_node(){ /** * 查看链表头部结点 */ if(this.head.next){ return this.head.next }else{ return null } } clear():void{ /** * 清空该双链表 */ this.head.next = null; // 不能去清空头指针`head`，而要清空头指针的引用结点`head.next` this.length = 0; } append(data:any):void{ /** * 在双链表右侧（尾）插入新的结点 */ let node = new Dnode(data); // 用数据建立新的结点 if(this.head.next==null){ // 如果指向空即还没有一个结点 this.head.next = node }else{ let pointer = this.head; while(pointer.next){ // 只要结点还存在 pointer = pointer.next // 向后一个结点引用 } node.pre = pointer; pointer.next = node } this.length++; } append_left(data:any):void{ /** * 在双链表左测（头）插入新的结点 */ let node:Dnode = new Dnode(data); if(this.head.next==null){ this.head.next = node; }else{ node.next = this.head.next; this.head.next.pre = node; this.head.next = this.head.next.pre; } this.length++; } insert(index:number, data: any):void{ /** * 在指定索引处插入新的结点 */ let pointer:Dnode = this.head; let ct: number = 0; while(ct < index){ pointer = pointer.next; ct++; } let node = new Dnode(data); node.next = pointer.next; node.pre = pointer; pointer.next = node; } to_node_array(){ /** * 将链表转换为结点数组后返回 * 数组的元素为结点 */ let ar: any[] = []; if(this.head.next){ let pointer = this.head; // 复制头指针的引用 while(pointer.next){ // 引用非空 ar.push(pointer.next); // 转载被引用结点的数据 pointer = pointer.next // 引用后移 } return ar }else{ return ar } } to_array():any[]{ /** * 将链表转换为数组后返回 * 数组的元素为结点的数据域 */ let ar: any[] = []; if(this.head.next){ let pointer = this.head; // 复制头指针的引用 while(pointer.next){ // 引用非空 ar.push(pointer.next.data); // 转载被引用结点的数据 pointer = pointer.next // 引用后移 } return ar }else{ return ar } } }
