使用js实现常见的数据结构---链表，队列，栈，树_业界新闻

发布时间:2024-07-20 07:13

阅读量:0

注：本文只作为数据结构的实现参考和个人理解

链表

链表是由多个节点（node）连接起来的，每个节点包含了一些存储的数据和指向下一个节点的指针，

链表：多个连续的节点构成，
节点：包含一串数据，以及下一个节点的数据
注意：链表是由顺序的数据集结构，访问链表只能从头到尾的访问

// 定义一个节点 class Node {   constructor(data) {     this.data = data;     this.next = null;   } }  // 定义一个链表 class LinkedList {   constructor() {     this.first = null;//初始化头节点   }   // 添加节点   addNode(data) {     const node = new Node(data);     if (this.first === null) {       this.first = node;     } else {       let current = this.first;       while (current.next) {//后续节点存在         current = current.next;//移动到下一个节点       }       current.next = node;     }   }   // 删除节点   removeNode(data) {     if (this.first === null) {       return;     }     if (this.first.data === data) {       this.first = this.first.next;       return;     }     let current = this.first;     while (current.next) {       if (current.next.data === data) {         current.next = current.next.next;         return;       }       current = current.next;     }   }   // 遍历链表   getList() {     let current = this.first;     let arr = []     while (current) {       arr.push(current.data);       current = current.next;     }     return arr.reduce((a, b) => a + '->' + b, '');   } }  const list = new LinkedList(); list.addNode(1); list.addNode(2); list.addNode(3); list.addNode(4); list.addNode(5); console.log(list.getList()); list.removeNode(3); console.log(list.getList()); console.log(list); console.log(list.first.next);

队列

先进先出的数据结构：每次只能从队列的尾部添加数据，从队列的头部访问数据，

一头放数据，一头拿数据，不可直接访问中间的数据

// 创建一个队列 class Queue {   #value   constructor(){     this.#value = []   }   get value(){     return this.#value[this.#value.length - 1];//返回最后一个元素   }   set value(val){     this.#value.splice(0, 0, val);//头部添加元素   }   delValue(){     this.#value.pop()//删除最后一个元素   }   getQueue(){     return this.#value.toReversed().reduce((a,b)=> a+'->'+b, '')   } }  // 先进先出 const queue = new Queue() queue.value = 1 queue.value = 2 queue.value = 3 queue.value = 4 queue.value = 5 queue.value = 6 queue.value = 7 console.log(queue.getQueue()) console.log(queue.value)  queue.delValue() queue.delValue() console.log(queue.value)

栈

后进先出的数据结构：只有一个出入口，数据的增减都在尾部

只能在链式数据的一端进行访问数据和修改数据

// 后进先出 class Stack {   #value   constructor() {     this.#value = []   }   get value() {     return this.#value[this.#value.length - 1]   }   set value(val) {     this.#value.push(val)   }  }  const stack = new Stack() stack.value = 1 stack.value = 2 stack.value = 3 console.log(stack.value)

树

树是一个二维结构，一颗树从根节点出发，连接着多个子节点，每个子节点又连接着子孙节点，循环往复就组成了一棵树；

注意：在树中子节点只能指向子孙节点不能指向父节点，根节点只有一个，他是所有节点的父节点，不能被任何节点指向

根节点：每个数的根节点只能有一个（最顶层的节点）
叶节点：没有子节点的节点（最底层的节点）

class TreeNode {   constructor(data) {     this.data = data;     this.children = null;   }   add(data) {// 向节点添加子节点     if (this.children === null) {// 如果无字节点添加节点之前，设置属性为空数组       this.children = [];     }     this.children.push(new TreeNode(data));   }   remove(data) {// 移除节点的子节点     if (this.children === null) {       return false;     }     for (let i = 0; i < this.children.length; i++) {       if (this.children[i].data === data) {         this.children.splice(i, 1);         return true;       }     }     return false;   }   // 层序遍历树   // 记录层数， 每层节点放入一个数组   log() {     const result = []; // 存放结果的容器     let level = 0; // 记录层数，默认为顶层     result[level] = [String(level), this.data]; // 将根节点放入第一层,string表示层级     level++;// 下一层      function loop(node, level) {       if (!node.children) {// 没有子节点退出递归         return;       }       if (!result[level]) {// 如果没有创建数组，则创建         result[level] = [String(level)];       }        node.children.map(item => {         result[level].push(item.data);// 将结果放置再本层         loop(item, level + 1);// 递归调用下一层        })      }     loop(this, level);     console.log(result);   } }  const tree = new TreeNode(1); tree.add(2); tree.add(3); tree.children[0].add(4); tree.children[0].add(5); tree.children[1].add(6); tree.children[1].add(7); tree.children[0].children[0].add(8); tree.log();  console.log(tree)