JavaScript 中的 DSA

2025 年 4 月 18 日 | 阅读 12 分钟

本文我们将了解 JavaScript 中的 DSA。

数据结构与算法 (DSA) 是计算机科学的支柱，对于高效解决难题至关重要。它们与各种编程语言（如 C++、Java、Python 等）相关联。现在，JavaScript 编程语言也已成为数据结构和算法概念的强大语言。

什么是数据结构？

数据结构是一种组织、管理和存储数据的方法。数据的组织方式使得访问数据变得简单无碍。

简单来说，我们可以说数据结构是一组数据值及其之间的联系。

JavaScript 中的数组

数组用于存储相关数据的集合，但在 JavaScript 中，我们可以在同一个数组中存储不同类型的数据。数组的每个元素都可以通过其索引值（即数组元素所在的位置编号）来访问。索引值从 0 开始，这意味着如果数组中有 5 个元素，则可以使用索引号 3 访问第 4 个元素。

语法

在上述语法中，const 是用于声明数组的关键字，array_name 是数组的名称。item1、item2 和 item3 是数组中存在的项目。

JavaScript 中的数组还可以存储其他数组。这些类型的数组被称为多维数组。

多维数组的语法

const arr = [
[2, 4, 6],
[8, 10, 12],
[14, 16, 18]
];

数组可以用于各种目的，例如添加数据、删除数据等。

JavaScript 中数组的示例

在下面的演示中，我们将创建一个相同数据类型的数组和不同数据类型的数组。

代码

const electronic_devices = ["LCD", "Refrigerator", "Microwave"]; //same data type
const example = ["BMW", 10, "laptop"]; //different data types
console.log(electronic_devices); //printing array of same data type
console.log(example); ////printing array of different data types

输出

这是我们可以看到数组的输出。

JavaScript 中多维数组的示例

我们将在下面的演示中创建一个多维数组。

代码

const salary = [
	["Remo", 25, 75000],
	["Raghav", 26, 42000],
	["Shakti", 30, 50000],
	["Puneet", 35, 45000],
];
console.log("Salary of Remo : " + salary[0][2]);
console.log("Salary of Raghav : " + salary[1][2]);

输出

这是我们可以看到多维数组的结果。

JavaScript 中的链表

链表是一种用于存储顺序数据的数据结构。链表中存在的元素彼此链接。链表中的第一个元素称为头节点，链表中的最后一个元素称为尾节点。我们可以在链表中放入或删除元素。

创建 Node 类

Node 类包含两个属性

data：它存储节点的实际数据。

next：它存储下一个节点的引用。

语法

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}

创建 LinkedList 类

LinkedList 类显示链表本身。它包含以下两个属性

head：它是第一个节点。

tail：它是最后一个节点。

语法

class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
}

打印 LinkedList 类

以下是用于打印链表中每个节点数据的语法。

语法

printAll() {
   let current = this.head;
   while (current) {
      console.log(current.data);
      current = current.next;
   }
}

在链表中添加新元素的演示

我们将在位置 4 添加节点 y，并在尾部添加节点 x。

代码

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   add(data) {
      const new_node = new Node(data);
      if (!this.head) {
         this.head = new_node;
         this.tail = new_node;
      } else {
         this.tail.next = new_node;
         this.tail = new_node;
      }
      this.length++;
      return this;
   }
   
   addToTail(data) {
      let new_node = new Node(data);
      if (this.head === null) {
         this.head = new_node;
         return;
      }
      let current = this.head;
      while (current.next !== null) {
         current = current.next;
      }
      current.next = new_node;
   }
   
   addAtPosition(data, position) {
      let new_node = new Node(data);
      if (position === 1) {
         new_node.next = this.head;
         this.head = new_node;
         return;
      }
      let current = this.head;
      let i = 1;
      while (i < position - 1 && current) {
         current = current.next;
         i++;
      }
      if (current) {
         new_node.next = current.next;
         current.next = new_node;
      }
   }
   
   it
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();

