欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

用TS实现链表结构

程序员文章站 2022-07-14 18:46:31
...

用TS实现链表结构

戳蓝字"

前端优选

"

关注我们哦

前面的几篇文章做了很多铺垫,学习TypeScript的一些基本入门知识,这次将使用TS来实现链表结构,并实现链表的反转操作。

什么是链表

链表是用来存储有序的元素集合,与数组不同,链表中的元素并非保存在连续的存储空间内,而是由每个元素本身的节点和一个指向下一个元素的指针构成。当要移动或删除元素时,仅需对元素上的指针进行修改即可,对比数组元素的操作效率,链表则更胜一筹。

因此,需要首选定义一个元素节点的接口,然后去实现它:

//由于Node属于内置类,这里给节点起的名字规避了Node
interface Nodea{
    element: number;
    next: object;
}
class Nodea implements Nodea{
    public element:number;
    public next:object;
    constructor(element:number,next:object){
        this.element = element;
        this.next = next;
    }
}

定义接口的element和next属性,然后再通过类进行具体实现。这里规定存放的值即为数字。

接下来就是要生成一个链表。

创建链表

首先创建一个类,它具有head属性和size属性,head是链表的头,用来记录链表的第一个元素节点;size用来描述当前链表的长度,在后续的遍历中将会用到。

class LinkList{
    public head;
    public size;
    constructor(){
        this.head = null;
        this.size = 0;
    }
}

链表还有很多操作方法,例如:add,remove,getNode,indexOf,length,empty等等,这里我们将只实现主要方法,其他方法大家可以根据兴趣自行尝试一下。

getNode

获取其中一个元素,该方法较其他方法更为基础,因此第一个 先实现它。

getNode(index:number):Nodea{
    let current = this.head;
    for(let i=0;i<index;i++){
        current = current.next;
    }
    return current;
}

通过要查找的索引,逐层遍历并返回相应元素。这里规定了参数必须为Number类型,返回的是Nodea实例。

add

添加元素节点

add(index:number,element?:number):void{
    if(arguments.length == 1){
        element = index;
        index = this.size;
    }
    if(index < 0 || index > this.size) throw new Error('创建索引异常!');
    if(index == 0){
     let head = this.head;
     this.head = new Nodea(element,head);
    }else{
     let prevNode:Nodea = this.getNode(index - 1);
     prevNode.next = new Nodea(element,prevNode.next);
    }
    this.size ++;
}

创建元素,可以根据索引在指定位置插入,也可默认将新建元素插入到链表的末尾,因此该方法的element为可选参数。当只有一个参数时,直接将该元素放到链表最后。

let ll = new LinkList();
ll.add(0,88);
ll.add(99);
//Nodea { element: 88, next: Node { element: 99, next: null } }

当创建索引为0时,则该元素直接为链表的新头部元素;当索引不为0时,则将记录该索引处的前后元素指针,用新元素来记录前后节点,达到插入元素的目的。

let ll = new LinkedList();
ll.add(0,88);
ll.add(0,77);
ll.add(99);
//Node { element: 99, next: Node { element: 88, next: Node { element: 77, next: null } }}

插入元素成功后,别忘了size++,这一点很重要。

remove

删除链表元素,主要在于定位元素:

remove(index:number):Nodea{
    let oldNode;
    if(index == 0){
     oldNode = this.head;
        this.head = oldNode && oldNode.next;
    }else{
     let prevNode:Nodea = this.getNode(index-1);
      oldNode = prevNode.next;
     prevNode.next = oldNode.next;
    }
    this.size --;
    return oldNode && oldNode.element;
}

如果索引为0,则将头部直接指向下一个元素即可;如果索引不为0,则需要通过getNode方法查找到对应位置,然后改变元素的next指针,达到删除的目的。

同时,可以将删除的元素返回,并将size--

length

这是最简单的一个方法,获取链表的长度:

length():number{
 return this.size;
}

这里直接使用链表的size属性,因此在改变链表长度的时候,一定要记得增加或减小size属性。

链表反转

链表有很多种操作方法,这里介绍一个最常见的,就是链表反转。

reverseLinkList():LinkList{
    let head = this.head;
    if(head == null || head.next == null) return head;
    let newHead = null;
    while(head !== null){
        let temp = head.next;
        head.next = newHead;
        newHead = head;
        head = temp;
    }
    this.head = newHead
    return this.head;
}

这里使用一个临时变量来存放元素,然后做到相互交换的效果,达到反转的目的。类似下面这张图:

用TS实现链表结构

通过临时变量达到互换的目的。

let ll = new LinkedList();
ll.add(0,88);
ll.add(0,77);
ll.add(99);
let reverse = ll.reverseLinkList();
//Nodea {element: 99,next: Nodea { element: 88, next: Nodea { element: 77, next: null } }}

到此,一个简单的链表实现和操作就完成了,对于TS的应用可能还有不详尽的地方,欢迎大家指出交流~

用TS实现链表结构

历史好文推荐:

1、TypeScript入门指北(一)                       

2、TypeScript入门指北(二)                        

3、TypeScript入门指北(三)                           

用TS实现链表结构

❤️ 感谢大家

如果你觉得这篇内容对你挺有有帮助的话:

  1. 点赞支持下吧,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)

  2. 关注公众号【前端优选】,定期为你推送好文。

用TS实现链表结构

添加个人微信,进群与小伙伴一起玩耍(已经推出)~

用TS实现链表结构

点个在看,大家都看 用TS实现链表结构