js中模拟链表详解编程语言

js中数组的主要问题是，它们被实现成了对象，与其他语言的数组相比，效率很低。如果发现数组在实际使用时很慢，就可以考虑使用链表来代替它。

   function Node(element){ 
      //element属性保存任何传入的数据 
      this.element = element; 
      this.next = null; 
   } 
   function LinkedList(){ 
      this.head = new Node('head'); 
      this.find = find; 
      this.insert = insert; 
      this.remove = remove; 
      this.display = display; 
      this.findPrevious = findPrevious; 
   }

方法实现

find方法演示了如何在链表上移动，首先，创建一个变量保存head节点的引用，通过循环不断向后搜索，如果没有发现目标节点，则将变量重新赋值为下一个节点引用

   function find(item){ 
       //用变量current来保存head节点的引用 
       var currentNode = this.head; 
       while(current.element != item){ 
           if(currentNode == null) return null; 
           //将变量重新赋值为当前节点的下一个节点 
           currentNode = currentNode.next; 
       }  
       return currentNode; 
   }

insert方法通过find方法来定位插入位置，然后通过操作next进行插入

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

display方法用来展示链表中的元素

   function display(){ 
       var currentNode = this.head; 
       while(!currentNode == null){ 
          print(currentNode.next.element) 
          currentNode = currentNode.next; 
       } 
   }

在链表中删除节点需要找到待删除节点的上一个节点，定义findPrevious方法来实现remove方法

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

双向链表

尽管从链表头节点遍历到尾节点很简单，但反过来遍历就比较麻烦，可以给Node对象增加一个属性，该属性指向前驱节点的链接。首先要为Node类增加一个previous属性

   function Node(element){ 
      this.element = element; 
      this.next = next; 
      this.previous = null; 
   } 
   function insert(item){ 
      var newNode = new Node(element); 
      var current = this.find(item); 
      current.next = newNode; 
      newNode.previous = current; 
   }

这里修改了remove方法，其他方法也要相应修改