list.add("Node 1");
list.add("Node 2");
list.add("Node 3");
list.add("Node 4");
console.log("Initial List:");
list.printAll();
console.log("After adding Node y at position 4");
list.addAtPosition("Node y",4);
list.printAll();
console.log("After adding Node x to tail");
list.addToTail("Node x");
list.printAll();

输出

这是输出，我们可以清楚地看到元素节点 y 和节点 x 已添加到链表中。

从链表中删除元素的演示

在下面的演示中，我们将从链表中删除节点 1，然后删除索引 2 的节点。

代码

class Node {
   constructor(data) {
      this.data = data;
      this.next = null;
   }
}
class LinkedList {
   constructor() {
      this.head = null;
      this.tail = null;
      this.length = 0;
   }
   
   add(data) {
      const new_node = new Node(data);
      if (!this.head) {
         this.head = new_node;
         this.tail = new_node;
      } 
      else {
         this.tail.next = new_node;
         this.tail = new_node;
      }
      this.length++;
      return this;
   }
   
   remove(data) {
      if (!this.head) {
         return null;
      }
      if (this.head.data === data) {
         this.head = this.head.next;
         this.length--;
         return this;
      }
      let current = this.head;
      while (current.next) {
         if (current.next.data === data) {
            current.next = current.next.next;
            this.length--;
            return this;
         }
         current = current.next;
      }
      return null;
   }
   
      removeAt(index) {
      if (index < 0 || index >= this.length) return null;
      if (index === 0) return this.remove();
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
         current = current.next;
      }
      current.next = current.next.next;
      this.length--;
      return this;
   }
   
   printAll() {
      let current = this.head;
      while (current) {
         console.log(current.data);
         current = current.next;
      }
   }
}
const list = new LinkedList();
list.add("Node 1");
list.add("Node 2");
list.add("Node 3");
list.add("Node 4");
console.log("Initial List:");
list.printAll();
console.log("List after removing Node 1");
list.remove("Node 1");
list.printAll();
console.log("List after removing node at index 2");
list.removeAt(2);
list.printAll();

输出

这是输出，我们可以清楚地看到节点已从链表中删除。

JavaScript 中的哈希表

哈希表是一种数据结构，允许构建键值对列表。我们可以借助 Object 数据类型和 Map 对象来实现哈希表。

使用 Object 数据类型

我们将使用 Object 数据类型来实现哈希表。

代码

var cars = new Object();

cars['car1'] = 'Hyundai Creta';
cars['car2'] = 'Toyota Urban Cruiser Taisor';
cars['car3'] = 'Mahindra Bolero';

for (var key in cars) {
  if (cars.hasOwnProperty(key)) {
    console.log('key is: ' + key + ', value is: ' + cars[key]);
  }
}

输出

我们可以在以下输出中看到哈希表的实现。

使用 Map 对象

Map 用于存储项目集合，其中每个项目都以键值对的形式存储。我们将使用 Map 对象来实现哈希表。

代码

var cars  = new Map();

cars.set('car1', 'Hyundai Creta');
cars.set('car2', 'Toyota Urban Cruiser Taisor');
cars.set('car3', 'Mahindra Bolero');

console.log(cars.get('car3'));

cars.set('car1', 'Hyundai Creta');

console.log(cars.get('car1'));

console.log(cars.size);

cars.delete('car2');

console.log(cars.size);

for (const [key, value] of cars) {
  console.log(key + ' = ' + value);
}

输出

我们可以在以下输出中看到 Map 对象的实现。

树

树是一种用于连接节点的数据结构。一个节点可能包含零个或多个子节点。树中最上面或顶部的节点称为根节点，最下面的节点称为叶节点。所有从根节点发出的节点都称为子节点。

树的高度通过计算根节点与最远节点之间的距离来确定。

节点的层级或深度通过计算节点与根节点之间的距离来确定。

以下是树的代码

