日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

數據結構TypeScript之鏈表實現詳解_其它

作者：前端技術獺 ? 更新時間： 2023-03-26 編程語言

鏈表結構特點

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

鏈表存儲的元素稱為節點。每個節點內部存在兩個值。如下：

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

嘗試手動構建鏈表結構。過程如下：

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。也就是說，可以在每個節點的前后都可以插入新的節點。

增加節點的情況分為四種，如下分析：

  • 鏈表為空，不存在節點：直接將新節點的值賦給頭節點。
  • 在頭部之前插入節點（存在index參數且范圍符合）：利用新節點的next緩存當前頭節點，然后新節點覆蓋頭節點。
  • 在兩個節點之間插入節點（存在index參數且范圍符合）：利用新節點的next緩存當前節點，改變前一個節點的next指向新節點。
  • 在尾部插入節點：遍歷到最后一個節點，在節點末尾插入節點。
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。

刪除節點的情況分為三種，如下分析：

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

注意：每次刪除都將改變鏈表的長度，而節點的刪除位置也會跟著改變。

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倉庫 ?

項目地址：Algorithmlib｜LinkedList

原文鏈接：https://juejin.cn/post/7179930193383915581

欄目分類
最近更新