亲宝软件园·资讯

展开

数据结构TypeScript之链表实现详解

前端技术獭 人气:0

链表结构特点

链表线性表的其中一种,用于存储有固定顺序的元素。而元素之间会通过”链“连接在一起。

链表存储的元素称为节点。每个节点内部存在两个值。如下:

尝试手动构建链表结构。过程如下:

class LinkedListNode {
    constructor(element) {
        this.element = element  // 链表要存储的值
        this.next = null        // 当前节点的下一个节点
    }
}
let A = new LinkedListNode('A') // 第一个节点A
let B = new LinkedListNode('B') // 第二个节点B
let C = new LinkedListNode('C') // 第三个节点C
// 节点之间通过this.next属性值连起来,如下:
A.next = B // 节点A下一个是节点B
B.next = C // 节点B下一个是节点C
console.log(A) // 输出链表:A -> B -> C

面向对象方法封装链表

构造函数

基本单元:链表节点

class LinkedListNode {
    element: any
    next: (null | LinkedListNode)
    constructor(element: any) {
        this.element = element
        this.next = null
    }
}

主体:链表

class LinkedList {
    length: number
    head: (null | LinkedListNode)
    constructor() {
        this.length = 0
        this.head = null
    }
}

查找节点

设计一个方法,可以获取当前节点的前中后三个节点。这样可以极大的方便接下来的增删操作。如下:

getLinkedListNode(index: number): (void | { [index: number]: (null | LinkedListNode) }) {
    if (this.isEmpty()) {
        throw new Error('LinkedList is empty')
    } else if (index < 0 || index >= this.length) {
        throw new Error(`${index} does exist in [0, ${this.length})`)
    } else if (index >= 0 && index < this.length) {
        let previous: (null | LinkedListNode) = null
        let current: (null | LinkedListNode) = this.head
        for (let i = 0; i < index; i++) {
            previous = current
            current = current!.next
        }
        return { 0: previous, 1: current, 2: current!.next }
    }
}

增加节点

新节点可插入的范围:index >= 0 && index <= this.length。也就是说,可以在每个节点的前后都可以插入新的节点。

增加节点的情况分为四种,如下分析:

insert(element: any, index?: number): LinkedList {
    let node: (null | LinkedListNode) = new LinkedListNode(element)
    if (this.isEmpty()) {
        this.head = node
    } else if (index !== undefined && (index >= 0 && index < this.length)) {
        if (index === 0) {
            node.next = this.head
            this.head = node
        } else {
            let current: (void | object) = this.getLinkedListNode(index)
            node.next = current[0]!.next
            current[0]!.next = node
        }
    } else if (index !== undefined && (index < 0 || index > this.length)) {
        throw new Error(`${index} does exist in [0, ${this.length}]`)
    } else if (index === undefined || index === this.length) {
        let current: (null | LinkedListNode) = this.head
        while (current!.next !== null) {
            current = current!.next
        }
        current!.next = node
    }
    this.length++
    return this
}

删除节点

链表节点的删除范围:index >= 0 && index < this.length。打个比方,链表长度为3,那么可删除的位置为0,1,2。

删除节点的情况分为三种,如下分析:

注意:每次删除都将改变链表的长度,而节点的删除位置也会跟着改变。

remove(index: number): LinkedList {
    if (this.isEmpty()) {
        throw new Error('LinkedList is empty')
    } else {
        if (index === 0) {
            this.head = (this.length === 1) ? null : this.head!.next
        } else if (index > 0 && index < this.length) {
            let current: (void | object) = this.getLinkedListNode(index)
            current[0]!.next = (index + 1 === this.length) ? null : current[2]
        } else {
            throw new Error(`${index} does exist in [0, ${this.length})`)
        }
        this.length--
        return this
    }
}

本文相关代码已放置我的Github仓库

加载全部内容

相关教程
猜你喜欢
用户评论