JavaScript数据结构

简介

JavaScript是一种广泛使用的脚本编程语言，也可以用于实现各种数据结构和算法。本文将介绍一些常见的数据结构和算法，并提供他们的JavaScript实现。

数据结构

数组（Array）

数组是一种线性数据结构，用于存储一系列相同类型的元素。在JavaScript中，数组是最常用的数据结构之一。

let array = []; // 创建一个空数组
array.push(1); // 在数组末尾添加元素1
array.push(2); // 在数组末尾添加元素2
array.push(3); // 在数组末尾添加元素3
console.log(array); // 输出 [1, 2, 3]

链表（Linked List）

链表是一种动态数据结构，由一系列节点组成。每个节点包含数据和指向下一个节点的指针。链表有多种类型，包括单链表、双链表和循环链表。

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

class LinkedList {
  constructor() {
    this.head = null;
  }
  
  add(data) {
    let newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
    } else {
      let currentNode = this.head;
      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = newNode;
    }
  }
}

栈（Stack）

栈是一种遵循"LIFO"（后进先出）原则的数据结构。在JavaScript中，可以使用数组或链表实现栈。

class Stack {
  constructor() {
    this.items = [];
  }
  
  push(element) {
    this.items.push(element);
  }
  
  pop() {
    if (this.items.length === 0) {
      return "Underflow";
    }
    return this.items.pop();
  }
}

队列（Queue）

队列是一种遵循"FIFO"（先进先出）原则的数据结构。在JavaScript中，可以使用数组或链表实现队列。

class Queue {
  constructor() {
    this.items = [];
  }
  
  enqueue(element) {
    this.items.push(element);
  }
  
  dequeue() {
    if (this.items.length === 0) {
      return "Underflow";
    }
    return this.items.shift();
  }
}

哈希表（Hash Table）

哈希表是一种使用哈希函数将键映射到值的数据结构。在JavaScript中，可以使用对象来实现哈希表。

class HashTable {
  constructor() {
    this.table = {};
  }
  
  put(key, value) {
    this.table[key] = value;
  }
  
  get(key) {
    return this.table[key];
  }
  
  remove(key) {
    delete this.table[key];
  }
}

算法

排序算法

冒泡排序（Bubble Sort）

冒泡排序通过相邻元素之间的比较和交换来排序元素。它重复遍历列表，直到没有需要交换的元素为止。

function bubbleSort(array) {
  let length = array.length;
  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - i - 1; j++) {
      if (array[j] > array[j + 1]) {
        let temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }
  return array;
}

快速排序（Quick Sort）

快速排序通过选择一个基准元素，并将列表分为两个子列表来排序元素。它递归地对子列表进行排序。

function quickSort(array) {
  if (array.length <= 1) {
    return array;
  }
  
  let pivot = array[0];
  let less = [];
  let greater = [];
  
  for (let i = 1; i < array.length; i++) {
    if (array[i] <= pivot) {
      less.push(array[i]);
    } else {
      greater.push(array[i]);
    }
  }
  
  return quickSort(less).concat(pivot, quickSort(greater));
}

查找算法

二分查找（Binary Search）

二分查找通过将列表分为两半来查找元素。它与中间元素进行比较，并根据比较结果决定继续查找左半边还是右半边。

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  
  while (left <= right) {
    let middle = Math.floor((left + right) / 2);
    
    if (array[middle] === target) {
      return middle;
    }
    
    if (array[middle] < target) {
      left = middle + 1;
    } else {
      right = middle - 1;
    }
  }
  
  return -1;
}

图算法

深度优先搜索（Depth First Search）

深度优先搜索是一种用于图遍历的算法。它从起始节点开始，递归地访问与当前节点相邻但未被访问过的节点。

function depthFirstSearch(graph, start) {
  let visited = {};
  let result = [];
  
  function dfs(node) {
    if (!node) {
      return;
    }
    
    visited[node] = true;
    result.push(node);
    
    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) {
        dfs(neighbor);
      }
    }
  }
  
  dfs(start);
  
  return result;
}

广度优先搜索（Breadth First Search）

广度优先搜索是一种用于图遍历的算法。它从起始节点开始，逐层遍历与当前层节点相邻但未被访问过的节点。

function breadthFirstSearch(graph, start) {
  let visited = {};
  let queue = [start];
  let result = [];
  
  visited[start] = true;
  
  while (queue.length > 0) {
    let node = queue.shift();
    result.push(node);
    
    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
  
  return result;
}

结论

JavaScript提供了丰富的数据结构和算法，可以用于解决各种问题。本文介绍了一些常见的数据结构和算法，并提供了他们的JavaScript实现。希望这些内容对您理解和应用JavaScript数据结构和算法有所帮助。

参考资料：

本文来自极简博客，作者：编程狂想曲，转载请注明原文链接：JavaScript数据结构

简介