「中高级前端」数据结构的世界 ES6版 - so-much-to-learn/weekly-blog GitHub Wiki

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

    push(...items) {
        return this.reverse
            ? this.stack.unshift(...items)
            : this.stack.push(...items);
    }
    
    pop() {
        return this.reverse ? this.stack.shift() : this.stack.pop();
    }
}

const stack = new Stack(4, 5);
stack.reverse = true;
console.log(stack.push(1, 2, 3) === 5) // true
console.log(stack.stack ===[1, 2, 3, 4, 5]) // true

class Queue {
    constructor(...items) {
        this.reverse = false;
        this.queue = [...items];
    }

    enqueue(...items) {
        return this.reverse
            ? this.queue.push(...items)
            : this.queue.unshift(...items);
    }

    dequeue() {
        return this.reverse ? this.queue.shift() : this.queue.pop();
    }
}

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

class LinkedList {
  constructor() {
    this.head = null
    this.tail = null
    // 长度非必要
    this.length = 0
  }
  push(data) {
    // 创建一个新节点
    const node = new Node(data)
    // 检查头部是否为空
    if (this.head === null) {
      this.head = node
      this.tail = node
    } 
    this.tail.next = node
    this.tail = node
    this.length++
  }
  pop(){
    // 先检查链表是否为空
    if(this.isEmpty()) {
      return null
    } 
    // 如果长度为1
    if (this.head === this.tail) {
      this.head = null
      this.tail = null
      this.length--
      return this.tail
    }
    let node = this.tail
    let currentNode = this.head
    let penultimate
    
    while (currentNode) {
      if (currentNode.next === this.tail) {
        penultimate = currentNode
        break
      }
      currentNode = currentNode.next
    }
    
    penultimate.next = null
    this.tail = penultimate
    this.length --
    return node
  }
  
  get(index){
    // 处理边界条件
    if (index === 0) {
      return this.head
    }
    if (index < 0 || index > this.length) {
      return null
    }
    
    let currentNode = this.head
    let i = 0
    while(i < index) {
      i++
      currentNode = currentNode.next
    }
    return currentNode
    
  }
  delete(index){
    let currentNode = this.head
    
    if (index === 0) {
      let deletedNode
      currentNode.next = this.head
      deletedNode = currentNode
      this.length--
      
      return deletedNode
    }
    
    if (index < 0 || index > this.length) {
      return null
    }
    
    let i = 0
    let previous
    
    while(i < index) {
      i++
      previous = currentNode
      currentNode = currentNode.next
    }
    previous.next = currentNode.next
    this.length--
    return currentNode
  }
  
  isEmpty() {
    return this.length === 0
  }
  print() {
    const list = []
    let currentNode = this.head
    while(currentNode){
      list.push(currentNode.data)
      currentNode = currentNode.next
    }
    return list.join(' => ')
  }
}

const l = new LinkedList()

// 添加节点
const values = ['A', 'B', 'C']
values.forEach(value => l.push(value))

console.log(l)
console.log(l.pop())
console.log(l.get(1))
console.log(l.isEmpty())
console.log(l.print())

class Node {
    constructor(data) {
        // data 包含链表项应存储的值
        this.data = data;
        // next 是指向列表中下一项的指针
        this.next = null;
        // prev 是指向列表中上一项的指针
        this.prev = null;
    }
}

class DoublyLinkedList {
    constructor() {
    	this.head = null;
        this.tail = null;
    }
    // 各种操作方法
    // ...
}

append( item ) {
  let node = new Node( item );
  if(!this.head) {
    this.head = node;
    this.tail = node;
  } else {
    node.prev = this.tail;
    this.tail.next = node;
    this.tail = node
  }
}

appendAt( pos, item ) {
   let current = this.head;
   let counter = 1;
   let node = new Node( item );
   if( pos == 0 ) {
     this.head.prev = node
     node.next = this.head
     this.head = node
   } else {
     while(current) {
      current = current.next;
      if( counter == pos ) {
        node.prev = current.prev
        current.prev.next = node
        node.next = current
        current.prev = node
      }
      counter++
    }
  }
}

