JavaScript - 数据结构 - 《Web前端学习总结》

1、双向链表
2、树

1、双向链表

双向链表 (doulby linked list) 是一个线性数据结构，表示一组元素，每个元素都指向下一个和上一个元素。双向链表中的第一个元素是头 (head)，最后一个元素是尾 (tail)。

双向链表数据结构的每个元素都必须具有以下属性:
- value: 元素的值
- next: 指向链表中下一个元素的指针(如果没有，则为 null)
- previous: 指向链表中前一个元素的指针(如果没有，则为 null)
双向链表数据结构的主要属性是:
- size: 双向链表中元素的数量
- head: 双向链表的第一个元素
- tail: 双向链表的最后一个元素
双向链表数据结构的主要操作是:
- insertAt: 在特定索引处插入一个元素
- removeAt: 删除特定索引处的元素
- getAt: 检索特定索引处的元素
- clear: 清空双向链表
- reverse: 颠倒双向链表中元素的顺序 ```javascript class DoublyLinkedList { constructor() { this.nodes = []; }
get size() { return this.nodes.length; }

get head() { return this.size ? this.nodes[0] : null; }

get tail() { return this.size ? this.nodes[this.size - 1] : null; }

insertAt(index, value) { const previousNode = this.nodes[index - 1] || null; const nextNode = this.nodes[index] || null; const node = { value, next: nextNode, previous: previousNode };

if (previousNode) previousNode.next = node; if (nextNode) nextNode.previous = node; this.nodes.splice(index, 0, node); }

insertFirst(value) { this.insertAt(0, value); }

insertLast(value) { this.insertAt(this.size, value); }

getAt(index) { return this.nodes[index]; }

removeAt(index) { const previousNode = this.nodes[index - 1] || null; const nextNode = this.nodes[index + 1] || null;

if (previousNode) previousNode.next = nextNode; if (nextNode) nextNode.previous = previousNode;

return this.nodes.splice(index, 1); }

clear() { this.nodes = []; }

reverse() { this.nodes = this.nodes.reduce((acc, { value }) => {
```
const nextNode = acc[0] || null;
const node = { value, next: nextNode, previous: null };
if (nextNode) nextNode.previous = node;
return [node, ...acc];
```
}, []); }

Symbol.iterator { yield this.nodes; } } ```

2、树
树是一种数据结构，由一组表示分层树结构的链接节点组成。每个节点通过父子关系链接到其他节点。树中的第一个节点是根，而没有子节点的节点是叶子。
树数据结构中的每个节点必须具有以下属性:
- key: 节点的key值
- value: 节点的value值
- parent: 节点的父节点(如果没有，则为 null)
- children: 指向节点子节点的指针数组
树型数据结构的主要操作是:
- insert: 将节点作为给定父节点的子节点插入
- remove: 从树中移除节点及其子节点
- find: 检索给定的节点
- preOrderTraversal: 前序遍历，通过递归遍历树中的每个节点及其子节点来遍历树
- postOrderTraversal: 后序遍历，通过递归遍历每个节点的子节点后面跟着节点来遍历树 ```javascript class TreeNode { constructor(key, value = key, parent = null) { this.key = key; this.value = value; this.parent = parent; this.children = []; }
get isLeaf() { return this.children.length === 0; }

get hasChildren() { return !this.isLeaf; } }

class Tree { constructor(key, value = key) { this.root = new TreeNode(key, value); }

preOrderTraversal(node = this.root) { yield node; if (node.children.length) { for (let child of node.children) { yield this.preOrderTraversal(child); } } }

postOrderTraversal(node = this.root) { if (node.children.length) { for (let child of node.children) { yield this.postOrderTraversal(child); } } yield node; }

insert(parentNodeKey, key, value = key) { for (let node of this.preOrderTraversal()) { if (node.key === parentNodeKey) { node.children.push(new TreeNode(key, value, node)); return true; } } return false; }

remove(key) { for (let node of this.preOrderTraversal()) { const filtered = node.children.filter(c => c.key !== key); if (filtered.length !== node.children.length) { node.children = filtered; return true; } } return false; }

find(key) { for (let node of this.preOrderTraversal()) { if (node.key === key) return node; } return undefined; } } ```

数据结构

1、双向链表

2、树