チェーンテーブル

フロントエンドの面接では、チェーンテーブルはよく聞かれます.チェーンテーブルの結果やチェーンテーブルの操作方法を熟知することが重要です.複数の要素を格納する場合、配列は最も一般的なデータ構造である可能性があります.このデータ構造は非常に便利で、コンビニエンスストア[]構文を提供して要素にアクセスします.しかし配列の欠点は,要素を挿入または削除するコストが高く,要素を移動する必要があることである.チェーンテーブルには、整列した要素の集合が格納されますが、配列とは異なり、チェーンテーブルの要素はメモリに連続的に配置されていません.各要素は、1つのストレージ要素自体のノードと、次の要素への参照から構成されます.チェーンテーブルの利点の1つは、要素を追加または削除するときに他の要素を移動する必要がないことです.配列のもう1つの詳細は、任意の場所の任意の要素に直接アクセスできますが、チェーンテーブルの中央にある要素にアクセスするには、必要な要素が見つかるまで、開始点からリストを反復する必要があります.

チェーンテーブルの作成

function LinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
    }
    var length = 0;
    var head = null;
}

チェーンテーブルの方法

append(element)--チェーンテーブルの末尾に新しいアイテムinsert(position,element)--チェーンテーブルの特定の場所に新しいアイテムremove(element)--チェーンテーブルからエレメントindexOf(element)--チェーンテーブル内のエレメントのインデックスを返します.チェーンテーブルに要素がない場合は-1 removeAt(position)--チェーンテーブルの特定の場所からisEmpty()を削除します.チェーンテーブルに要素が含まれていない場合はtrueを返します.チェーンテーブルの長さが0より大きい場合はfalsesize()を返します.チェーンテーブルに含まれる要素の数を返します.

チェーンテーブルの完全なコード

function LinkedList(){
        var Node = function(element){
            this.element = element;
            this.next = null;
        }
        var length = 0;
        var head = null;
        
       this.append = function(element){
           var node = new Node(element),current;
           if(head === null){
               head = node;
           } else {
               current = head;
               //    ，      
               while(current.next){
                   current = current.next;
               }
               //      ，  next   node
               current.next = node;
           }
           length++;
       };
       
       this.removeAt = function(position){
           if(position > -1 && position < length){
               var current = head,
               previous,
               index = 0;
               
               if(position === 0){
                   head = current.next;
               } else {
                   while(index++ < pisition){
                       previous = current;
                       current = current.next;
                   }
                   previous.next = current.next;
               }
               length--;
               
               return current.element;
           } else {
               return null;
           }
       };
       
       this.insert = function(position, element){
           if(position >= 0 && position <= length){
               var node = new Node(element),
               current = head,
               previous,
               index = 0;
               
               if(position === 0){
                   node.next = current;
                   head = node;
               } else {
                   while(index++ < position){
                       previous = current;
                       current = current.next;
                   }
                   previous.next =node;
                   node.next = current;
               }
               
               length++;
               
               return true;
           } else {
               return false;
           }
       };
       
       this.indexOf = function(element){
           var current = head, index = 0;
           while(current){
               if(element === current.element){
                   return index;
               }
               index++;
               current = current.next;
           }
           return -1;
       };
       
       this.remove = function(element){
           var index = this.indexOf(element);
           return this.removeAt(index);
       }
       
       this.isEmpty = function(){
           return length === 0;
       }
       
       this.size = function(){
           return length;
       }
       
       this.getHead = function(){
           return head;
       }
       
 }
 

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

双方向チェーンテーブルと通常のチェーンテーブルの違いは、チェーンテーブルでは、1つのノードがチェーンの次のノードへのリンクしかなく、双方向チェーンテーブルではリンクが双方向であることです.

function DoublyLinkedList(){
    var Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null;
    };
    var length = 0;
    var head = null;
    var tail = null;
    
    this.insert = function(position, element){
        if(position >= 0 && position <= length){
            var node = new Node(element),
            current = head,
            previous,
            index = 0;
            if(position === 0){
                if(!head){
                    head = node;
                    tail = node;
                } else {
                    node.next = current;
                    current.previous = node;
                    head = node;
                }
            } else if(position === length){
                current = tail;
                current.next = node;
                node.previous = current;
                tail = node;
            } else {
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
                
                current.prev = node;
                node.prev = previous;
            }
            length++;
            return true;
        } else {
            return false;
        }
    };
    
    this.removeAt = function(position){
        if(position > -1 && position < length){
            var current = head,
            previous,
            index = 0;
            if(position === 0){
                head = current.next;
                if(length === 1){
                    tail = null;
                } else {
                    head.prev = null;
                }
            } else if(position === length-1){
                current = tail;
                tail = current.prev;
                tail.next = null;
            } else {
                while(index++ < position){
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
                current.next.prev = previous;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    }
}

参考書:Learning Javascript Data Structures and Algorithms
vue、angularコンポーネントを探すホイール工場をお勧めします
フロントエンド面接総括--データ構造とアルゴリズム1フロントエンド面接総括--データ構造とアルゴリズム2フロントエンド面接総括--データ構造とアルゴリズム3