remove( item ) {
  let current = this.head;
  while( current ) {
    if( current.data === item ) {
      if( current == this.head && current == this.tail ) {
        this.head = null;
        this.tail = null;
      } else if ( current == this.head ) {
        this.head = this.head.next
        this.head.prev = null
      } else if ( current == this.tail ) {
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        current.prev.next = current.next;
        current.next.prev = current.prev;
      }
   }
   current = current.next
  }
}

removeAt( pos ) {
  let current = this.head;
  let counter = 1;
  if( pos == 0 ) {
   this.head = this.head.next;
   this.head.prev = null;
  } else {
   while( current ) {
    current = current.next
    if ( current == this.tail ) {
     this.tail = this.tail.prev;
     this.tail.next = null;
    } else if( counter == pos ) {
     current.prev.next = current.next;
     current.next.prev = current.prev;
     break;
    }
    counter++;
   }
  }
}

reverse(){
  let current = this.head;
  let prev = null;
  while( current ){
   let next = current.next
   current.next = prev
   current.prev = next
   prev = current
   current = next
  }
  this.tail = this.head
  this.head = prev
}

swap( nodeOne, nodeTwo ) {
   let current = this.head;
   let counter = 0;
   let firstNode;
   while( current !== null ) {
     if( counter == nodeOne ){
       firstNode = current;
     } else if( counter == nodeTwo ) {
       let temp = current.data;
       current.data = firstNode.data;
       firstNode.data = temp;
     }
     current = current.next;
     counter++;
   }
   return true
}

length() {
  let current = this.head;
  let counter = 0;
  while( current !== null ) {
   counter++
   current = current.next
  }
  return counter;
}
isEmpty() {
  return this.length() < 1
}

traverse( fn ) {
   let current = this.head;
   while( current !== null ) {
    fn(current)
    current = current.next;
   }
   return true;
}

search( item ) {
  let current = this.head;
  let counter = 0;
  while( current ) {
    if( current.data == item ) {
     return counter
    }
    current = current.next
    counter++
  }
  return false;
}

class Node { 
  constructor(data) { 
    this.left = null
    this.right = null
    this.value = value
  } 
} 

class BST {
    constructor() {
        this.root = null
    }
    // 二叉树的各种操作
    // insert(value) {...}
    // insertNode(root, newNode) {...}
    // ...

  insertNode(root, newNode) {
    if (newNode.value < root.value) {
      // 先执行无左节点操作
      (!root.left) ? root.left = newNode : this.insertNode(root.left, newNode)
    } else {
      (!root.right) ? root.right = newNode : this.insertNode(root.right, newNode)
    }
  }
  
insert(value) {
    let newNode = new Node(value)
    // 如果没有根节点
    if (!this.root) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
}

  removeNode(root, value) {
    if (!root) {
      return null
    }
    
    // 从该值小于根节点开始判断
    if (value < root.value) {
      root.left = this.removeNode(root.left, value)
      return root
    } else if (value > root.value) {
      root.right = tis.removeNode(root.right, value)
      return root
    } else {
      // 如果没有左右节点
      if (!root.left && !root.right) {
        root = null
        return root
      }
      
      // 存在左节点
      if (root.left) {
        root = root.left
        return root
      // 存在右节点
      } else if (root.right) {
        root = root.right
        return root
      }
      
      // 获取正确子节点的最小值以确保我们有有效的替换
      let minRight = this.findMinNode(root.right)
      root.value = minRight.value
      // 确保删除已替换的节点
      root.right = this.removeNode(root.right, minRight.value)
      return root
    }
  }
  
remove(value) {
    if (!this.root) {
      return 'Tree is empty!'
    } else {
      this.removeNode(this.root, value)
    }
}
  

findMinNode(root) {
    if (!root.left) {
      return root
    } else {
      return this.findMinNode(root.left)
    }
}

searchNode(root, value) {
    if (!root) {
      return null
    }
    
    if (value < root.value) {
      return this.searchNode(root.left, value)
    } else if (value > root.value) {
      return this.searchNode(root.right, value)
    }
    
    return root
}

search(value) {
    if (!this.root) {
      return 'Tree is empty'
    } else {
      return Boolean(this.searchNode(this.root, value))
    }
}

preOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      console.log(root.value)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  }

inOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      this.inOrder(root.left)
      console.log(root.value)
      this.inOrder(root.right)
    }
  }

postOrder(root) {
    if (!root) {
      return 'Tree is empty'
    } else {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.value)
    }
}

|V| = 6 
|E| = 7 

class Graph {
  constructor() {
    this.AdjList = new Map();
  }
  
  // 基础操作方法
  // addVertex(vertex) {}
  // addEdge(vertex, node) {}
  // print() {}
}

addVertex(vertex) {
  if (!this.AdjList.has(vertex)) {
    this.AdjList.set(vertex, []);
  } else {
    throw 'Already Exist!!!';
  }
}

let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');

Map {
  'A' => [],
  'B' => [],
  'C' => [],
  'D' => []
}

Map {
  'A' => ['B', 'C', 'D'],
  // B没有任何指向
  'B' => [],
  'C' => ['B'],
  'D' => ['C']
}

 addEdge(vertex, node) {
    // 向顶点添加边之前，必须验证该顶点是否存在。
    if (this.AdjList.has(vertex)) {
      // 确保添加的边尚不存在。
      if (this.AdjList.has(node)){
        let arr = this.AdjList.get(vertex);
        // 如果都通过，那么可以将边添加到顶点。
        if(!arr.includes(node)){
          arr.push(node);
        }
      }else {
        throw `Can't add non-existing vertex ->'${node}'`;
      }
    } else {
      throw `You should add '${vertex}' first`;
    }
}

print() {
  for (let [key, value] of this.AdjList) {
    console.log(key, value);
  }
}

