用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实现链表结构