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

2019-11-19 14:50:30

字体：大中小

来源：转载

供稿：网友

数据结构系列前言：

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

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

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

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

下面是JS部分

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

方法	描述
append(element)	向链表尾部添加结点element
insert(position,element)	向位置position处插入结点element
removeAt(position)	按照索引值position删除结点
remove(element)	搜索并删除给定结点element
remove()	删除链表中最后一个结点
indexOf(element)	查找并返回给定结点element的索引值
isEmpty()	判断链表是否为空
size()	获取链表长度
toString()	转换为字符串输出
getHead()	获取头结点
getTail()	获取尾结点

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

单链表：

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;  };   }

使用方法：