JavaScript 中的数据结构

2025年3月2日 | 9 分钟阅读

JavaScript 中的数据结构是什么？

在 JavaScript 中，数据结构是一种组织、管理和存储数据的格式，这种格式有助于我们访问和修改数据。简单来说，数据结构是数据值的集合以及它们之间的关系，以及可以应用于这些数据的函数或操作。

换句话说，我们可以说数据结构被定义为在我们的设备中存储和组织数据的特定方式，以便高效且有效地使用数据。

通过在 JavaScript 中使用数据结构，我们可以最小化时间复杂度和空间复杂度。高效的数据结构占用最小的内存空间，并且执行数据所需的时间最少。

如何开始学习 JavaScript 数据结构？

要使用 JavaScript 学习数据结构，我们需要按顺序遵循一些步骤。

让我们看看从零开始学习 JavaScript 数据结构的过程

了解时间和空间复杂度
学习单个数据结构的基础知识
练习数据结构问题

了解复杂度

第一步，我们使用数据结构的主要目的是有效地解决问题。如果你需要找出你的程序是否高效，那么你需要测量程序的复杂度。

DS 中有两种复杂度

时间复杂度

它用于测量执行代码所需的时间量。

空间复杂度

它意味着成功执行代码功能所需的空间量。有时，你会在 DSA 中非常常见地遇到“辅助空间”一词，它指的是程序中除了输入数据结构之外使用的额外空间。

上述两种复杂度都是相对于输入参数测量的。但这里出现了一个问题。执行代码所需的时间取决于几个因素，例如：

程序中执行的操作数量。
设备的速度以及
在在线平台上执行的数据传输速度。

学习数据结构

数据结构由两部分组成，例如：

数据结构
算法

JavaScript 中有各种各样的数据结构，允许开发人员执行一系列不同的功能，这些功能有助于数据分析和可视化，或者帮助我们创建 AI 和 ML 算法。

Array

在 JavaScript 中，数组是存储在连续内存位置的相似类型变量或项目的集合。它是最流行和最简单的数据结构之一，并且经常用于实现其他数据结构。数组中每个项目的索引从 0 开始。

数组的声明： 声明数组基本上有两种方式。

语法

 
let arrayName = [value1, value2, ... ]; or
let arrayName = new Array();   

数组操作的类型

遍历： 在 JavaScript 数组中，我们遍历元素。
插入： 我们在数组中插入一个新元素。
删除： 从 JavaScript 数组中删除元素。
搜索： 在数组中搜索一个元素。
排序： 在此，我们维护数组中元素的顺序。

示例

 
// Initializing while declaring
    // Creates an array having elements 5, 10, 15, 20, 25
    var house = new Array(5, 10, 15, 20, 25);
    
    // Creates an array of 5 undefined elements
    var house1 = new Array(5);
    
    // Creates an array with element 2BHK
    var home = new Array("2BHK");
    console.log(house)
    console.log(house1)
    console.log(home)   

输出

 
[ 5, 10, 15, 20, 25 ]
[ <5 empty items> ]
[ '2BHK' ]

Stack

在 JavaScript 中，堆栈是一种线性数据结构，它包含一个元素列表。堆栈遵循 LIFO（后进先出）原则。这意味着最近添加到堆栈的元素将首先被移除。

堆栈顶部发生两个主要操作：push 和 pop。使用 push 方法，我们可以向数组末尾添加一个或多个元素。使用 pop 方法，我们可以移除数组末尾的顶层元素，然后将其返回给调用者。

堆栈在 JavaScript 中不是原生可用的，但可以使用相对简单的数组添加

 
const stack = [];
//add item to the top
stack.push("value");
//remove the item from the top
const topItem = stack.pop();   

当我们需要跟踪用户交互时，我们可以在现实世界中使用堆栈。它可用于构建诸如撤消按钮之类的功能。

堆栈中的操作

