使用ts实现单链表

孙泽辉

发布于：2021年8月19日

字数：580字

时长：2分钟

次浏览

单链表用Js写是不是不太好，话说js怎么释放内存？

基本结构

data是数据域，next是指针域，这里不知道有没有指针，我js学的太烂了。。。

interface DataType {
    num: number,
    name: string
}

interface LinkListInterface {
    data: DataType | null;
    next: LinkListInterface | null
}

model

类名起的不太好，应该叫Node才是，这个类本身是个节点，拿到LinkList的时候不过是拿到了整个链表的头结点，所以叫LinkList好了。

class LinkList implements LinkListInterface {
    data: DataType | null;
    next: LinkListInterface | null;

    constructor() {
        this.data = null;
        this.next = null;
    }
}

获取第i个元素

从1到i依次找咯。

getLinkListElement(i: number) {
    let p = this.next, cur = 1;
    while (p != null && cur < i) {
        p = p.next;
        cur++
    }
    if (i === cur) return p;
    return null;
}

插入元素

首先拿到待插入元素的前驱结点，头结点比较特殊，其他的位置就是i的前驱结点。

找到前驱结点之后，新建个空节点，数据放进去，指针指向该节点的前驱结点的后继节点，再将前驱结点的指针域指向待插入元素。

图片取自：(26条消息) 单链表按顺序插入节点_e891377的专栏-CSDN博客_链表插入节点

insertLinkList(x: DataType, i: number) {
    let p = null, newNode;
    if (i === 1) {
        p = this
    } else {
        p = this.getLinkListElement(i - 1);
    }
    if (p === null) {
        throw new Error("can't find insert position!")
    } else {
        newNode = new LinkList()
        newNode.data = x;
        newNode.next = p.next;
        p.next = newNode;
    }
    return this;
}

删除元素

找到前驱结点，将前驱结点的指针域直接接到前驱结点的后继节点的后继节点

DeleteLinkListElement(i: number): boolean {
    let q, p;
    if (i === 1) q = this;
    else q = this.getLinkListElement(i - 1);
    if (q != null && q.next != null) {
        p = q.next;
        q.next = p.next;
        p = null;
        return true;
    } else {
        return false;
    }
}

初始化链表（方法1）

static ArrayToList(DataList: Array<DataType>): LinkListInterface {
    const node = new LinkList();
    let p = node;
    
    DataList.forEach(elem => {
        const t = new LinkList();
        t.data = elem;
        p.next = t;
        p = t;
        console.log(p);
    })
    p.next = null;
    return node;
}

初始化链表（方法2）

static ArrayToList2(DataList: Array<DataType>): LinkListInterface {
    const p = new LinkList();
    DataList.forEach(elem => {
        const t = new LinkList();
        t.data = elem;
        t.next = p.next;
        p.next = t;
    })

    return p;
}

测试就不测了，都是可以跑的。

总结

插入和删除比顺序表快

内存空间占用上可以随机存储