JavaScriptを使って双方向リンク表を実現します.

JavaScriptを使って双方向リンク表を実現します.
前言
JavaScript自体には指針がないので、チェーンを実現するには既存のデータ構造がなく、自分で書くしかないです.チェーンテーブルの基本概念については、本明細書では多くの詳細に説明しないが、チェーンテーブルの利点は、ノードの削除と新規ノードの配列のように「引っ張って全身を動かす」ことはないが、そのデータ構造が複雑であることである.
実現する
本論文で実現されるのは双方向リンク表であり、本質的には配列で保存されるものであり、以下の機能を含んでいる.

ヘッドノードを追加しました.

ヘッドノード

を削除する.

に、ノード

が追加されました.

は、エンドノード(pop)

を削除する.

エルゴード出力完全チェーン

位置決めヘッド、尾ポインタ

不要ノードをリサイクルする

.
コード解析
初期化動作:このチェーンテーブルは、1つの配列を初期化データとして受け入れ、その「転化」をチェーンテーブルにしてもいいです.本質的には、チェーンテーブルは1つの配列で保存しています.各配列要素は、そのポインタ、データ値、前後のポインタを含みます.チェーンテーブルを初期化する以外に、ヘッドポインタ、テールポインタ、チェーン長などのデータメンバーを定義しています.

    class Chain {
        constructor(arr = []) {
            //          
            this.chain = []
            this.chain.length = arr.length
            //        “  ”     ，              
            for (let i = 0; i < arr.length; i++) {
                this.chain[i] = {
                    //      
                    index: i,
                    //     
                    element: arr[i],
                    //         
                    prev: i - 1,
                    //         
                    next: i < arr.length - 1 ? i + 1 : -1
                }
            }
            //      
            this.length = this.chain.length
            //    
            this.head = arr.length ? 0 : -1
            //    
            this.tail = arr.length ? arr.length - 1 : -1
            //    
            this.free = arr.length
            //           ，         
            this.freeList = []
        }

巡回出力の完全なリンク表

        //          
        toString () {
            let current = this.head
            let string = ''
    
            while (current !== -1) {
                string += this.chain[current].element + (this.chain[current].next !== -1 ? ',' : '')
                current = this.chain[current].next
            }
    
            console.log(string)
        }

接点をpop,push,shift,unshift操作します.

        //      
        shift() {
            this.collection()
            //         ，    
            this.free = this.head
            //         
            this.head = this.chain[this.head].next
            //                     -1
            this.head !== -1 && (this.chain[this.head].prev = -1)
            //      -1         -1
            --this.length === 0 && (this.tail = -1)
            //       
            return this.chain[this.free]
        }
    
        //      
        unshift(element) {
            //       
            let sec = this.head
            //           
            this.head = this.free
            //       
            this.chain[this.head] = {
                index: this.head,
                prev: -1,
                next: sec,
                element: element
            }
            //                           
            if (sec !== -1) {
                this.chain[sec].prev = this.head
            } else {
                //        ，        ，        
                this.tail = this.head
            }
            //        
            this.calloc()
            //     +1
            this.length++
        }
    
        //      
        push (element) {
            let last = this.tail
            //         
            this.tail = this.free
            //          
            this.chain[this.tail] = {
                index: this.tail,
                prev: last,
                next: -1,
                element: element
            }
            //                           
            if (last !== -1) {
                this.chain[last].next = this.tail
            } else {
                //        ，        ，        
                this.head = this.tail
            }
            //        
            this.calloc()
            //     +1
            this.length++
        }
    
        //      
        pop () {
            this.collection()
            //         ，    
            this.free = this.tail
            //             
            this.tail = this.chain[this.tail].prev
            //                     -1
            this.tail !== -1 && (this.chain[this.tail].next = -1)
            //      -1         -1
            --this.length === 0 && (this.head = -1)
            //       
            return this.chain[this.free]
        }

先頭ノードに戻る

        //      
        first() { 
            return this.chain[this.head]
        }
    
        //      
        last() {
            return this.chain[this.tail]
        }

空のポインタを回収して再分配します.

        //        
        calloc() {
            //          
            this.free = this.freeList.length ? this.freeList.pop() : this.chain.length
        }
    
        //      
        collection() {
            //               
            this.freeList.push(this.free)
        }
    }

おわりに
本文はJavaScriptで双方向チェーンの基本機能を実現しましたが、怠け者です.指定された位置を挿入したり、指定されたノードを削除したりする機能が実現されていません.今後もこれらの機能を改善していきます.
この文章があなたのために役に立つと思ったら、下にほめてください.こんなにきれいで根気よく文章を読み終えてくれてありがとうございます.٩()ω')و問題があったらいつでも下にメッセージを書いてください.全力を尽くして答えます.