データ構造javascript実装

コンピュータ配置CPU:AMD X 4 640メモリ:マクロDDR 3 1600 MHz 8 gマザーボード:華擎980 DE 3/U 3 S 3 R 2.0ブラウザ:chrome 79.0.3945.88(正式版)(64ビット)
じかんしけんかんすう

        function testRunTime(fn) {
            let start = new Date();
            let end = null;
            fn();
            end = new Date();
            console.log(`    : ${(end - start) / 1000} `);
        }

データ構造
1.配列2.チェーンテーブル3.キュー4.スタック5.最大ヒープ6.マッピング7.ツリー8を検索する.図9.ハッシュ表**
はいれつ

//   
class MyArray {
    constructor(capacity=10) {
        this._data = new Array(capacity);
        this._size = 0;
    }
    get length() {
        return this._size;
    }
    get capacity() {
        return this._data.length;
    }

    //       
    insert(index, e) { 
        if (index < 0 || index >= this._data.length) {
            throw new RangeError("index is invalid");
        }
        for (let i=this._size-1; i>=index; i--) {
            this._data[i+1] = this._data[i];
        }
        this._data[index] = e;
        this._size++;
    }
    //      
    insertLast(e) { 
        this.insert(this._size, e);
    }
    //      
    insertFirst(e) { 
        this.insert(0, e);
    }

    //      index   
    get(index) { 
        if (index < 0 || index >= this._data.length) {
            throw new RangeError("index is invalid");
        } 
        return this._data[index];
    }

    //      index   
    remove(index) { 
        if (index < 0 || index >= this._data.length) {
            throw new RangeError("index is invalid");
        } 
        let ret = this._data[index];
        for (let i=index,len=this._size-1; i<=len; i++) {
            this._data[i] = this._data[i+1];
        }
        this._size--;
        return ret;
    }

    //     
    set(index, e) { 
        if (index < 0 || index >= this._data.length) {
            throw new RangeError("index is invalid");
        } 
        if (this._data[index]) {
            this._data[index] = e;
        } else { //       
            this.insertLast(e);
        }
    }