Push： 我们可以将元素添加到堆栈顶部。
Pop： 此操作用于从堆栈顶部移除元素。
IsEmpty： 此操作用于检查堆栈是否为空。
IsFull： 此操作用于检查堆栈是否已满。
Top/Peek： 我们获取顶部元素的值而不将其移除。

示例

 
function Stack() {
    this.count= 0;
    this.storage = {};
    this.push = function (value){
        this.storage[this.count] = value;
        this.count++;
    }
    this.pop = function () {
        if (this.count === 0) {
          return undefined;
        }
        this.count--;
        var result = this.storage[this.count];
        delete this.storage[this.count];
        return result;
      }
    
      this.peek = function () {
        return this.storage[this.count - 1];
      }
    
      this.size = function () {
        return this.count;
      }
}   

Queue

在 JavaScript 中，队列在某些方面与堆栈相似，但有一个关键区别。在这种情况下，队列不是移除最后添加的元素，而是移除最先添加到队列的元素。队列遵循先进先出（FIFO）原则。

队列操作

在 JavaScript 中，队列是一个对象，可以帮助我们执行一些操作，例如

Enqueue： 它将元素添加到队列的末尾。
Dequeue： 它是一个从队列前端移除元素的操作。
IsEmpty： 它用于检查队列是否为空。
IsFull： 它用于检查队列是否已满。
Top/Peek： 我们将获取队列前端的值而不将其移除。

示例

 
class Queue {
    constructor() {
        this.items = {}
        this.frontIndex = 0
        this.backIndex = 0
    }
    enqueue(item) {
        this.items[this.backIndex] = item
        this.backIndex++
        return item + ' inserted'
    }
    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 function
isEmpty() {
//it will return true if the queue is empty.
return this.items.length == 0;
}

}
const queue = new Queue()
console.log(queue.enqueue(7 ))
console.log(queue.enqueue(2 ))
console.log(queue.enqueue(6 ))
console.log(queue.enqueue(4 ))
console.log(queue.dequeue())
console.log(queue.peek())
var str = queue.printQueue;
console.log(str)	   

输出

 
7 inserted
2 inserted
6 inserted
4 inserted
7
2
{ '1': 2, '2': 6, '3': 4 }

链表

在 JavaScript 中，链表是一种线性数据结构，它们不像数组那样存储在连续位置。基本上，它是一个节点链，每个节点都包含数据和指向链中下一个节点的指针等信息。

在链表中，有一个头指针指向链表的第一个元素，如果列表为空，则它简单地指向 null 或什么都没有。

链表操作

遍历： 在 JavaScript 中，我们可以从头节点开始遍历整个链表。现在，假设有 n 个节点，那么遍历的时间复杂度变为 O(n)，因为我们遍历了每个节点。
插入： 在 JavaScript 中，将一个键插入链表。插入可以通过 3 种不同的方式完成：在列表开头插入、在列表末尾插入和在列表中间插入。
删除： 在 JavaScript 中，它从给定链表中删除元素 x。我们不能一步删除一个节点。删除可以通过 3 种不同的方式完成：我们可以从列表的开头删除，我们可以从列表的末尾删除，我们可以从列表的中间删除。
搜索： 我们可以通过简单的线性搜索在给定链表中找到第一个键为 k 的元素并返回指向此元素的指针。

示例

 
// Node class
class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
    }
  }
  
  // LinkedList class
  class LinkedList {
    constructor() {
      this.head = null;
    }
  
    // Add a new node to the end of the list
    append(data) {
      const newNode = new Node(data);
      if (!this.head) {
        this.head = newNode;
      } else {
        let current = this.head;
        while (current.next) {
          current = current.next;
        }
        current.next = newNode;
      }
    }
  
    // Print the linked list
    printList() {
      let current = this.head;
      while (current) {
        console.log(current.data);
        current = current.next;
      }
    }
  }
  
  // Create a new linked list
  const myList = new LinkedList();
  
  // Add some nodes to the list
  myList.append(1);
  myList.append(2);
  myList.append(3);
  myList.append(4);
  myList.append(5);
  
  // Print the linked list
  myList.printList();   