class TreeNode {
  constructor(value) {
    this.value = value;
    this.descendants = [];
  }
}


const seema = new TreeNode('Seema');
const rakhi = new TreeNode('Rakhi');
const krish = new TreeNode('Krish');
const meeta = new TreeNode('Meeta');
const hina = new TreeNode('Hina');

seema.descendants.push(rakhi);
rakhi.descendants.push(krish, meeta, hina);

上面创建的树将如下所示

在上面创建的树中，节点 seema 是根节点。节点 krish、meeta 和 hina 是叶节点。

Seema 的高度是 2，hina 的高度是 0。

krish 的层级或深度是 2，rakhi 的层级或深度是 1。

二叉树

最多包含两个子节点的树称为二叉树。二叉树有多种类型

满二叉树
完全二叉树
完美二叉树

用于搜索的二叉树称为二叉搜索树 (BST)。

实现二叉搜索树 (BST)

class Node{
    constructor(value){
        this.value = value
        this.left = null
        this.right = null
    }
}
class BinarySearchTree {
    constructor(){
        this.root = null
    }
    insert(value){
        const new_node = new Node(value)
        if(this.root === null){
            this.root = new_node
            return this
        }
        let current = this.root
        while(true){
            if(value === current.value) return undefined
            if(value < current.value){
                if(current.left === null){
                    current.left = new_node
                    return this
                }
                current = current.left
            } else {
                if(current.right === null){
                    current.right = new_node
                    return this
                } 
                current = current.right
            }
        }
    }
    find(value){
        if(this.root === null) return false
        let current = this.root,
            found = false
        while(current && !found){
            if(value < current.value){
                current = current.left
            } else if(value > current.value){
                current = current.right
            } else {
                found = true
            }
        }
        if(!found) return undefined
        return current
    }
    contains(value){
        if(this.root === null) return false
        let current = this.root,
            found = false
        while(current && !found){
            if(value < current.value){
                current = current.left
            } else if(value > current.value){
                current = current.right
            } else {
                return true
            }
        }
        return false
    }
}

JavaScript 中的栈

栈是一种线性数据结构，它利用后进先出 (LIFO) 或先进后出 (FILO) 原则。栈中的插入和删除都在一端进行。根据 FILO 原则，第一个插入栈的元素最后被移除。根据 LIFO 原则，最后一个放入栈的元素最先被取出。

栈中执行着许多操作，例如 push、pop、peek、isFull 和 isEmpty。

代码

class Stack {

    constructor()
    {
        this.items = [];
    }

  push(element)
{
    this.items.push(element);
}

    
pop()
{
    if (this.items.length == 0)
        return "Welcome";
    return this.items.pop();
}

 peek()
{
    return this.items[this.items.length - 1];
}


  isEmpty()
{
    return this.items.length == 0;
}

    
 printStack()
{
    var str = "";
    for (var i = 0; i < this.items.length; i++)
        str += this.items[i] + " ";
    return str;
}

}
var stack = new Stack();

console.log(stack.isEmpty());

console.log(stack.pop());
stack.push(50);
stack.push(60);
stack.push(20);

console.log(stack.printStack());
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.printStack());

输出

我们可以在 JavaScript 中看到栈的实现。

JavaScript 中的队列

队列是一种线性数据结构，它遵循先进先出 (FIFO) 规则，这意味着队列中的第一个元素将是第一个出来的，就像排队买火车票的人会第一个拿到票一样。

栈中执行着各种操作，例如 push、pop、peek、isFull 和 isEmpty。

代码

class Queue {
        constructor() {
            this.items = {}
            this.frontIndex = 0
            this.backIndex = 0
        }
        enqueue(item) {
            this.items[this.backIndex] = item
            this.backIndex++
            return item + ' added'
        }
        dequeue() {
            const item = this.items[this.frontIndex]
            delete this.items[this.frontIndex]
            this.frontIndex++
            return item
        }
        peek() {
            return this.items[this.frontIndex]
        }
        get printQueue() {
            return this.items;
        }
isEmpty() {
    return this.items.length == 0;
}

    }
    const queue = new Queue()
    console.log(queue.enqueue(42))
    console.log(queue.enqueue(60))
    console.log(queue.enqueue(9))
    console.log(queue.dequeue())
    console.log(queue.enqueue(72))
    console.log(queue.peek())
    var sq = queue.printQueue;
    console.log(sq);

