数据结构--单链表

单链表：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
结构如下图：

image.png

Head时一个指针，存放的时第一个节点的地址，表示为：head=node(第一个节点)
节点中的nest存放的时再下一个节点的地址。

添加节点
插入节点
查询节点
删除节点

添加节点

添加节点：
未添加之前：
添加之前得判断头节点是否存在，头节点时用来遍历链表的起始存在，如果头节点为空，那么头指针就只想插入的节点：head=node;
有数据插入：

image.png

添加之后

image.png

JS实现：

function createLinkList(){
    //节点信息
    var Node=function(data){
        this.data=data;//节点信息
        this.next=null;//下一个节点信息
    };
    var head=null,//头指针
        last=null,//尾指针
        length=0;//链表长度
    //在尾节点添加
    this.append=function(data){
        //实例化节点
        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();

插入节点：

原理图：
未插入之前：

image.png

插入过程,目标是吧data2插入到data1前面：

image.png
image.png
image.png
如图，我们需要先断开与data1的联系，把data2连接上，然后再把data1连接到后面。

我分了三种情况做的插入：

1. 链表为空时插入 -----因为为空时不需要插入，这个就是头节点了。
2. 插入到第一个链表时-----插入到第一个节点时，只需要把这个节点指向头节点就行了
3. 插入到中间与结尾部分时-----需要轮询到这里，然后断开前面的节点，插入后面的节点

this.insert=function(index,data){
    var node = new Node(data);
    if(head==null){
    //链表为空时
        head=node;
        last=node;
    }else if(index==0){
        //要插入到链表头部时
        node.next=head;
        head=node;
    }else{
        //插入到后面的节点中
        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++;
        }
    }
}

查询节点：

没什么说的就是遍历节点，然后返回这个节点的信息就行了，不过很慢。
下面的代码直接轮询判断每个节点，但是while的缺点是不能判断最后一个，因此再最后又判断了一遍
直接看代码吧：

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";
}

删除节点

删除就是把要删除的节点给断开连接，这样的话垃圾回收器会自动清除那部分资源并释放。
分为两种情况：
一个是删除第一个，一个是删除后面的，分情况考虑。
如同下图所示：

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;
        }
    }
}