一：线性表的定义
线性表是一种数结构；线性表有两种存储方式连续存储以及链表存储；其基本组成称为数据节点；
1：连续存储
当使用连续存储的时候系统会为线性表分配一个连续的存储空间；假设每一个节点平均长度为L；每个节点的首存储位置定义为每个节点的存储位置的时候，则 每个节点之间存在下列关系LOC(ai+1)=LOC(ai)+L；LOC(ai)=LOC(a1)+(L-1)*l.
ai称为a(i+1)的后继,a(i-1)称为ai的前驱。
2：链表实现
使用链表结构实现线性表。即每个节点包括数据部分以及指针部分。即每个数据节点的位置不一定是物理上的相连只需要逻辑上的相连即可即通过指针实现链表的串联
2-1：链表的分类
单向链表/循环链表/双向链表/静态链表
静态链表：就是用数组描述的链表。也就是数组中每一个下表都是一个“节”包含了数据与指向
循环链表：由于单链表的只会往后方传递，所以到达尾部的时候，要回溯到首部会非常麻烦，所以把尾部节的链与头连接起来形成循环
双向链表：针对单链表的优化，让每一个节都能知道前后是谁，所以除了后指针域还会存在一个前指针域，这样提高了查找的效率，不过带来了一些在设计上的复杂度，总体来说就是空间换时间了
二：具体单链表实现
1:最基本的单项链表实现
function list(){
var _this,prev=null;
return {
add:function(val){
prev={
data:val,
next:prev||null
}
}
var li=list();
list.add("mike");
list.add("alice");
list.add("jim");
通过node对象的next去直引用下一个node对象，初步是实现了通过链表的引用，这种链式思路jQuery的异步deferred中的then方法，还有日本的cho45的jsderferre中都有用到。这个实现上还有一个最关键的问题，我们怎么动态插入数据到执行的节之后？
2:查找当前节点
所以我们必须 要设计一个遍历的方法，用来搜索这个node链上的数据，然后找出这个对应的数据把新的节插入到当前的链中，并改写位置记录
var find=function findNode(cur){
return function(key){
while(cur.data!=key)
{
cur=cur.next;
}
return cur;
}
} (headNode);
3：将指定节点插入到指定节点之后
function node(data)
{
this.data=data;
this.next=null
}
var headNode=new node(data);
var findnode=function findnodecreate(cur){
return function(key){
while(cur.data!=key)
{
cur=cur.next;
}
return cur;
}
}
this.insert=function(data,key){
var node=new node(data);
var cur=findNode(key);
node.next=cur.next;
cur.next=node;
}
4:删除节点
由于链表的特殊性，我们a->b->c->d ，如果要删除c那么就必须修改b.next->c为 b.next->d，所以找到前一个节修改其链表next地址，这个有点像dom操作中removeChild找到其父节点调用移除子节点
同样的我们也在remove方法的设计中，需要设计一个遍历往上回溯一个父节点即可
var findPrevious=function(cur){
return function(key)
{
while(!(cur.next==null)&&cur.next.data!=key)
{
cur=cur.next;
}
}
}(headnode);
this.remove=function(key){
var pre=findPrevious(key)
if(pre.next!=null)
{
pre.next=pre.next.next;
}
}
三：双链表实现
insert的改变
this.insert=function(data,key)
{
var newNode = new createNode(data);
//在链条中找到对应的数据节
//然后把新加入的挂进去
var current = findNode(headNode,key);
//插入新的接，更改引用关系
newNode.next = current.next;
newNode.previous = current
current.next = newNode;
};
delete 的改变
this.remove = function(key) {
var currNode = findNode(headNode,key);
if (!(currNode.next == null)) {
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
网友评论