链表是一种物理存储单元上非连续、非顺序的存储结构,它由一系列结点组成,其特点在于结点可以在运行时动态生成。
链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起构成单链表。单链表即单向链表,单向指的是其指针域所存储的信息只能为一个方向。具体来说,单链表中的每个存储单元中,除了需要存储每个单元的数据外,还必须附带储存其直接后继存储单元的地址信息。如图所示:
链表是由一个一个节点通过某种关系建立关联构成的一种数据结构,单链表也是如此。单链表中的所有节点只有一个指向各自直接后继节点的指针域以及各自的数据域:
由于在TypeScript中没有指针类型,所以我们需要用一个类来模拟一个结点:
由于在Typescript中泛型可以提高我们代码的可复用性和灵活性,所以下面在定义结点和创建链表时会用到泛型。
class ListNode<T>{ value : T //数据域 next : ListNode<T> | null //指针域 constructor(value: T){ this.value = value; this.next = null } }
增加结点是指为单链表增添节点,增加元素的方法有很多:
//添加结点 add(value:T){ const newNode = new ListNode(value); //首先需要创建一个新结点 //头结点为空,那么这个新结点就是链表的头结点 if(!this.head){ this.head=newNode; } //头结点非空 else{ let current = this.head; //遍历链表,直到找到链表的末尾 while(current.next) { current = current.next } current.next = newNode;//将链表的最后一个节点的指针域指向新创建的结点 } }
删除结点是从链表中删除一个结点,同样删除的方法也有很多:
remove(value : T){ const newNode = new ListNode(value); let current = this.head; if(!current){ console.log('该结点不存在,删除失败') } //删除的结点是头结点 else if(current && current.value == value){ this.head = current.next; console.log('删除成功'); } else{ while(current.next){ if(current.next.value==value){ //让所要删除结点的上一个结点的指针域 //直接指向所要删除结点的下一个结点即可 current.next = current.next.next; console.log('删除成功'); return; } current = current.next; } console.log('该结点不存在,删除失败') } }
打印链表很简单,就是将这个链表的每个结点都遍历一次并且每遍历到一个结点就将这个结点的数据输出即可
//打印链表 print(){ let current = this.head; while(current){ console.log(current); current = current.next } }
测试结果如下:
测试结果如下:
//链表 //定义一个结点类: class ListNode<T>{ value : T next : ListNode<T> | null constructor(value: T){ this.value = value; this.next = null } } //定义一个链表类 class LinkList<T>{ head:null | ListNode<T> constructor(){ this.head = null; } //定义方法 //添加结点 add(value:T){ const newNode = new ListNode(value); //头结点为空 if(!this.head){ this.head=newNode; } //头结点非空 else{ let current = this.head; while(current.next) { current = current.next } current.next = newNode; } } //删除结点 remove(value : T){ const newNode = new ListNode(value); let current = this.head; if(!current){ console.log('该结点不存在,删除失败') } else if(current && current.value == value){ this.head = current.next; console.log('删除成功'); } else{ while(current.next){ if(current.next.value==value){ current.next = current.next.next; console.log('删除成功'); return; } current = current.next; } console.log('该结点不存在,删除失败') } } //打印链表 print(){ let current = this.head; while(current){ console.log(current); current = current.next } } } let list = new LinkList() list.add(10); list.add('hello'); list.add(true); list.print(); list.remove('hello'); list.print();
到此这篇关于TypeScript实现单链表的示例代码的文章就介绍到这了,更多相关TypeScript 单链表内容请搜索插件窝以前的文章或继续浏览下面的相关文章希望大家以后多多支持插件窝!