數(shù)據(jù)結(jié)構(gòu)TypeScript之鏈表實(shí)現(xiàn)詳解

更新時間：2023年01月30日 09:40:59 作者：前端技術(shù)獺

這篇文章主要為大家介紹了數(shù)據(jù)結(jié)構(gòu)TypeScript之鏈表實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

鏈表結(jié)構(gòu)特點(diǎn)

鏈表是線性表的其中一種，用于存儲有固定順序的元素。而元素之間會通過”鏈“連接在一起。

鏈表存儲的元素稱為節(jié)點(diǎn)。每個節(jié)點(diǎn)內(nèi)部存在兩個值。如下：

this.element：鏈表需要存儲的單個元素
this.next：指向下一個節(jié)點(diǎn)，也就是鏈表中的”鏈“，將節(jié)點(diǎn)連接在一起。

嘗試手動構(gòu)建鏈表結(jié)構(gòu)。過程如下：

class LinkedListNode {
    constructor(element) {
        this.element = element  // 鏈表要存儲的值
        this.next = null        // 當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
    }
}
let A = new LinkedListNode('A') // 第一個節(jié)點(diǎn)A
let B = new LinkedListNode('B') // 第二個節(jié)點(diǎn)B
let C = new LinkedListNode('C') // 第三個節(jié)點(diǎn)C
// 節(jié)點(diǎn)之間通過this.next屬性值連起來，如下：
A.next = B // 節(jié)點(diǎn)A下一個是節(jié)點(diǎn)B
B.next = C // 節(jié)點(diǎn)B下一個是節(jié)點(diǎn)C
console.log(A) // 輸出鏈表：A -> B -> C

面向?qū)ο蠓椒ǚ庋b鏈表

構(gòu)造函數(shù)

基本單元：鏈表節(jié)點(diǎn)

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
    }
}

查找節(jié)點(diǎn)

設(shè)計(jì)一個方法，可以獲取當(dāng)前節(jié)點(diǎn)的前中后三個節(jié)點(diǎn)。這樣可以極大的方便接下來的增刪操作。如下：

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 }
    }
}

增加節(jié)點(diǎn)

新節(jié)點(diǎn)可插入的范圍：index >= 0 && index <= this.length。也就是說，可以在每個節(jié)點(diǎn)的前后都可以插入新的節(jié)點(diǎn)。

增加節(jié)點(diǎn)的情況分為四種，如下分析：

鏈表為空，不存在節(jié)點(diǎn)：直接將新節(jié)點(diǎn)的值賦給頭節(jié)點(diǎn)。
在頭部之前插入節(jié)點(diǎn)（存在index參數(shù)且范圍符合）：利用新節(jié)點(diǎn)的next緩存當(dāng)前頭節(jié)點(diǎn)，然后新節(jié)點(diǎn)覆蓋頭節(jié)點(diǎn)。
在兩個節(jié)點(diǎn)之間插入節(jié)點(diǎn)（存在index參數(shù)且范圍符合）：利用新節(jié)點(diǎn)的next緩存當(dāng)前節(jié)點(diǎn)，改變前一個節(jié)點(diǎn)的next指向新節(jié)點(diǎn)。
在尾部插入節(jié)點(diǎn)：遍歷到最后一個節(jié)點(diǎn)，在節(jié)點(diǎn)末尾插入節(jié)點(diǎn)。

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
}

刪除節(jié)點(diǎn)

鏈表節(jié)點(diǎn)的刪除范圍：index >= 0 && index < this.length。打個比方，鏈表長度為3，那么可刪除的位置為0，1，2。

刪除節(jié)點(diǎn)的情況分為三種，如下分析：

刪除頭節(jié)點(diǎn)：鏈表長度為1，頭節(jié)點(diǎn)置空。鏈表長度大于1，頭節(jié)點(diǎn)的下一個節(jié)點(diǎn)覆蓋當(dāng)前頭節(jié)點(diǎn)。
刪除中間節(jié)點(diǎn)（存在index參數(shù)且范圍符合）：前一個節(jié)點(diǎn)的next直接指向當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)。
刪除尾節(jié)點(diǎn)：找到尾節(jié)點(diǎn)的前一個節(jié)點(diǎn)，將它的next屬性置空。

注意：每次刪除都將改變鏈表的長度，而節(jié)點(diǎn)的刪除位置也會跟著改變。

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
    }
}

本文相關(guān)代碼已放置我的Github倉庫 ??

項(xiàng)目地址：Algorithmlib｜LinkedList

以上就是數(shù)據(jù)結(jié)構(gòu)TypeScript之鏈表實(shí)現(xiàn)詳解的詳細(xì)內(nèi)容，更多關(guān)于TypeScript數(shù)據(jù)結(jié)構(gòu)鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: