JavaScript算法与数据结构：实用指南

JavaScript中的算法与数据结构：实践指南

在现代Web开发中，掌握算法与数据结构不仅是学术技能，更是构建快速、可扩展应用程序的工具。JavaScript，特别是在Node.js环境中，能够实现从简单到复杂的各种算法结构。本文将结合实际代码示例，深入讲解关键的数据结构与算法，这些代码可直接用于项目中。

1. 基础数据结构：栈、队列和链表

我们从基础开始。栈和队列是线性结构，常用于解析、任务队列和操作历史管理。

栈（LIFO）

栈遵循"后进先出"原则。我们基于数组实现：

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

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

  pop() {    return this.items.pop();  }

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

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

// 使用示例const stack = new Stack();stack.push('Page 1');stack.push('Page 2');console.log(stack.pop()); // 'Page 2'

队列（FIFO）

队列适用于按顺序处理任务。使用类实现：

class Queue {  constructor() {    this.items = {};    this.front = 0;    this.rear = 0;  }

  enqueue(element) {    this.items[this.rear] = element;    this.rear++;  }

  dequeue() {    const item = this.items[this.front];    delete this.items[this.front];    this.front++;    return item;  }

  peek() {    return this.items[this.front];  }

  size() {    return this.rear - this.front;  }}

// 示例const queue = new Queue();queue.enqueue('Task 1');queue.enqueue('Task 2');console.log(queue.dequeue()); // 'Task 1'

链表

链表在列表中间插入和删除元素时效率很高。实现单向链表：

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

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

  append(value) {    const newNode = new Node(value);    if (!this.head) {      this.head = newNode;      this.tail = newNode;    } else {      this.tail.next = newNode;      this.tail = newNode;    }    this.length++;  }

  prepend(value) {    const newNode = new Node(value);    newNode.next = this.head;    this.head = newNode;    if (!this.tail) {      this.tail = newNode;    }    this.length++;  }

  print() {    const arr = [];    let current = this.head;    while (current) {      arr.push(current.value);      current = current.next;    }    return arr;  }}

// 示例const list = new LinkedList();list.append(10);list.append(20);list.prepend(5);console.log(list.print()); // [5, 10, 20]

2. 搜索算法：线性搜索与二分搜索

搜索是最常见的操作之一。我们来看两种方法：简单的线性搜索和高效的二分搜索。

线性搜索

适用于未排序数据。时间复杂度O(n)：

function linearSearch(arr, target) {  for (let i = 0; i < arr.length; i++) {    if (arr[i] === target) {      return i; // 返回索引    }  }  return -1;}

console.log(linearSearch([3, 7, 1, 9, 4], 9)); // 3

二分搜索

要求数组已排序。时间复杂度O(log n)。在Node.js中实现：

function binarySearch(arr, target) {  let left = 0;  let right = arr.length - 1;

  while (left <= right) {    const mid = M