Biegral Blog

链表

链接也是一种存储数据的工具，不同于数组，链表中的元素并不是连续存储的。因此不能通过下标去访问。 链表分为单(向)链表，双向链表，循环链表等。.今天来实现一下单链表。
单链表中的每个元素包括两个两个域，一个是保存元素本身的域，另一个是指向一下一个节点的指针域

    function LinkedList(){
        var Node = function( ele ){
            this.ele = ele;     //ele  属性代表插入的值
            this.next = null;   //  next属性 代表 指向下一个节点的指针
        }
        var head = null;
        var length = 0;


        // 向链表末尾插入一个元素
        this.append = function(ele){
            var node = new Node(ele);
            var currentNode = null;

            if( head === null){    // 列表为空，插入的节点是第一个头结点
                head = node;
            }
            else{
                currentNode = head;
                // 循环链表，直到最后一个节点
                while( currentNode.next !== null ){
                    currentNode = currentNode.next;
                }
                // 出了while循环，说明找到了最后一个节点
                currentNode.next = node;

            }
            length++;
        }
        // 删除链表中指定的某个节点:删除头结点 or  除了头结点以外的节点
        this.removeAt = function( position ){
            var currentNode = head;
            var previousNode = null;
            var index = 0;

            if( position >= 0 && position < length ){
                if( position === 0 ){
                    node = currentNode.next;
                }
                else{
                    while( index++ < position ){
                        previousNode = currentNode;
                        currentNode = currentNode.next;
                    }
                    // 出了while循环， index === position
                    previousNode.next = currentNode.next;
                }
                length--;
                return currentNode.ele
            }
            // 要删除的节点的不存在
            else{

                return -1;
            }
        }
        // 在任意位置插入一个元素
        this.insert = function(){
            // 检查是否越界
            if( position >= 0 && position <= length ){
                var newNode = new Node(ele);
                var currentNode = head;   // 保存一下头结点
                var previousNode = null;
                var index = 0;

                if( position === 0 ){
                   newNode.next = currentNode;
                   head = newNode;
                }
                else{
                    while ( index++ < position ){
                        previousNode = currentNode;
                        currentNode = currentNode.next;
                    }
                    // 出了循环表示找到位置
                    newNode.next = currentNode;
                    previousNode.next = currentNode;
                }
                length++;
                return 1;
            }
            else{
                return -1;
            }
        }

        //查找链表中的某个元素所在位置， 无此元素返回 -1
        this.find = function(ele){
             var currentNode = head;
             var index = 0;
             while( currentNode ){
                if( currentNode.ele = ele ){
                    return index;
                }
                currentNode = currentNode.next;
                index++; 
            }  
            return -1;
        }       

        this.isEmpty = function(){
            return length === 0;
        }

        this.size = function(){
            return length;
        }

    }

下面来实现链表的反转

function reverse( linkedList ){
    var head = linkedList.head;

    // 如果只有一个节点 或者 是空链表
    if( head === null || head.next === null ){
        return;
    }
    var p = head;
    var q = p.next;
    // 反转后的头结点变成尾节点
    head.next = null;
    while(q){
        r = q.next;
        q.next = p;
        p = q;
        q = r;
    }
    // 退出循环后 r = q.next = null, q.next = q; p=q; q=null;
    // p指向原来节点的尾节点， 那么翻转后，尾节点变成头结点
    linkedList.head = p;
}