首页 > 编程语言 > 详细

数据结构链表——JavaScript的实现

时间:2017-10-13 15:52:09      阅读:244      评论:0      收藏:0      [点我收藏+]

链表的概念

  链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量,以head表示,它存放一个地址,指向一个元素。每个结点都使用一个对象的引用指标它的后继,指向另一个结点的引用叫做链。

  技术分享

 

  数组元素依靠下标(位置)来进行引用,而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高,下图演示了链表结点d的插入过程:  

技术分享

  删除过程:

技术分享

  基于对象的链表

  我们定义2个类,Node类与LinkedList类,Node为结点数据,LinkedList保存操作链表的方法。

  首先看Node类:

function Node(element){
    this.element = element;
    this.next = null;
}

element用来保存结点上的数据,next用来保存指向一下结点的的链接。  

LinkedList类:

  

function LinkedList(){
         this.head = new Node(‘head‘);
         this.find = find;
         this.insert = insert;
         this.remove = remove;
         this.show = show;
         this.frontNode = frontNode;//修改的地方
}

 

   find()方法,从头结点开始,沿着链表结点一直查找,直到找到与item内容相等的element则返回该结点,没找到则返回空。

function find(item){
         var currentNode = this.head;//从头结点开始
         while(currentNode.element!=item){
                  currentNode =  currentNode.next;
         }
         return currentNode;//找到返回结点数据,没找到返回null
}

  Insert方法。通过前面元素插入的演示可以看出,实现插入简单四步:

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

function insert(newElement,item){
      var newNode = new Node(newElement);
      var currentNode = this.find(item);
      newNode.next = currentNode.next;
      currentNode.next = newNode;
}

  Remove()方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法frontNode():

function frontNode(item){
    var currentNode = this.head;
    while(currentNode.next.element!=item&&currentNode.next!=null){
                  currentNode = currentNode.next;
        }      
       return currentNode;
}

 简答三步:

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

function remove(item){
          var frontNode = this.frontNode(item);
          //console.log(frontNode.element);
          frontNode.next = frontNode.next.next;
}

  Show()方法:  

function show(){
         var currentNode = this.head
         var result = ‘‘;//修改
         while(currentNode.next!=null){
                  result += currentNode.next.element;//为了不显示head结点
                  currentNode = currentNode.next;
         }
         return result;//修改
}

  测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

  输出:
技术分享

 

双向链表

  从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

 技术分享

  首先我们先给Node类增加front属性:  

function Node(element){
    this.element = element;
    this.next = null;
    this.front = null;
}

LinkedList类:

function LinkedList(){
         this.head = new Node(‘head‘);
         this.find = find;
         this.insert = insert;
         this.remove = remove;
         this.show = show;
         this.frontNode = frontNode;
         this.showReverse = showReverse;
         this.findLast = findLast;
} 

当然,对应的insert()方法和remove()方法我们也需要做相应的修改:

function insert(newElement,item){//修改的前插操作
    var newNode = new Node(newElement);
    var currentNode = this.frontNode(item);
    newNode.next = currentNode.next;
    newNode.front = currentNode;//增加front指向前驱结点
    currentNode.next.front = newNode;//添加的
    currentNode.next = newNode;
}

function remove(item){   
    var currentNode = this.find(item);//找到需要删除的节点
    if (currentNode.next != null) {
        currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
        currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
        currentNode.next = null;//并设置前驱与后继的指向为空
        currentNode.front = null;       
    }    
}

  反序显示链表: 

  需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。

function findLast() {//查找链表的最后一个节点
    var currentNode = this.head;
    while (currentNode.next != null) {
        currentNode = currentNode.next;
    }
    return currentNode;
}

  实现反序输出:

function showReverse() {
    var currentNode = this.head, result = "";
    currentNode = this.findLast();  
    while(currentNode.front!=null){
        result += currentNode.element + " ";
        currentNode = currentNode.front;
    }
    return result;
}

测试程序:  

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());

输出:

技术分享

循环链表

 

  循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:

1 head.next = head

  这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表:

  技术分享

  

  修改构造方法:

function LinkedList(){
         this.head = new Node(‘head‘);
         this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
         this.find = find;
         this.insert = insert;
         this.remove = remove;
         this.show = show;
         this.frontNode = frontNode;
         this.showReverse = showReverse;
         this.findLast = findLast;
}

  这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
         var currentNode = this.head;//从头结点开始
         while(currentNode.element!=item&&currentNode.next.element!=‘head‘){
                  currentNode =  currentNode.next;
         }
         return currentNode;//找到返回结点数据,没找到返回null
}

function show(){
         var currentNode = this.head
         var result = ‘‘;
         while(currentNode.next != null && currentNode.next.element != "head"){
                  result += currentNode.next.element;//为了不显示head结点
                  currentNode = currentNode.next;
         }
         return result;//修改
}

  测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());

  测试结果:

技术分享

 

  本文为博主修改文章,转自: http://www.cnblogs.com/qq503665965/

数据结构链表——JavaScript的实现

原文:http://www.cnblogs.com/hitwgs/p/7661397.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!