let g = new Graph();
let arr = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < arr.length; i++) {
  g.addVertex(arr[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.print();
/* PRINTED */
// A [ 'B', 'D', 'E' ]
// B [ 'C' ]
// C [ 'F' ]
// D [ 'E' ]
// E [ 'F', 'C' ]
// F []

visited = {
  'A': true,
  'B': true,
  'D': true,
  'E': true
}
q = ['B', 'D', 'E']

createVisitedObject(){
  let arr = {};
  for(let key of this.AdjList.keys()){
    arr[key] = false;
  }
  return arr;
}

bfs(startingNode){
  let visited = this.createVisitedObject();
  let q = [];

  visited[startingNode] = true;
  q.push(startingNode);

  while(q.length){
    let current = q.pop()
    console.log(current);

    let arr = this.AdjList.get(current);

    for(let elem of arr){
      if(!visited[elem]){
        visited[elem] = true;
        q.unshift(elem)
      }
    }

  }
}

createVisitedObject(){
  let arr = {};
  for(let key of this.AdjList.keys()){
    arr[key] = false;
  }
  return arr;
}

 dfs(startingNode){
    console.log('\nDFS')
    let visited = this.createVisitedObject();
    this.dfsHelper(startingNode, visited);
  }

  dfsHelper(startingNode, visited){
    visited[startingNode] = true;
    console.log(startingNode);

    let arr = this.AdjList.get(startingNode);

    for(let elem of arr){
      if(!visited[elem]){
        this.dfsHelper(elem, visited);
      }
    }
  }

  doesPathExist(firstNode, secondNode){
    let path = [];
    let visited = this.createVisitedObject();
    let q = [];
    visited[firstNode] = true;
    q.push(firstNode);
    while(q.length){
      let node = q.pop();
      path.push(node);
      let elements = this.AdjList.get(node);
      if(elements.includes(secondNode)){
        console.log(path.join('->'))
        return true;
      }else{
        for(let elem of elements){
          if(!visited[elem]){
            visited[elem] = true;
            q.unshift(elem);
          }
        }
      }
    }
    return false;
  }
}

class PrefixTreeNode {
  constructor(value) {
    this.children = {};
    this.endWord = null;
    this.value = value;
  }
}
class PrefixTree extends PrefixTreeNode {
  constructor() {
    super(null);
  }
  // 基础操作方法
  // addWord(string) {}
  // predictWord(string) {}
  // logAllWords() {}
}

addWord(string) {
    const addWordHelper = (node, str) => {
        if (!node.children[str[0]]) {
            node.children[str[0]] = new PrefixTreeNode(str[0]);
            if (str.length === 1) {
                node.children[str[0]].endWord = 1;
            } else if (str.length > 1) {
                addWordHelper(node.children[str[0]], str.slice(1));
        }
    };
    addWordHelper(this, string);
}

predictWord(string) {
    let getRemainingTree = function(string, tree) {
      let node = tree;
      while (string) {
        node = node.children[string[0]];
        string = string.substr(1);
      }
      return node;
    };

    let allWords = [];
    
    let allWordsHelper = function(stringSoFar, tree) {
      for (let k in tree.children) {
        const child = tree.children[k]
        let newString = stringSoFar + child.value;
        if (child.endWord) {
          allWords.push(newString);
        }
        allWordsHelper(newString, child);
      }
    };

    let remainingTree = getRemainingTree(string, this);
    if (remainingTree) {
      allWordsHelper(string, remainingTree);
    }

    return allWords;
  }

  logAllWords() {
    console.log('------ 所有在字典树中的节点 -----------')
    console.log(this.predictWord(''));
  }

{[[['a'，9]，['b'，88]]，[['e'，7]，['q'，8]]，[['j'，7]，['l '，8]]]};

hash = hashfunc（key）
index = hash ％ array_size

{“abcdef”，“bcdefa”，“cdefab”，“defabc”}

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

class HashTableWithChaining {
	constructor( size = 10 ) {
		this.table = new Array( size );
	}
	
    // 操作方法
    // computeHash( string ) {...}
    // ...
}

isPrime( num ) {
	for(let i = 2, s = Math.sqrt(num); i <= s; i++)
        if(num % i === 0) return false; 
    return num !== 1;
}

computeHash( string ) {
	let H = this.findPrime( this.table.length );
	let total = 0;
	for (let i = 0; i < string.length; ++i) {
      	total += H * total + string.charCodeAt(i);
   	}
	return total % this.table.length;
}
// 取模
findPrime( num ) {
	while(true) {
		if( this.isPrime(num) ){ break; }
		num += 1
	}
	return num;
}

put( item ) {
	let key = this.computeHash( item );
	let node = new Node(item)
	if ( this.table[key] ) {
		node.next = this.table[key]
	}
	this.table[key] = node
}

remove( item ) {
	let key = this.computeHash( item );
	if( this.table[key] ) {
		if( this.table[key].data === item ) {
			this.table[key] = this.table[key].next
		} else {
			let current = this.table[key].next;
			let prev = this.table[key];
			while( current ) {
				if( current.data === item ) {
					prev.next = current.next
				}
				prev = current
				current = current.next;
			}
		}
	}
}

contains(item) {
    for (let i = 0; i < this.table.length; i++) {
        if (this.table[i]) {
            let current = this.table[i];
            while (current) {
                if (current.data === item) {
                    return true;
                }
                current = current.next;
            }
        }
    }
    return false;
}

size( item ) {
  let counter = 0
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i]
      while( current ) {
        counter++
        current = current.next
      }
    }
  }
  return counter
}
isEmpty() {
  return this.size() < 1
}

traverse( fn ) {
  for(let i=0; i<this.table.length; i++){
    if( this.table[i] ) {
      let current = this.table[i];
      while( current ) {
        fn( current );
        current = current.next;
      }
    }
  }
}