输出

我们可以在 JavaScript 中看到栈的实现。

JavaScript 中的 Set

Set 用于存储互不相同的项目集合。Set 包含唯一且不重复的项目。

语法

在上述语法中，参数 "it" 是一个可迭代对象，其中包含元素，并且其所有元素都添加到新创建的集合中。如果参数不包含任何元素，则也会创建一个空的新的集合。

Set 对象的实现

代码

var set1 = new Set(["kartik", "aryan", "sahil", "bhavna", "anjali"]);

var set2 = new Set("Brilliant");

var set3 = new Set([2, 4, 6, 8, 10, 12]);

var set4 = new Set();

set4.add(2);
set4.add(4);

set4.add(18).add(21).add(60);
console.log(set1);
console.log(set2);
console.log(set3);
console.log(set4);

输出

我们可以在 JavaScript 中看到 set 的使用。

JavaScript 中的图

图是一种非线性数据结构，包含节点和边。边也称为弧或线。节点也称为顶点。

代码

class Graph {
    constructor(verticesNumber)
    {
        this.verticesNumber = verticesNumber;
        this.AdjList = new Map();
    }

addVertex(v)
{
    this.AdjList.set(v, []);
}

addEdge(v, x)
{
    this.AdjList.get(v).push(x);

    this.AdjList.get(x).push(v);
}

printGraph()
{
    var getKeys = this.AdjList.keys();

    for (var k of getKeys)
{
        var getValues = this.AdjList.get(k);
        var conc = "";

        for (var l of getValues)
            conc += l + " ";

        console.log(k + " -> " + conc);
    }
}
}

 var gr = new Graph(6);
var vertices = [ 'H', 'I', 'J', 'K', 'L', 'M' ];

for (var i = 0; i < vertices.length; i++) {
    gr.addVertex(vertices[i]);
}

gr.addEdge('H', 'I');
gr.addEdge('H', 'K');
gr.addEdge('H', 'L');
gr.addEdge('I', 'J');
gr.addEdge('K', 'L');
gr.addEdge('L', 'M');
gr.addEdge('L', 'J');
gr.addEdge('J', 'M');

gr.printGraph();

输出

我们可以在 JavaScript 中看到图的利用。

JavaScript 中的算法

JavaScript 中有各种算法，我们将在下面讨论

排序算法

有时我们需要在 JavaScript 中对数字进行排序，为此我们有各种排序算法，例如归并排序、快速排序、选择排序、冒泡排序、插入排序和堆排序。

归并排序：它通过分治法对数组进行排序，这意味着它将一个大问题分解为小问题，然后单独解决这些小问题。之后，将小问题的结果合并以解决大问题。

快速排序：它通过分治算法对数组进行排序。它首先在数组中选择一个枢轴项，然后将其与数组中存在的其他项进行比较并对数组进行排序。

冒泡排序：它通过构建一个循环来对数组进行排序，该循环用于将每个项与其他项进行比较。如果比较的项比手中的项短，则我们交换它们的位置。这个过程会一遍又一遍地发生，直到整个数组排序完成。

选择排序：它通过将第一项视为最小项来对数组进行排序，然后将该项与其他项进行比较。如果其他项更小，则将其设置为新的最小项。这个循环将一直进行，直到整个数组排序完成。

插入排序：它通过将第一项视为已排序的项来对数组进行排序，然后选取下一项将其与已排序的项进行比较。如果该项更小，则将其插入到正确的位置。这个过程会一遍又一遍地发生，直到整个数组排序完成。

