单向链表的结构与队列相似，都是头指针指向第一个放入的节点，尾指针指向最后一个节点，但单向链表是不遵循先进先出的原则的，它可以随机获取，随机添加。
单向链表
用js写一个单向链表并写出它的随机获取与随机添加：
先创建一个节点：
function Node(value){
this.value = value;
this.next= null;//用于前一节点指向后一节点
}
接下来开始写单向链表：
function ChainTable(){
this.head = null;//头指针
this.tail = null;//尾指针
this.iter = null;//循环器
this.add=function(value){ //按照前后顺序加入节点
node = new Node(value);
if(this.head != null){
this.tail.next = node;// 将尾指针的next指向新加入的节点 也就将倒数第二的next指向新加入的这个节点
this.tail = node;//将尾指针指向最后一个节点
}else{//如果this.head为null 那证明还没有加入过节点 将 头指针和尾指针都指向这个新加入的节点即可
this.head = node;
this.tail = node;
}
this.iterator = function(){
this.iter = this.head;
}
this.next = function(){ //按照先进先出的顺序取出 但不弹出
if(this.iter!=null){
node = this.iter;
this.iter = node.next;
return node;
}else{
return null;
}
}
this.get = function(index){ // 随机获取单个
point = this.head;
for(var i=0;i<index;i++){//获取第几个就循环几减一次
point = point.next; //每循环一次 就指向下一个节点
if(point == null){ //如果point为null 那就证明想得到的节点 根本不存在 所请求的次数超出了节点的总数
break;
}
}
return point;
}
this.insert = function(index,value){ // 随机插入一个节点 输入位置 和 插入节点的内容
node = new Node(value);
// -------------- 找到要插入的位置的前一个节点-----------
let ii= index -1;
if(ii!=-1){ //先判断是不是第一个节点
preNode = this.get(ii); //用随即获取 得到 插入位置的前一个节点
node.next = preNode.next;//将新插入节点的指针指向原本在这个位置的节点
preNode.next = node;//将上一个节点的指针指向新插入的节点
if(node.next == null){ //如果node加在最后一个那么node.next指向的就是null 把尾指针给node
this.tail = node;
}
}else{//如果要插入的位置 是第一个位置 那么 将新插入的节点的指针指向头指针指向的节点也就是原来的第一个节点 然后把头指针指向这个新加入的节点 让这个节点变成第一个节点
node.next = this.head;
this.head = node;
}
}
this.remove = function(index){ //随机删除一个
let ii = index -1;
if(ii != -1){//先判断是不是第一个节点
let preNode = this.get(ii);//获取到要删除的节点的前一个节点
if(preNode.next != null){ // 如果要删除的节点是存在的 那么 要删除的节点的前一个节点的下一个节点是肯定存在的 这个不需要多解释吧
preNode.next = preNode.next.next;
if(preNode.next == null){ //preNode.next 指向 preNode.next.next 之后 如果变成了null 那就证明 这个节点是最后一个节点 那么 把尾指针 指向原本最后一个节点的前一个节点就ok了
this.tail = preNode;
}
}
}else{//如果是第一个节点
this.head = this.head.next;
}
}
}
网友评论