JavaScript数据结构2——单链表

以下的代码包括了以下几部分

• 单链表初始化
• 单链表的插入
• 单链表的删除
• 单链表的创建（头插法）
• 单链表的创建（尾插法）

//节点
function Node(data,next) {
    this.data = data;
    this.next = next;
};
//链表
function NodeList(node0){
    this.next = node0;
}
this.node0;
this.node1;
this.node2;
//初始化一个链表
node2 = new Node(3,null);
node1 = new Node(2,node2);
node0 = new Node(1,node1);
var list = new NodeList(node0);
//获取元素
NodeList.prototype.getNode = function(n) {
    if(n==-1){
            return this;
    }
    else if(n<0){
        return undefined;
    }
    else{
        var elem = this;
        var i = 0;
        do{
            elem = elem.next;
            if(!elem){
                return undefined;
            }
            i++;
        }while(i<=n);
        return elem;
    }
};
//插入元素
NodeList.prototype.insertNode = function(i,elem){
    if(i<0){
        return undefined;
    }
    else{
        var p = this.getNode(i-1);
        elem.next = p.next;
        p.next = elem;
    }
}
//删除元素
NodeList.prototype.deleteNode = function(i){
    this.getNode(i-1).next = this.getNode(i+1);
    delete this.getNode(i);
}
//创建单链表(头插法)
function createListHead(num){
    var list = new NodeList(null);
    for (var i = 0; i < num; i++) {
        var node = new Node(Math.round(Math.random()*10000),null);
        node.next = list.next;
        list.next = node;
    }
    return list;
}
//创建单链表(尾插法)
function createListTail(num){
    var list = new NodeList(null);
    var p = list;
    for (var i = 0; i < num; i++) {
        var node = new Node(Math.round(Math.random()*10000),null);
        p.next = node;
        p = node;
    }
    return list;
}
console.info('当前链表'+JSON.stringify(list));
//获取第一个元素
console.info('获取第一个元素:\n'+list.getNode(0).data);
//获取第二个元素
console.info('获取第二个元素:\n'+list.getNode(1).data);
//插入元素
list.insertNode(0,new Node(1000,null));
console.info('向第一个位置插入一个元素1000，插入之后获取第一个元素:\n'+
    list.getNode(0).data);
console.info('获取第二个元素:\n'+list.getNode(1).data);
//插入元素
console.info('当前链表'+JSON.stringify(list));
list.insertNode(1,new Node(2000,null));
console.info('向第二个位置插入一个元素2000，插入之后获取第二个元素:\n'+
    list.getNode(1).data);
console.info('获取第三个元素:\n'+list.getNode(2).data);
console.info('当前链表'+JSON.stringify(list));
list.deleteNode(2);
console.info('删除第三个元素,当前的第三个元素是:\n'+list.getNode(2).data);
console.info('当前链表'+JSON.stringify(list));
console.info('创建单链表(头插法)\n'+JSON.stringify(createListHead(10)));
console.info('创建单链表(尾插法)\n'+JSON.stringify(createListTail(10)));

打印台输出为

当前链表{"next":{"data":1,"next":{"data":2,"next":{"data":3,"next":null}}}}
获取第一个元素:
1
获取第二个元素:
2
向第一个位置插入一个元素1000，插入之后获取第一个元素:
1000
获取第二个元素:
1
当前链表{"next":{"data":1000,"next":{"data":1,"next":{"data":2,"next":{"data":3,"next":null}}}}}
向第二个位置插入一个元素2000，插入之后获取第二个元素:
2000
获取第三个元素:
1
当前链表{"next":{"data":1000,"next":{"data":2000,"next":{"data":1,"next":{"data":2,"next":{"data":3,"next":null}}}}}}
删除第三个元素,当前的第三个元素是:
2
当前链表{"next":{"data":1000,"next":{"data":2000,"next":{"data":2,"next":{"data":3,"next":null}}}}}
创建单链表(头插法)
{"next":{"data":2357,"next":{"data":7764,"next":{"data":3891,"next":{"data":7510,"next":{"data":3047,"next":{"data":2975,"next":{"data":42,"next":{"data":4948,"next":{"data":5293,"next":{"data":3913,"next":null}}}}}}}}}}}
创建单链表(尾插法)
{"next":{"data":8471,"next":{"data":3457,"next":{"data":4029,"next":{"data":3596,"next":{"data":1630,"next":{"data":4171,"next":{"data":7875,"next":{"data":359,"next":{"data":3750,"next":{"data":9982,"next":null}}}}}}}}}}}