數(shù)據(jù)結(jié)構(gòu)--單鏈表

單鏈表：?jiǎn)捂湵硎且环N鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點(diǎn)來(lái)表示的，每個(gè)結(jié)點(diǎn)的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲(chǔ)位置)，元素就是存儲(chǔ)數(shù)據(jù)的存儲(chǔ)單元，指針就是連接每個(gè)結(jié)點(diǎn)的地址數(shù)據(jù)。
結(jié)構(gòu)如下圖：

image.png

Head時(shí)一個(gè)指針，存放的時(shí)第一個(gè)節(jié)點(diǎn)的地址，表示為：head=node(第一個(gè)節(jié)點(diǎn))
節(jié)點(diǎn)中的nest存放的時(shí)再下一個(gè)節(jié)點(diǎn)的地址。

添加節(jié)點(diǎn)
插入節(jié)點(diǎn)
查詢節(jié)點(diǎn)
刪除節(jié)點(diǎn)

添加節(jié)點(diǎn)

添加節(jié)點(diǎn)：
未添加之前：
添加之前得判斷頭節(jié)點(diǎn)是否存在，頭節(jié)點(diǎn)時(shí)用來(lái)遍歷鏈表的起始存在，如果頭節(jié)點(diǎn)為空，那么頭指針就只想插入的節(jié)點(diǎn)：head=node;
有數(shù)據(jù)插入：

image.png

添加之后

image.png

JS實(shí)現(xiàn)：

function createLinkList(){
    //節(jié)點(diǎn)信息
    var Node=function(data){
        this.data=data;//節(jié)點(diǎn)信息
        this.next=null;//下一個(gè)節(jié)點(diǎn)信息
    };
    var head=null,//頭指針
        last=null,//尾指針
        length=0;//鏈表長(zhǎng)度
    //在尾節(jié)點(diǎn)添加
    this.append=function(data){
        //實(shí)例化節(jié)點(diǎn)
        var node=new Node(data);
        if (head==null){
            head=node;
            last=head;
        }else{
            var current=head;
            while(current.next!=null){
                current=current.next;
            }
            current.next=node;
            last=current;
        }
        length++;
    };
    this.display=function(){
        var current=head;
        while(current.next!=null){
            console.log(current.data);
            current=current.next;
        }
        console.log(current.data);
    };
    this.size=function(){
        return length;
    }
}

var linkList=new createLinkList();
linkList.append("arron1")
linkList.append("arron2")
linkList.append("arron3")
linkList.display();

插入節(jié)點(diǎn)：

原理圖：
未插入之前：

image.png

插入過(guò)程,目標(biāo)是吧data2插入到data1前面：

image.png

image.png

image.png

我分了三種情況做的插入：

1. 鏈表為空時(shí)插入 -----因?yàn)闉榭諘r(shí)不需要插入，這個(gè)就是頭節(jié)點(diǎn)了。
2. 插入到第一個(gè)鏈表時(shí)-----插入到第一個(gè)節(jié)點(diǎn)時(shí)，只需要把這個(gè)節(jié)點(diǎn)指向頭節(jié)點(diǎn)就行了
3. 插入到中間與結(jié)尾部分時(shí)-----需要輪詢到這里，然后斷開(kāi)前面的節(jié)點(diǎn)，插入后面的節(jié)點(diǎn)

this.insert=function(index,data){
    var node = new Node(data);
    if(head==null){
    //鏈表為空時(shí)
        head=node;
        last=node;
    }else if(index==0){
        //要插入到鏈表頭部時(shí)
        node.next=head;
        head=node;
    }else{
        //插入到后面的節(jié)點(diǎn)中
        var current=head;
        var llength=0;
        while(current.next!=null){
            if(llength+1==index){
                node.next=current.next;
                current.next=node;
                length++;
                if(llength+1==length){
                    last=current;
                }
                break;
            }
            current=current.next;
            llength++;
        }
        if (index==length) {
            current.next=node;
            length++;
        }
    }
}

查詢節(jié)點(diǎn)：

沒(méi)什么說(shuō)的就是遍歷節(jié)點(diǎn)，然后返回這個(gè)節(jié)點(diǎn)的信息就行了，不過(guò)很慢。
下面的代碼直接輪詢判斷每個(gè)節(jié)點(diǎn)，但是while的缺點(diǎn)是不能判斷最后一個(gè)，因此再最后又判斷了一遍
直接看代碼吧：

this.find=function(data){
    var current=head;
    var llength=0;
    var result=null;
    while(current.next!=null){
        if(data==current.data){
            result=current;
            break;
        }
        current=current.next;
        llength++;
    }
    if(data==current.data){
        result=current;
    }
    return result?{length:llength,result}:"NO Have Data";
}

刪除節(jié)點(diǎn)

刪除就是把要?jiǎng)h除的節(jié)點(diǎn)給斷開(kāi)連接，這樣的話垃圾回收器會(huì)自動(dòng)清除那部分資源并釋放。
分為兩種情況：
一個(gè)是刪除第一個(gè)，一個(gè)是刪除后面的，分情況考慮。
如同下圖所示：

image.png

image.png

this.delete=function(data){
    var current=head;
    if(data==current.data){
        head=current.next;
        current=head;
    }else{
        while(current.next!=null){
            if(data==current.next.data){
                current.next=current.next.next;
                break;
            }
            current=current.next;
        }
    }
}