    //       
    includes(e) {
        for (let i=0,len=this._size; i

チェーンテーブル
たんほうこうチェーンテーブル

//   
class LinkedListNode {
    constructor(e, next=null) {
        this.e = e;
        this.next = next;
    }
}
class LinkedList {
    constructor() {
        this._dummyhead = new LinkedListNode(null);
        this._tail = null; //    
        this._size = 0;
    }
    get length() {
        return this._size;
    }
    get isEmpty() {
        return this._size == 0;
    }

    //     
    insert(index, e) {
        if (index < 0 || index>this._size) {
            throw new RangeError("index is invalid");
        }
        let cur = this._dummyhead;
        for (let i=0; ithis._size) {
            throw new RangeError("index is invalid");
        }
        if (this.isEmpty) {
            return new Error("Element is empty");
        }
        let prev = this._dummyhead;
        let ret;
        for (let i=0; ithis._size) {
            throw new RangeError("index is invalid");
        }
        let cur = this._dummyhead.next;
        for (let i=0; i ";
            }
            cur = cur.next;
        }
        return res;
    }
}

export default LinkedList;

にほうこうチェーンテーブル

class LinkedListNode {
    constructor(item, next = null, prev = null) {
        this.item = item;
        this.next = next;
        this.prev = prev;
    }
}
//     
class LinkedList {
    constructor() {
        this._dummyhead = new LinkedListNode(null);
        this._tail = null; //    
        this._size = 0;
    }
    get size() {
        return this._size;
    }
    get isEmpty() {
        return this._size === 0;
    }
    //     
    insert(index, e) {
        if (index < 0 || index > this._size) {
            throw new RangeError("index is invalid");
        }
        let cur = this._dummyhead;
        for (let i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = new LinkedListNode(e, cur.next, cur);
        if (cur.next.next) {
            cur.next.next.prev = cur.next;
        }
        if (this._size === index) {
            this._tail = cur.next;
        }
        this._size++;
    }
    //     
    unshift(e) {
        this._dummyhead.next = new LinkedListNode(e, this._dummyhead.next);
        if (this._size == 0) {
            this._tail = this._dummyhead.next;
        }
        this._size++;
    }
    //     
    push(e) {
        if (this._size == 0) {
            this._dummyhead.next = new LinkedListNode(e, null, this._dummyhead);
            this._tail = this._dummyhead.next;
        } else {
            this._tail.next = new LinkedListNode(e, null, this._tail);
            this._tail = this._tail.next;
        }
        this._size++;
    }
    //     
    removeElement(e) {
        if (this.isEmpty) {
            return new Error("Element is empty");
        }
        let prev = this._dummyhead;
        while (prev != null) {
            if (prev.next !== null && Object.is(prev.next.item, e)) {
                break;
            }
            prev = prev.next;
        }
        if (prev != null) {
            let ret = prev.next;
            prev.next = ret.next;
            if (ret.next) {
                ret.next.prev = prev; //          
            }
            ret.next = null;
            if (Object.is(ret.item, this._tail.item)) {
                this._tail = prev;
            }
            this._size--;
            return ret;
        }
        return null;
    }
    //         
    removeIndex(index) {
        if (index < 0 || index > this._size) {
            throw new RangeError("index is invalid");
        }
        if (this.isEmpty) {
            return new Error("Element is empty");
        }
        let prev = this._dummyhead;
        let ret;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        ret = prev.next;
        prev.next = ret.next;
        if (ret.next) {
            ret.next.prev = prev; //          
        }
        ret.next = null;
        if (Object.is(ret.item, this._tail.item)) {
            this._tail = prev;
        }
        this._size--;
        return ret;
    }
    pop() {
        return this.removeIndex(this.size - 1);
    }
    shift() {
        return this.removeIndex(0);
    }
    //     
    find(e) {
        let cur = this._dummyhead.next;
        let index = 0;

        while (cur !== null) {
            if (Object.is(cur.item, e)) {
                break;
            }
            index++;
            cur = cur.next;
        }
        if (cur == null) {
            return -1;
        } else {
            return index;
        }
    }
    contains(e) {
        let result = this.find(e);
        return result != -1 ? true : false;
    }
    //     
    get(index) {
        if (index < 0 || index > this._size) {
            throw new RangeError("index is invalid");
        }
        let cur = this._dummyhead.next;
        for (let i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }
    toString() {
        let res = "";
        let cur = this._dummyhead.next;

        for (let i = 0, len = this._size; i < len; i++) {
            res += cur.item;
            if (i != len - 1) {
                res += " > ";
            }
            cur = cur.next;
        }
        return res;
    }
    iterator() { //    
        return {
            _item: this._dummyhead,
            next() {
                if (this.hasNext()) {
                    let ret = this._item.next;
                    this._item = this._item.next;
                    return ret;
                }
                return null;
            },
            hasNext() {
                return this._item.next !== null; 
            }
        }
    }
}

スタック

配列実装

class Stack {
    constructor() {
        this._data = [];
    }
    push(e) {
        this._data.push(e);
    }
    pop() {
        return this._data.pop();
    }
    peek() {
        return this._data[0];
    }
    isEmpty() {
        return this._data.length == 0;
    }
    get length() {
        return this._data.length;
    }
}
export default Stack;

チェーンテーブル実装

import LinkedList from "./LinkedList.js";
//      

class Stack {
   constructor() {
       this._data = new LinkedList();
   }
   push(e) {
       this._data.insertFirst(e);
   }
   pop() {
       return this._data.removeIndex(0);
   }
   peek() {
       return this._data.get(0);
   }
   get isEmpty() {
       return this._data.isEmpty;
   }
   get lenght() {
       return this._data.length;
   }
}

export default Stack;

キュー

配列実装

class Queue {
   constructor() {
       this._data = [];
   }
   enqueue(e) {
       this._data.push(e);
   }
   dequeue() {
       return this._data.shift();
   }
   front() {
       return this._data[0];
   }
   get isEmpty() {
       return this._data.length == 0;
   }
   get length() {
       return this._data.length;
   }
   toString() {
       return "Front ["+this._data.toString+"]";
   }
}

export default Queue;

チェーンテーブル実装

import LinkedList from "./LinkedList.js";

class Queue {
    constructor() {
        this._data = new LinkedList();
    }

    //   
    enqueue(e) {
        this._data.insertLast(e);
    }

    //   
    dequeue() {
        return this._data.removeIndex(0);
    }

    //     
    front() {
        return this._data.get(0);
    }
    get isEmpty() {
        return this._data.length == 0;
    }
    get length() {
        return this._data.length;
    }
    toString() {
        return "Front "+this._data.toString();
    }
}

export default Queue;

にぶんたんさくじゅ

import Queue from "./LinkedListQueue.js";

class Node {
    constructor(e=null) {
        this.e = e;
        this.left = null;
        this.right = null;
    }
}
class BST {
    constructor() {
        this._root = null;
        this._size = 0;
    }
    get size() {
        return this._size;
    }
    get isEmpty() {
        return this._size == 0;
    }

    //   
    insert(e) {
        let _this = this;

        if (this._root == null) {
            this._root = new Node(e);
            this._size++;
        } else {
            this._root = _insert(this._root);
        }

        function _insert(node) {
            if (node == null) {
                _this._size++;
                return new Node(e);
            }

            if (e < node.e) {
                node.left = _insert(node.left);
            } else if (e > node.e) {
                node.right = _insert(node.right);
            }
            return node;
        }
    }

    //    
    maximum() {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        return this._maximum(this._root);
    }
    _maximum(node) {
        if (node.right == null) {
            return node;
        }
        return this._maximum(node.right); 
    }

    //    
    minimum() {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        return this._minimum(this._root);
    }
    _minimum(node) {
        if (node.left == null) {
            return node;
        }
        return this._minimum(node.left);  
    }

    //      
    removeMin() {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        let minimum = this.minimum();
        this._root = this._removeMin(this._root);
        return minimum;
    }
    _removeMin(node) {
        if (node.left == null) {
            let rightNode = node.right;
            node.right = null;
            this._size--;
            return rightNode;
        }
        node.left = this._removeMin(node.left);
        return node; 
    }

    //      
    removeMax() {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        let maximum = this.maximum();
        this._root = this._removeMax(this._root);
        return maximum;
    }
    _removeMax(node) {
        if (node.right == null) {
            let leftNode = node.left;
            node.left = null;
            this._size--;
            return leftNode;
        }
        node.right = this._removeMax(node.right);
        return node;
    }

    //   
    remove(e) {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        let _this = this;
        this._root = _remove(this._root);
        function _remove(node) {
            if (node == null) {
                return null;
            }
            if (e < node.e) {
                node.left = _remove(node.left);
                return node;
            } else if (e > node.e) {
                node.right = _remove(node.right);
                return node;
            } else { //     
                if (node.left == null) {
                    let rightNode = node.right;
                    node.right = null;
                    _this._size--;
                    return rightNode;
                } else if (node.right == null) {
                    let leftNode = node.left;
                    node.left = null;
                    _this._size--;
                    return leftNode;
                } 
                //       
                let successor = _this._minimum(node.right);
                successor.right = _this._removeMin(node.right);
                successor.left = node.left;
                return successor;
            }
        }
    }

    //   
    find(e) {
        if (this.isEmpty) {
            throw new Error("data is empty");
        }
        return _find(this._root);
        function _find(node) {
            if (node == null) {
                return null;
            }
            if (e < node.e) {
                node.left = _find(node.left);
                return node.left;
            } else if (e > node.e) {
                node.right = _find(node.right);
                return node.right;
            } else {
                return node;
            }
        }
    }

    //     
    preOrder() {
        _preOrder(this._root);
        function _preOrder(node) {
            if (node == null) {
                return;
            }
            console.log(node.e);
            _preOrder(node.left);
            _preOrder(node.right);
        }
    }
    //     
    inOrder() {
        _inOrder(this._root);
        function _inOrder(node) {
            if (node == null) {
                return;
            }
            _inOrder(node.left);
            console.log(node.e);
            _inOrder(node.right);
        }
    }
    //      
    postOrder() {
        _postOrder(this._root);
        function _postOrder(node) {
            if (node == null) {
                return;
            }
            _postOrder(node.left);
            _postOrder(node.right);
            console.log(node.e);
        }
    }

    //     
    levelOrder() {
        let queue = new Queue();
        let node;
        queue.enqueue(this._root);

        while (!queue.isEmpty) {
            node = queue.dequeue();
            console.log(node.e.e);
            if (node.e.left != null) {
                queue.enqueue(node.e.left);
            }
            if (node.e.right != null) {
                queue.enqueue(node.e.right);
            }
        }
    }

    //         
    contains(e) {
        return _contains(this._root);
        function _contains(node) {
            if (node == null) {
                return false;
            }
            if (e < node.e) {
                node.left = _contains(node.left);
                return node.left;
            } else if (e > node.e) {
                node.right = _contains(node.right);
                return node.right;
            } else {
                return true;
            }
        }
    }
}

export default BST;

しゅうごう

配列実装

class Set {
   constructor() {
       this._data = [];
   }
   contains(e) {
       return this._data.includes(e);
   }
   add(e) {
       if (!this.contains(e)) {
           this._data.push(e);
       }
   }
   remove(e) {
       let index = this._data.indexOf(e);
       this._data.splice(index,1);
       return this._data[index];
   }
   get length() {
       return this._data.length;
   }
   get isEmpty() {
       return this.length == 0;
   }
}

export default Set;

チェーンテーブル実装

import LinkedList from "./LinkedList.js";

class Set {
    constructor() {
        this._data = new LinkedList();
    }
    contains(e) {
        return this._data.contains(e);
    }
    add(e) {
        if (!this.contains(e)) {
            this._data.insertFirst(e);
        }
    }
    remove(e) {
        return this._data.removeElement(e);
    }
    get length() {
        return this._data.length;
    }
    get isEmpty() {
        return this.length == 0;
    }
}

export default Set;

マッピング
データ量の挿入
双方向チェーンテーブルマッピング
配列マッピング
jsオブジェクト
3万
9.965秒
0.108秒
0.018秒
10万
33.22秒
0.247秒
0.043秒
双方向チェーンテーブルの検索と設定の複雑さはいずれもO(n)である.

class Node {
    constructor(key,value,prev=null,next=null) {
        this.key = key;
        this.value = value;
        this.next = next;
        this.prev = prev;
    }
}
class LinkedListMap {
    constructor() {
        this._root = null;
        this._tail = null;
        this._size = 0;
    }
    get size() {return this._size}
    get isEmpty() {return this._size === 0}
    contains(key) {
        if (typeof key !== "string") {throw("key need string type")}
        for(let cur=this._root; cur!=null; cur=cur.next) {
            if (cur.key === key) {
                return cur;   
            }
        }
        return null;
    }
    get(key) {
        if (typeof key !== "string") {throw("key need string type")}
        let ret = this.contains(key);
        return ret ? ret.value : null;
    }
    put(key, value) {
        if (typeof key !== "string") {throw("key need string type")}
        let ret = this.contains(key);
        if (ret !== null) { //     
            ret.value = value;
        } else { //      
            let node = new Node(key,value);
            if (this.size === 0) {
                this._root = node;
                this._tail = node;
            } else {
                node.prev = this._tail;
                this._tail.next = node;  
                this._tail = node;
            }
            this._size++;
        }
    }
    delete(key) {
        if (typeof key !== "string") {throw("key need string type")}
        let node = this.contains(key);
        if (node !== null) {
            if (key === this._root.key) {
                let next = this._root.next;
                this._root.next = null;
                this._root = next;
                if (next != null) { 
                    next.prev = null;
                } else { //       
                    this._tail = null
                }
            } else {
                node.prev.next = node.next;
                if (key === this._tail.key) {
                    this._tail = node.prev;
                } else {
                    node.next = null;
                    node.next.prev = null;
                }
            }
            this._size--;
        }
    }

}

配列実装log 2^nの検索と挿入

class ArrayMap {
    constructor() {
        this.keys = [];
        this.values = [];
    }
    get size() {return this.keys.length;}
    get isEmpty() {return this.keys.length === 0}
    get(key) {
        key = this._strToNum(key); 
        let i = this._search(key,0, this.size-1);
        return i !== -1 ? this.values[i] : null;
    }
    put(key, value) {
        key = this._strToNum(key);
        let index = this._search(key,0,this.size-1);
        if (index !== -1) {
            this.values[index] = value;
        } else {
            let begin = 0;
            let end = this.size-1;
            let middle = Math.floor(end/2);
            while (begin < end && this.keys[middle] != key) { //      
                if (this.keys[middle] > key) {
                    end = middle-1;
                } else if (this.keys[middle] < key) {
                    begin = middle+1;
                }
                middle = Math.floor(begin+(end-begin)/2);
            }
            if (this.keys[middle] > key) { //         ，      
                this.keys.splice(middle-1,0,key);
                this.values.splice(middle-1,0,value);
            } else {
                this.keys.splice(middle+1,0,key);
                this.values.splice(middle+1,0,value);
            }
        }
    }
    contains(key) {
        key = this._strToNum(key);
        return this._search(key,0, this.size-1) != -1;
    }
    delete(key) {
        key = this._strToNum(key);
        let i = this._search(key,0, this.size-1);
        if (i!==-1) {
            this.keys.splice(i,1);
            return this.values.splice(i,1)[0];
       } else {
           return null
       }
    }
    _strToNum(key) { //    key      ，            
        if (typeof key !== "string") {throw("key need string type")}
        let num = "";
        for (let i=0; i end) {
            return -1;
        }
        let middle = Math.floor(begin+(end-begin)/2);
        if (key === this.keys[middle]) {
            return middle;
        } else if (key < this.keys[middle]) {
            return this._search(key, begin, middle-1);
        } else if (key > this.keys[middle]) {
            return this._search(key, middle+1, end);
        }
    }
}

さいだいスタック

class MaxHeap {
    constructor(arr=[]) {
        this._data = arr;
        for (let i=this._parent(arr.length-1); i>=0; i--) {
            this._shiftDown(i);
        }
    }
    get length() {
        return this._data.length;
    }
    get isEmpty() {
        return this._data.length == 0;
    }
    add(e) {
        this._data.push(e);
        this._shiftUp(this._data.length-1);
    }
    get() {
        return this._data[0];
    }
    remove(e) {
        let ret = this._data.shift();
        this._shiftDown(0);
        return ret;
    }
    //       
    _parent(index) {
        if (index == 0) {
            throw new RangeError("index-0 doesn't parent");
        }
        return Math.floor((index-1) / 2);
    }
    //       
    _leftChild(index) {
        return index*2+1;
    }
    //       
    _rightChild(index) {
        return index*2+2;
    }

    //      
    _shiftUp(k) {
        let data = this._data;
        while (k>0 && data[this._parent(k)] < data[k]) {
            let parent = data[this._parent(k)];
            data[this._parent(k)] = data[k];
            data[k] = parent;

            k=this._parent(k);
        }
    }
    //      
    _shiftDown(k) {
        let size = this._data.length;

        while (this._leftChild(k) < size) {
            let j = this._leftChild(k);
            let data = this._data;
            if (j+1 < size && data[j+1] > data[j]) {
                j = this._rightChild(k);
            }
            if (data[k] > data[j]) {
                break;
            }
            let agent = data[k];
            data[k] = data[j];
            data[j] = agent;
            k=j;
        }
    }
}

export default MaxHeap;

ゆうせんキュー

import MaxHeap from "./MaxHeap.js";

class PriorityQueue {
    constructor() {
        this._data = new MaxHeap();
    }
    get length() {
        return this._data.length;
    }
    get isEmpty() {
        return this._data.isEmpty;
    }
    enqueue(e) {
        this._data.add(e);
    }
    dequeue() {
        return this._data.remove();
    }
    front() {
        return this._data.get();
    }
}

export default PriorityQueue;

接頭辞ツリー

class Node {
    constructor(isWord=false) {
        this.isWord = isWord;
        this.next = {};
    }
}
class Trie {
    constructor() {
        this._root = new Node();
        this._size = 0;
    }
    get size() {
        return this._size;
    }
    add(word) {
        let cur = this._root;
        for (let i=0; i

コレクションを調べる

class UnionFind {
    constructor(size) { // size     
        if (!size) {
            throw new TypeError("size is empty");
        }
        this._parent = new Array(size);
        this._rank = new Array(size); //    

        for (let i=0; i=parent.length) {
            throw new RangeError(`${p} is invalid`);
        }
        while (p != this._parent[p]) {
            this._parent[p] = this._parent[this._parent[p]];
            p = this._parent[p];
        }
        return p;
    }
    isConnected(p, q) {
        return this._find(p) == this._find(q);
    }
    unionElement(p, q) {
        let pRoot = this._find(p);
        let qRoot = this._find(q);

        if (pRoot == qRoot) {
            return;
        }
        if (this._rank[pRoot] < this._rank[qRoot]) { //          
            this._parent[pRoot] = qRoot;
        } else if (this._rank[pRoot] > this._rank[qRoot]) {
            this._parent[qRoot] = pRoot;
        } else {
            this._parent[qRoot] = pRoot;
            this._rank[pRoot] += 1;
        }
    }

}

export default UnionFind;

ハッシュ表

class HashTable {
    constructor(capacity) {
        if (!capacity) {
            throw new RangeError("capacity is empty");
        }
        this._data = new Array(capacity);
        this._size = 0;
        for (let i=0; i

図

//     
class DenseGraph {
    constructor(n, directed) {
        this._n = n; //  
        this._m = 0; //  
        this._directed = directed; //      
        this._g = [];
        for (let i = 0; i < n; i++) {
            let arr = new Array(n).fill(false);
            this._g.push(arr);
        }
    }
    get V() { return this._n }
    get E() { return this._m }
    addEdge(v, w) {
        if (this.hasEdge(v, w)) return;

        this._g[v][w] = true;
        if (!this._directed) {
            this._g[w][v] = true;
        }
        this._m++;
    }
    hasEdge(v, w) {
        if (v < 0 || v >= this._n) throw RangeError(v + " not exist");
        if (w < 0 || w >= this._n) throw RangeError(w + " not exist");
        return this._g[v][w];
    }
    DFS(v) { //       
        if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
        let visited = [];
        let _this = this;
        _dfs(v);
        function _dfs(v) {
            visited[v] = true;
            console.log(v);
            for (let i = v; i < _this._g.length; i++) {
                for (let j = 0; j < _this._g[i].length; j++) {
                    if (_this._g[i][j] && !visited[j]) {
                        _dfs(j);
                    }
                }
            }
            //            
            // for (let i = 0; i < _this._g.length; i++) {
            //     for (let j = 0; j < _this._g[i].length; j++) {
            //         if (_this._g[i][j] && !visited[j]) {
            //             _dfs(j);
            //         }
            //     }
            // }

        }
    }
    BFS(v) { //       
        if (!this._g[0].includes(v)) {throw new RangeError(v+" is not exist")}
        let queue = [];
        let visited = [];
        let node;
        queue.push(v);
        while (queue.length) {
            visited[v] = true;
            node = queue.shift();
            console.log(node);
            for (let i=node; i{
                    if (!visited[item]) {
                        _dfs(item);
                        visited[item] = true;
                    }
                })
            }
        }
    }
    BFS(v) {
        if (!this._edge[v]) {throw new RangeError(v+" is not exist")}
        let visited = {};
        let queue = [];
        let node;
        visited[v] = true;
        queue.push(v);

        while (queue.length) {
            node = queue.shift();
            console.log(node);
            this._edge[node].forEach(item=>{
                if (!visited[item]) {
                    queue.push(item);
                    visited[item] = true;
                }
            })
        }
    }
}