JavaScript数据结构3——静态链表

静态链表是用数组来实现链表的基本操作，对于没有引用功能和指针功能的语言，是不错的选择，下面的程序实现了以下的功能

• 读取
• 插入
• 删除

var list_max_size = 10;
//静态链表基本元素
function Compontent(data,cur) {
    this.data = data;//数据
    this.cur = cur;//游标
}
//获得一个初始化的静态链表
function initList() {
    for(var i=0;i<list_max_size-1;i++){
        list[i] = new Compontent(null,i+1);
    }
    //数组的最后一位要存放第一个元素的下标
    //数组的第一个元素存放备用链表的第一个节点的下表
    list[list_max_size-1] = new Compontent(null,0);
}
//申请新元素
//若备用链表非空，返回分配的结点下标，否则返回0
function mallocSll() {
    var i = list[0].cur;
    if(i){
        list[0].cur = list[i].cur;
    }
    return i;
}
//插入
function insertList(i,data) {
    var j,k;
    k = list_max_size-1;
    if(i<1||i>list.length+1){
        return 1;
    }
    j = mallocSll(list);
    if(j){
        list[j].data = data;
        //获取i位置前面的元素
        for(var l=1;l<=i-1;l++){
            k = list[k].cur;
        }
        list[j].cur = list[k].cur
        list[k].cur = j;
        return 0;
    }
    return 1;
}
//删除第i个元素
function deleteComponent(i){
    if(i<1||i>list.length){
        return 1;
    }
    k = list_max_size-1;
    for (var j = 1; j <=i-1; j++) {
        k = list[k].cur;
    }
    j = list[k].cur;
    list[k].cur = list[j].cur;
    list[j].cur = list[0].cur;
    list[j].data = null;
    list[0].cur = j;
}
//读取链表
function readList(){
    var l = 0;
    var string = '';
    do{
        l = list[l].cur;
        if(list[l].data!=null){
            string += list[l].data;
        }
    }
    while(l!=0);
    return string;
}
var list = new Array(list_max_size);
initList();
console.info(JSON.stringify(list));
insertList(1,1);
console.info('建立第一个元素\n'+JSON.stringify(list));
console.info('建立第一个元素:'+readList());
insertList(1,2);
console.info('在第一个元素前面插入一个数据\n'+JSON.stringify(list));
console.info('在第一个元素前面插入一个数据:'+readList());
insertList(2,3);
console.info('在第二个元素前面插入一个数据\n'+JSON.stringify(list));
console.info('在第二个元素前面插入一个数据:'+readList());
deleteComponent(2);
console.info('删除第二个元素\n'+JSON.stringify(list));
console.info('删除第二个元素:'+readList());

打印到控制台的结果

[{"data":null,"cur":1},{"data":null,"cur":2},{"data":null,"cur":3},{"data":null,"cur":4},{"data":null,"cur":5},{"data":null,"cur":6},{"data":null,"cur":7},{"data":null,"cur":8},{"data":null,"cur":9},{"data":null,"cur":0}]
建立第一个元素
[{"data":null,"cur":2},{"data":1,"cur":0},{"data":null,"cur":3},{"data":null,"cur":4},{"data":null,"cur":5},{"data":null,"cur":6},{"data":null,"cur":7},{"data":null,"cur":8},{"data":null,"cur":9},{"data":null,"cur":1}]
建立第一个元素:1
在第一个元素前面插入一个数据
[{"data":null,"cur":3},{"data":1,"cur":0},{"data":2,"cur":1},{"data":null,"cur":4},{"data":null,"cur":5},{"data":null,"cur":6},{"data":null,"cur":7},{"data":null,"cur":8},{"data":null,"cur":9},{"data":null,"cur":2}]
在第一个元素前面插入一个数据:21
在第二个元素前面插入一个数据
[{"data":null,"cur":4},{"data":1,"cur":0},{"data":2,"cur":3},{"data":3,"cur":1},{"data":null,"cur":5},{"data":null,"cur":6},{"data":null,"cur":7},{"data":null,"cur":8},{"data":null,"cur":9},{"data":null,"cur":2}]
在第二个元素前面插入一个数据:231
删除第二个元素
[{"data":null,"cur":3},{"data":1,"cur":0},{"data":2,"cur":1},{"data":null,"cur":4},{"data":null,"cur":5},{"data":null,"cur":6},{"data":null,"cur":7},{"data":null,"cur":8},{"data":null,"cur":9},{"data":null,"cur":2}]
删除第二个元素:21
[Finished in 0.2s]