[JavaScript]データ構造とアルゴリズム——チェーン表

本編は主に3つの部分がある.

チェーンは何ですか?

チェーンの実現

チェーンの変種

ソースの住所:https://github.com/yhtx1997/S...
また、今日2019年2月18日午前に2048-vue版が発見されました.コードバージョンが正しくなく、最新バージョンが失われました.仕方なく再修復しました.https://github.com/yhtx1997/S...
チェーンは何ですか
チェーンテーブルは秩序化された要素セットを記憶していますが、配列とは異なり、チェーンテーブルの要素はメモリに連続的に配置されていません.各要素は、記憶要素自体のノードと、次の要素を指す参照(ポインタまたはリンクとも称する)から構成される.従来の配列に対して、チェーンテーブルの利点は、要素を追加または除去する際に他の要素を移動する必要がないことです.しかし、チェーンはポインタを使う必要がありますので、チェーンを実現するには追加の注意が必要です.配列の他の詳細は、任意の位置の任意の要素に直接アクセスすることができ、チェーンテーブルの中間の要素にアクセスするには、起点(ヘッダ)から必要な要素が見つかるまで反復リストを開始する必要があります.下記の図:注:00 06 10 12 18はメモリ内のアドレスを想定しています.
出来上がったチェーンをデータに入れて、コンソールで印刷します.
それはこのように見えます.
実は次のように、犬をつなぐ鎖のようなものです.
チェーンの実現
チェーン機能

追加要素

は、指定された位置要素

を取得する.

は、指定された位置に要素

を挿入する.

指定された位置の要素

を除去する.

は、指定された要素の位置

を返します.

指定要素を削除する

は空かどうか

長さ

は、ヘッダ

を取得する.

クリアランス

は文字列出力

に変換される.

//     
class Node {
    constructor(element) {
        this.element = element; //   
        this.next = undefined; //        
    }
}
class LinkedList {
    //             
    constructor(){
        this.count = 0; //   
        this.head = undefined; //      
    }
    //     
    push(element) {
        
    }
    //         
    getElementAt(index) {
        
    }
    //          
    insert(element, index) {
        
    }
    //          
    removeAt(index) {
    
    }
    //          
    indexOf(element) {
        
    }
    //       
    remove(element) {
        
    }
    //     
    isEmpty() {
        
    }
    //   
    size() {
        
    }
    //     
    getHead() {
       
    }
    //     
    clear() {
        
    }
    //         
    toString() {
        
    }
}

コードの実装

class LinkedList {
    //             
    constructor(){
        this.count = 0; //   
        this.head = undefined; //      
    }
    //     
    push(element) {
        const node = new Node(element);
        if (this.head === undefined) {
            this.head = node;
        } else {
            let current = this.head;
            while (current.next !== undefined) {
                current = current.next;
            }
            current.next = node;
        }
        this.count++;
    }
    //         
    getElementAt(index) {
        //        
        if (this.isEmpty() || index > this.count || index < 0) { 
            //         
            //          ，       （0）
            return undefined;
        }
        //       
        let current = this.head;
        for (let i = 0; i < index; i++){
            current = current.next;
        }
        return current;//        
    }
    //          
    insert(element, index) {
        //       
        let current = new Node(element);
        //              
        if (index === 0){
            current.next = this.head;
            this.head = current;
        } else {
            //            
            let previous = this.getElementAt(index - 1);
            //         next          next
            current.next = previous.next;
            //        node           next
            previous.next = current;
        }
        this.count++;
    }
    //          
    removeAt(index) {
        let current = this.head;
        if (index === 0){
            this.head = current.next;
        } else {
            //                 
            let previous = this.getElementAt(index - 1);
            current = previous.next;
            //        next              next
            previous.next = current.next;
        }
        this.count--;
        //         
        return current.element;
    }
    //          
    indexOf(element) {
        //      
        let current = this.head;
        //        
        for (let i = 0; i < this.size() && current != null; i++){
            if (current.element === element){ //           
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    //       
    remove(element) {
        //         
        let index = this.indexOf(element);
        //         
        return this.removeAt(index);
    }
    //     
    isEmpty() {
        return this.size() === 0;
    }
    //   
    size() {
        return this.count;
    }
    //     
    getHead() {
        return this.head;
    }
    //     
    clear() {
        this.head = undefined;
        this.count = 0;
    }
    //         
    toString() {
        if (this.head == null) {
            return '';
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current != null; i++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }
        return objString;
    }
}
let a = new LinkedList();
a.push('a');
a.push('b');
a.push('c');
a.push('d');
a.push('e');
a.push('f');
a.push('h');
a.push('i');
a.push('j');
a.push('k');
a.push('l');
a.push('m');
a.push('n');
a.push('o');
a.push('p');
a.push('q');
a.remove('a');
a.insert('a',1);
console.log(a);

要素の図解を挿入する:
今は犬のチェーンが二つあります.真ん中にもう一つのセクションを追加したいです.
まず二つの節を分けます.
それから前の尾部をプラスする頭部と連結して、後の頭部と連結します.
0連xx、xx連1
チェーンの変種
双方向リンク表
チェーンテーブルの各要素は、記憶要素自体のノードと次の要素を指す参照(ポインタまたはリンクともいう)から構成されていることが分かりました.この基本的な特性に加えて、各要素は前の要素を指す参照も含まれています.
循環リンク表
循環チェーンとは、チェーンの最後の次の要素を指す参照が最初の要素を指し、循環チェーンとして使われます.
双方向循環リンク表
双方向循環チェーン表とは、双方向リンク表の最初の要素が前の参照を指して最後の要素を指し、最後の要素が次の要素を指す参照は、図に示すように、最初の要素を指しています.