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

作者：函数茶馆时间：2026-10-26 09:49:02浏览：605

本文详细解析TypeScript中链表的实现原理与代码构建。从节点类的封装入手，讲解如何通过next指针连接元素，并完整演示查找、插入及删除节点的核心逻辑。包含针对空链表、头部、中间及尾部节点处理的边界条件分析，提供完整的TypeScript面向对象实现代码。

链表结构特点

链表属于线性表的一种，专门用于存储具有固定顺序关系的元素集合。各元素之间依靠特定的“链”结构相互关联。

在链表中，被存储的数据单元被称为节点。每个节点内部包含两个关键属性值，具体结构如下：

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。这意味着可以在链表的任意节点前后位置插入新的数据节点。

增加节点的操作需根据当前链表状态分为四种情况进行分析：

当链表为空，即不存在任何节点时：直接将新节点的数据赋值给头节点（head）。
当在头部之前插入节点（存在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属性设置为空，以切断尾节点的引用。

特别注意：每次执行删除操作都会导致链表长度减1，且后续节点的索引位置会随之发生改变，需动态调整。

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

以上就是数据结构TypeScript之链表实现详解的详细内容，更多关于TypeScript数据结构链表的资料请关注本站其它相关文章！

作者最新文章

JS大数值转字符串出现科学计数法怎么办

2026-11-05 17:09:21

JS split切割后出现空字符串怎么过滤

2026-11-05 16:00:30

在 React 或 Vue 项目中封装使用 JS 节流防抖

2026-11-05 15:27:29

JavaScript中怎么将带小数的字符串转为整数？

2026-11-05 14:32:38

怎么用JavaScript策略模式重构电商促销计算逻辑？

2026-11-05 14:01:09