javascript鏈表實(shí)現(xiàn)

Imfan 發(fā)布于2019-08-22 10:58 / 1239人閱讀

摘要：而遍歷鏈表，則是跟著首元素一直遍歷至尾元素。單鏈表代碼實(shí)現(xiàn)類實(shí)現(xiàn)類用來設(shè)置鏈表的節(jié)點(diǎn)相關(guān)信息本節(jié)點(diǎn)信息指向下一個節(jié)點(diǎn)的指針類實(shí)現(xiàn)類實(shí)現(xiàn)的是一些對鏈表進(jìn)行操作的方法，包括插入刪除節(jié)點(diǎn)查找節(jié)點(diǎn)等。

單鏈表初識

鏈表是由一組節(jié)點(diǎn)組合成的集合.每個節(jié)點(diǎn)都使用一個對象的引用指向它的后繼，指向另一個節(jié)點(diǎn)的引用叫做鏈

數(shù)組元素靠他們的位置進(jìn)行引用，鏈表元素則是靠相互之間的關(guān)系進(jìn)行引用，在下圖中bread跟在milk后面而不是說bread是鏈表中的第二個元素。
而遍歷鏈表，則是跟著首元素一直遍歷至尾元素。由圖可知尾元素指向一個null元素。

為了更好的標(biāo)志處鏈表的起始節(jié)點(diǎn)，我們在前面設(shè)置一個特殊節(jié)點(diǎn)，叫做頭節(jié)點(diǎn)

插入節(jié)點(diǎn)：在鏈表中插入一個節(jié)點(diǎn)效果非常的高，需要修改其前面的節(jié)點(diǎn)，使指針指向新節(jié)點(diǎn)

刪除節(jié)點(diǎn)：刪除節(jié)點(diǎn)即是將待刪除元素的前驅(qū)節(jié)點(diǎn)指向待刪除元素的后繼節(jié)點(diǎn)。

單鏈表代碼實(shí)現(xiàn) Node類實(shí)現(xiàn)

    //Node類用來設(shè)置鏈表的節(jié)點(diǎn)相關(guān)信息 
    // 1 本節(jié)點(diǎn)信息 2 指向下一個節(jié)點(diǎn)的指針
    function Node(ele){
        this.element=ele;
        this.next=null;
    }

Llist類實(shí)現(xiàn)

Llist類實(shí)現(xiàn)的是一些對鏈表進(jìn)行操作的方法，包括插入、刪除節(jié)點(diǎn)、查找節(jié)點(diǎn)等。
插入節(jié)點(diǎn)

     //Llist類的實(shí)現(xiàn)

        function Llist(){
            this.head=new Node("head");
        }
        //添加方法
        Llist.prototype={
            find:function(ele){
                var curNode=this.head//從頭節(jié)點(diǎn)開始遍歷
                while(curNode.element!=ele){
                    curNode=curNode.next;
                }
                return curNode;//返回找到的節(jié)點(diǎn) 若是沒有找到則返回的是null
            },
            insert:function(newEle,ele){//插入節(jié)點(diǎn)
                var newNode=new Node(newEle);
                var curNode=this.find(ele);
                    newNode.next=curNode.next;
                    curNode.next=newNode;
            },
            display:function(){//遍歷顯示節(jié)點(diǎn)信息
                var curNode=this.head;
                while(curNode.next!=null){
                    console.log(curNode.next.element);//只顯示有數(shù)據(jù)的節(jié)點(diǎn)
                    curNode=curNode.next;
                }
            }
        }

測試

             //測試
            var citys=new Llist();
            citys.insert("贛州","head");
            citys.insert("江西","贛州");
            citys.insert("南昌","江西");
            citys.display();

明天開始校招，先寫到這里^+^