输出

Tree

在 JavaScript 中，树数据结构是非线性的，它具有分层数据结构，由节点集合组成，树的每个节点都存储一个值和指向其他节点引用的列表。

换句话说，树是 JavaScript 中一种嵌套数据结构。它具有分层结构，其中包含一个称为父节点的单个节点。此父节点有子节点，它们是嵌套在原始根节点中的元素。这些子节点中的每一个都可能在其内部进一步嵌套子节点。

树的类型

DS 中有几种不同类型的树，例如

二叉树
二叉搜索树
AVL 树
B 树
红黑树

树数据结构的操作

插入： 我们可以将元素插入树中，或者我们可以创建一棵树。
搜索： 我们还可以在树中搜索元素。
树遍历： 树遍历算法用于访问树中的特定节点以对其执行特定操作。

示例

 
class Node {
    constructor(value) {
      this.value = value;
      this.children = [];
    }
  
    addChild(node) {
      this.children.push(node);
    }
   }
  
  class Tree {
    constructor(root) {
      this.root = new Node(root);
    }
  
    traverse(node = this.root) {
      console.log(node.value);
      node.children.forEach(child => this.traverse(child));
    }
  }
  
  // Example usage:
  let tree = new Tree("A");
  let treeNodeB = new Node("B");
  let treeNodeC = new Node("C");
  let treeNodeD = new Node("D");
  let treeNodeE = new Node("E");
  let treeNodeF = new Node("F");
  
  tree.root.addChild(treeNodeB);
  tree.root.addChild(treeNodeC);
  treeNodeB.addChild(treeNodeD);
  treeNodeB.addChild(treeNodeE);
  treeNodeC.addChild(treeNodeF);
  
  tree.traverse();   

优先队列

在 JavaScript 中，优先队列的操作与标准队列相似，但能够为每个元素分配优先级。它允许元素按其优先级排序。

简单来说，优先队列是一种队列类型，它帮助我们根据元素的优先级值排列元素。优先级值较高的元素通常会在优先级值较低的元素之前被检索。

我们需要将优先队列的元素存储在堆结构中。当我们使用优先队列时，优先级最高的元素始终是根元素。

示例

 
class PriorityQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(priority, item) {
    this.queue.push({ priority, item });
    this.queue.sort((a, b) => b.priority - a.priority);
  }

  dequeue() {
    return this.queue.shift().item;
  }

  peek() {
    return this.queue[0].item;
  }

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

// Example usage:
const pq = new PriorityQueue();

pq.enqueue(3, "low priority task");
pq.enqueue(1, "high priority task");
pq.enqueue(2, "medium priority task");

console.log(pq.dequeue()); // "high priority task"
console.log(pq.dequeue()); // "medium priority task"
console.log(pq.dequeue()); // "low priority task"   

输出

 
low priority task
medium priority task
high priority task

Map

在 JavaScript 中，Map 是一个元素集合，其中每个元素都以键值对的形式存储。Map 具有一些对象，这些对象用于将对象和原始值作为键或值。

在 JavaScript 中，当我们遍历 Map 对象时，它会按插入的相同顺序返回键值对。

语法

参数

它：它是任何可迭代对象，其值存储为键或值对；如果未指定参数，则创建的新 Map 为空。

返回： 一个新的 Map 对象

示例

 
// Original array
const numbers = [1, 2, 3, 4, 5];

// Using map() to create a new array with squares
const squares = numbers.map(function(num) {
  return num * num;
});

console.log(squares); // Output: [1, 4, 9, 16, 25]   

输出

 
[ 1, 4, 9, 16, 25 ]

下一主题JavaScript 迭代器

← 上一个下一个 →

JavaScript 中的数据结构