堆排序：堆是一种基于树的数据结构。堆排序通过利用堆数据结构对数组进行排序。

搜索算法

在 JavaScript 中，搜索算法用于获取存储在数据结构中的信息。我们有多种方式可以在数组中搜索数据

线性搜索

它用于在数组中搜索元素。它遍历数组中存在的每个元素，当找到目标元素时，它返回该元素的索引。

二分搜索

它用于在已排序的数组中搜索值。它遵循分治算法，因此它将数组分成两部分并检查目标。

动态规划

这是一种强大的方法，用于解决复杂问题。它将复杂问题分解为简单的子问题。它解决了子问题，然后结合结果来解决复杂问题。

贪心算法

此算法用于解决复杂问题。它允许在每个步骤中做出局部最优选择来解决问题。首先，此算法将检查所有选项，然后选择最佳选项，然后重复此过程，直到达到结果。

贪心算法的实现

代码

function coin_change(coins, amount) {
  coins.sort((c, d) => d - c);
  let count = 0;
  for (let k = 0; k < coins.length; k++) {
    while (amount >= coins[k]) {
      amount -= coins[k];
      count++;
    }
  }
  return count;
}

console.log(coin_change([2, 6, 12], 10));

输出

JavaScript 中 DSA 的优势

JavaScript 编程语言用于前端和后端开发。
JavaScript 的动态特性和富有表现力的语法使其易于对不同的算法和数据结构进行原型设计和实验。
由于 JavaScript 是最流行的编程语言之一，因此有大量资源、库和社区可用于学习和实现 DSA 概念。

结论

在本文中，我们学习了 JavaScript 中的 DSA。我们理解了数组、链表、哈希表、树、二叉树、栈、队列、集合、图、搜索算法和贪心算法等算法，以及 JavaScript 中 DSA 的优势。

下一主题Javascript-null-coalescing

JavaScript 中的 DSA

什么是数据结构？

JavaScript 中的数组

语法

多维数组的语法

JavaScript 中数组的示例

JavaScript 中多维数组的示例

JavaScript 中的链表

创建 Node 类

创建 LinkedList 类

打印 LinkedList 类

在链表中添加新元素的演示

从链表中删除元素的演示

JavaScript 中的哈希表

使用 Object 数据类型

使用 Map 对象

树

二叉树

JavaScript 中的栈

JavaScript 中的队列

JavaScript 中的 Set

JavaScript 中的图

JavaScript 中的算法

排序算法

搜索算法

贪心算法

JavaScript 中 DSA 的优势

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

JavaScript 基础

JS 变量和数据类型

JS 控制语句

JavaScript 函数

JavaScript 对象

JS 高级函数

JS Promises & Async/Await

JavaScript DOM

JavaScript JSON 对象

JavaScript 验证

JavaScript Cookies

异常处理

JavaScript 集合

JavaScript 事件

JavaScript OOPs

JavaScript BOM

面试题

选择题

差异

JavaScript Map 方法

JavaScript Handler

JavaScript Number 方法

JavaScript Reflect

JavaScript Symbol

Symbol 属性

JavaScript Math 方法

JavaScript Date 方法

JavaScript DataView

JavaScript Object 方法

JavaScript Set 方法

JavaScript 字符串方法

JavaScript TypedArray 方法

JavaScript WeakMap 方法

JavaScript WeakSet 方法

JavaScript 数组方法

JavaScript RegExp 对象

JavaScript 附加内容

JavaScript 杂项

JavaScript 进阶

问题

Lodash

JavaScript 中的 DSA

什么是数据结构？

JavaScript 中的数组

语法

多维数组的语法

JavaScript 中数组的示例

JavaScript 中多维数组的示例

JavaScript 中的链表

创建 Node 类

创建 LinkedList 类

打印 LinkedList 类

在链表中添加新元素的演示

从链表中删除元素的演示

JavaScript 中的哈希表

使用 Object 数据类型

使用 Map 对象

树

二叉树

JavaScript 中的栈