JavaScript数据结构之单链表和循环链表

数据结构系列前言：

数据结构作为程序员的基本知识，需要我们每个人牢牢掌握。近期我也展开了对数据结构的二次学习，来弥补当年挖的坑。。。。。。   当时上课的时候也就是跟着听课，没有亲自实现任何一种数据结构，更别提利用数据结构来解决问题了。  现在就来填坑了奋斗   在这里提醒看到我博客的孩子们，如果你还是在校生，永远不要轻视任何一门基础课的学习，这个时候挖的坑，要么需要用双倍的努力去填，要么会直接影响一个人的能力等等。。。。。。 千万别给自己挖坑

进入正题，关于链表的数据结构知识，这里简单介绍下：

链表是一种物理存储单元上非线性、非连续性的数据结构（它在数据逻辑上是线性的），它的每个节点由两个域组成：数据域和指针域。数据域中存储实际数据，指针域则存储着指针信息，指向链表中的下一个元素或者上一个元素。正是由于指针的存在，链表的存储在物理单元是非连续性的。

链表的优点和缺点同样明显。和线性表相比，链表在添加和删除节点上的效率更高，因为其只需要修改指针信息即可完成操作，而不像线性表（数组）那样需要移动元素。同样的，链表的长度在理论上也是无限的（在存储器容量范围内），并可以动态变化长度，相比线性表优势很大。 相应的，由于线性表无法随机访问节点，只能通过指针顺着链表进行遍历查询来访问，故其访问数据元素的效率比较低。

下面是JS部分

这里面封装了的常用方法及描述：

对于各常用方法的算法描述在这里就不写了，相信大家都可以轻易读懂并理解，毕竟都是非常基础的知识了。

单链表：

function LinkedList(){
 /*节点定义*/
 var Node = function(element){
  this.element = element; //存放节点内容
  this.next = null; //指针
 } 

 var length = 0, //存放链表长度
  head = null; //头指针 

 this.append = function(element){
  var node = new Node(element),
   current; //操作所用指针 

  if (!head){
   head = node;
  }else {
   current = head; 

   while(current.next){
    current = current.next;
   } 

   current.next = node;
  } 

  length++;
  return true;
 }; 

 this.insert = function(position, element){
  if (position >= 0 && position <= length) {
   var node = new Node(element),
    current = head,
    previous,
    index = 0; 

   if(position === 0){
    node.next = current;
    head = node;
   }else{
    while(index++ < position){
     previous = current;
     current = current.next;
    }
    node.next = current;
    previous.next = node;
   } 

   length++;
   return true;
  }else{
   return false;
  }
  }; 

 this.removeAt = function(position){
  if(position > -1 && position < length){
   var current = head,
    previous,
    index = 0; 

   if (position === 0) { 

    head = current.next; 

   }else{ 

    while (index++ < position){
     previous = current;
     current = current.next;
    } 

    previous.next = current.next;
   }; 

   length--;
   return current.element;
  }else{
   return null;
  }
 }; 

 this.remove = function(element){
  var current = head,
   previous; 

  if(element === current.element){
   head = current.next;
   length--;
   return true;
  }
  previous = current;
  current = current.next; 

  while(current){
   if(element === current.element){
    previous.next = current.next;
    length--;
    return true;
   }else{
    previous = current;
    current = current.next;
   }
  }
  return false;
 }; 

 this.remove = function(){
  if(length < 1){
   return false;
  } 

  var current = head,
  previous; 

  if(length == 1){
   head = null;
   length--;
   return current.element;
  } 

  while(current.next !== null){
   previous = current;
   current = current.next;
  } 

  previous.next = null;
  length--;
  return current.element;
 }; 

 this.indexOf = function(element){
  var current = head,
   index = 0; 

  while(current){
   if(element === current.element){
    return index;
   }
   index++;
   current = current.next;
  } 

  return false;
 }; 

 this.isEmpty = function(){
  return length === 0;
 }; 

 this.size = function(){
  return length;
 }; 

 this.toString = function(){
  var current = head,
   string = ''; 

  while(current){
   string += current.element;
   current = current.next;
  }
  return string;
 };  

 this.getHead = function(){
  return head;
 } 

}

循环链表：在单链表的基础上，将尾节点的指针指向头结点，就构成了一个循环链表。环形链表从任意一个节点开始，都可以遍历整个链表。

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

 var length = 0,
  head = null; 

 this.append = function(element){
  var node = new Node(element),
   current; 

  if (!head) {
   head = node;
   node.next = head;
  }else{
   current = head; 

   while(current.next !== head){
    current = current.next;
   } 

   current.next = node;
   node.next = head;
  }; 

  length++;
  return true;
 }; 

 this.insert = function(position, element){
  if(position > -1 && position < length){
   var node = new Node(element),
    index = 0,
    current = head,
    previous; 

   if (position === 0) { 

    node.next = head;
    head = node; 

   }else{ 

    while(index++ < position){
     previous = current;
     current = current.next;
    } 

    previous.next = node;
    node.next = current; 

   }; 

   length++;
   return true;
  }else{
   return false;
  }
 }; 

 this.removeAt = function(position){
  if(position > -1 && position < length){
   var current = head,
    previous,
    index = 0; 

   if (position === 0) { 

    head = current.next; 

   }else{ 

    while (index++ < position){
     previous = current;
     current = current.next;
    } 

    previous.next = current.next;
   }; 

   length--;
   return current.element;
  }else{
   return null;
  }
 }; 

 this.remove = function (element){
  var current = head,
   previous,
   indexCheck = 0; 

  while(current && indexCheck < length){
   if(current.element === element){
    if(indexCheck == 0){
     head = current.next;
     length--;
     return true;
    }else{
     previous.next = current.next;
     length--;
     return true;
    }
   }else{
    previous = current;
    current = current.next;
    indexCheck++;
   }
  }
  return false;
 }; 

 this.remove = function(){
  if(length === 0){
   return false;
  } 

  var current = head,
   previous,
   indexCheck = 0; 

  if(length === 1){
   head = null;
   length--;
   return current.element;
  } 

  while(indexCheck++ < length){
   previous = current;
   current = current.next;
  }
  previous.next = head;
  length--;
  return current.element;
 }; 

 this.indexOf = function(element){
  var current = head,
   index = 0; 

  while(current && index < length){
   if(current.element === element){
    return index;
   }else{
    index++;
    current = current.next;
   }
  }
  return false;
 }; 

 this.isEmpty = function(){
  return length === 0;
 }; 

 this.size = function(){
  return length;
 }; 

 this.toString = function(){
  var current = head,
   string = '',
   indexCheck = 0; 

  while(current && indexCheck < length){
   string += current.element;
   current = current.next;
   indexCheck++;
  } 

  return string;
 };  

}

使用方法：

在类外部扩充方法：

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。