JavaScript数据结构_链表树图算法实现-js教程-PHP中文网

JavaScript数据结构_链表树图算法实现

紅蓮之龍

发布： 2025-11-27 18:47:02

原创

840人浏览过

链表、树、图是JavaScript中核心数据结构。链表通过节点连接实现动态存储，支持尾插、指定位置插入与删除；树以二叉搜索树为例，实现节点插入、中序遍历与查找；图采用邻接表表示，支持添加顶点与边，并实现深度优先（DFS）和广度优先（BFS）遍历。三者分别适用于线性、层级与网状关系的数据处理，是算法设计与开发中的基础工具。

javascript数据结构_链表树图算法实现

链表、树、图是JavaScript中常见的数据结构，它们在算法实现和实际开发中应用广泛。下面分别介绍这三种数据结构的基本实现方式及常用操作。

链表（Linked List）

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

节点定义：

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

登录后复制

单向链表实现：

立即学习“Java免费学习笔记（深入）”；

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
<pre class='brush:php;toolbar:false;'>// 在尾部添加节点
append(val) {
    const node = new ListNode(val);
    if (!this.head) {
        this.head = node;
    } else {
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = node;
    }
    this.size++;
}

// 插入节点到指定位置
insertAt(index, val) {
    if (index < 0 || index > this.size) return false;
    const node = new ListNode(val);
    if (index === 0) {
        node.next = this.head;
        this.head = node;
    } else {
        let current = this.head;
        for (let i = 0; i < index - 1; i++) {
            current = current.next;
        }
        node.next = current.next;
        current.next = node;
    }
    this.size++;
    return true;
}

// 删除指定值的节点
remove(val) {
    if (!this.head) return null;
    if (this.head.val === val) {
        this.head = this.head.next;
        this.size--;
        return val;
    }
    let current = this.head;
    while (current.next && current.next.val !== val) {
        current = current.next;
    }
    if (current.next) {
        current.next = current.next.next;
        this.size--;
        return val;
    }
    return null;
}

登录后复制

}

树（Tree）— 二叉树与二叉搜索树

树是非线性结构，常用于表示层级关系。二叉树每个节点最多有两个子节点。

二叉树节点定义：

Matlab语言的特点中文WORD版

本文档主要讲述的是Matlab语言的特点；Matlab具有用法简单、灵活、程式结构性强、延展性好等优点，已经逐渐成为科技计算、视图交互系统和程序中的首选语言工具。特别是它在线性代数、数理统计、自动控制、数字信号处理、动态系统仿真等方面表现突出，已经成为科研工作人员和工程技术人员进行科学研究和生产实践的有利武器。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看

查看详情

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

登录后复制

二叉搜索树（BST）实现：

class BST {
    constructor() {
        this.root = null;
    }
<pre class='brush:php;toolbar:false;'>// 插入节点
insert(val) {
    const node = new TreeNode(val);
    if (!this.root) {
        this.root = node;
    } else {
        this._insertNode(this.root, node);
    }
}

_insertNode(root, node) {
    if (node.val < root.val) {
        if (!root.left) {
            root.left = node;
        } else {
            this._insertNode(root.left, node);
        }
    } else {
        if (!root.right) {
            root.right = node;
        } else {
            this._insertNode(root.right, node);
        }
    }
}

// 中序遍历（升序输出）
inorder(node = this.root, result = []) {
    if (node) {
        this.inorder(node.left, result);
        result.push(node.val);
        this.inorder(node.right, result);
    }
    return result;
}

// 查找节点
search(val, node = this.root) {
    if (!node) return null;
    if (val === node.val) return node;
    if (val < node.val) {
        return this.search(val, node.left);
    } else {
        return this.search(val, node.right);
    }
}

登录后复制

}

图（Graph）

图由节点（顶点）和边组成，可用于表示复杂关系网络。

图的邻接表实现：

class Graph {
    constructor() {
        this.adjacencyList = new Map();
    }
<pre class='brush:php;toolbar:false;'>// 添加顶点
addVertex(v) {
    if (!this.adjacencyList.has(v)) {
        this.adjacencyList.set(v, []);
    }
}

// 添加边（无向图）
addEdge(v, w) {
    this.addVertex(v);
    this.addVertex(w);
    this.adjacencyList.get(v).push(w);
    this.adjacencyList.get(w).push(v);
}

// 深度优先遍历（DFS）
dfs(start) {
    const visited = new Set();
    const result = [];

    const traverse = (vertex) => {
        if (!vertex) return;
        result.push(vertex);
        visited.add(vertex);
        this.adjacencyList.get(vertex).forEach(neighbor => {
            if (!visited.has(neighbor)) {
                traverse(neighbor);
            }
        });
    };

    traverse(start);
    return result;
}

// 广度优先遍历（BFS）
bfs(start) {
    const queue = [start];
    const visited = new Set([start]);
    const result = [];

    while (queue.length) {
        const vertex = queue.shift();
        result.push(vertex);
        this.adjacencyList.get(vertex).forEach(neighbor => {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        });
    }
    return result;
}

登录后复制

}

这些基础实现涵盖了链表、树、图的核心操作。理解其原理有助于解决如路径查找、排序、递归等常见算法问题。基本上就这些，不复杂但容易忽略细节。

以上就是JavaScript数据结构_链表树图算法实现的详细内容，更多请关注php中文网其它相关文章！