缘起

最近工作上需要依照现有数据生成嵌套json对象形式的组织机构列表，一时觉得无从下手，请教同事大神才知道此乃数据结构相关知识，遂恶补相关基础并在此记录。

数据结构可以分为：1、列表；2、线性；3、树形；4、图 四种基本结构。何为数据结构？我理解就是数据的结构。。。即承载数据的形式。数据结构中的线性结构有数组和链表，本文即对链表进行简单总结，在后续文章中会实现几种基本的数据结构。

链表

1 链表是什么

2 用链表实现数组和其基本操作，以下附上代码

function ARRAY(){  var INDEX=-1;  var HEAD=null;  var OBJ=null;  //添加元素  this.add=function(e){    function Element(value){      this.value=value;    }    e=new Element(e);    if(INDEX==-1){      OBJ=e;      HEAD=e;      INDEX++;    }else{      INDEX++;      OBJ.next=e;      OBJ=OBJ.next;    }    return HEAD;  }  //删除最后一个元素  this.deleteLast=function(){    for(var i=HEAD;i!=undefined;i=i.next){      if(i.next.next==undefined){        i.next=null;      }    }    return HEAD;  }  //按序号取元素  this.get=function(Inx){    var index=0;    for(var i=HEAD;i!=undefined;i=i.next){      index++;      if(index==Inx){        return i;      }    }  }  //按位置插入元素  this.insert=function(Inx,e){    function Element(value){      this.value=value;    }    e=new Element(e);    if(Inx==0){      e.next=HEAD;      HEAD=e;    }else{      var currentItem=this.get(Inx);      var sufItem=this.get(Inx+1);      e.next=sufItem;      currentItem.next=e;    }    return HEAD;  }  //删除特定位置元素  this.deleteElement=function(Inx){    if(Inx==0){      var sufItem=this.get(Inx+1);      HEAD=sufItem;    }else{      var preItem=this.get(Inx-1);      var sufItem=this.get(Inx+1);      preItem.next=sufItem;      }    return HEAD;  }}

同时提供两种遍历链表的方法

//遍历链表（递归）function loop(head){  if(head.next==undefined){    return;  }  return loop(head.next);}

//遍历链表（非递归）function loopLinkedList(head){  for(var i=head;i!=undefined;i=i.next){    console.log(i);  }}

具体使用方法

var obj = new ARRAY();console.time('addtest');obj.add('aaa');obj.add('bbb');obj.add('ccc');obj.add('ddd');var head=obj.add('eee');console.log(head);console.timeEnd('addtest');