js实现链表

链表

数组不总是组织数据的最佳数据结构，原因如下。在很多编程语言中，数组的长度是固定
的，所以当数组已被数据填满时，再要加入新的元素就会非常困难。在数组中，添加和删
除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了
添加或删除操作。然而，JavaScript 的数组并不存在上述问题，因为使用 split() 方法不需
要再访问数组中的其他元素了^- 。
JavaScript 中数组的主要问题是，它们被实现成了对象，与其他语言（比如 C++ 和 Java）
的数组相比，效率很低

链表是由一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。

Node类：用来表示节点
linkedList：提供插入、删除、显示元素的方法，以及一些其他方法

Node类：包含两个属性：
element：当前数据
next：用来指向下个节点的链接

单链表的实现

var Node = function(element){this.element = element;this.next = null;
}	var linkedList = function(){this.head = new Node('head');
}
var linkedList.prototype = {//查找一个元素find:function(item){//遍历整个链表，获取头节点var currentNode = this.head;while(currentNode.element != item && currentNode.next != null){currentNode = currentNode.next;}return currentNode;}//查找一个元素的前一个元素findPrevious:function(item){var currentNode = this.head;while(currentNode.next.element != item && currentNode.next!=null){currentNode = current.next;}return curretnNode;}//添加一个元素//element要插入的元素//item 要插入在什么元素的后面//需要找到前一个元素，并且判断前一个元素是否为空  //需要一个辅助函数findinsert:function(element,item){var nowNode = new Node(element);var currentNode = this.find(item);nowNode.next = currentNode.next;currentNode.next = nowNode;}//删除一个元素remove:function(item){var preNode =this.findPrevious(item);if(preNode!=null){preNode.next = preNode.next.next;}		}//显示链表的元素display:function(){var str = '';var currentNode = this.head;while(currentNode.next != null){str+=currentNode.next.element;currentNode = currentNode.next;}return str;}
}

双向链表的实现
通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接。此时向链表插入一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。

删除节点： 首先需要在链表中找出存储待删除数据的节点，然后设置该节点前驱的 next 属性，使其指向待删除节点的后继；设置该节点后继的 previous 属性，使其指向待删除节点的前驱。

var Node = function (element) {this.next = null;this.element = element;this.previous = null;
}var linkedList = function () {this.head = new Node('head');
}linkedList.prototype = {//查找当前节点的父节点find: function (item) {var currentNode = this.head;while (currentNode.element != item) {currentNode = currentNode.next;}return currentNode;},//返回最后一个节点findLast: function () {var currentNode = this.head;while (currentNode.next != null) {currentNode = currentNode.next;}return currentNode;},//添加一个元素insert: function (element, item) {var nowNode = new Node(element);var currentNode = this.find(item);        nowNode.next = currentNode.next;nowNode.previous = currentNode; currentNode.next = nowNode;               },//删除一个元素remove: function (item) {var currentNode = this.find(item);if (currentNode.next != null) {currentNode.next.previous = currentNode.previous;currentNode.previous.next = currentNode.nextcurrentNode.next = null;currentNode.previous = null;}},//展示整个列表display: function () {var curNode = this.head;var curStr = ''while (curNode.next != null) {curStr += curNode.next.element;curNode = curNode.next;}return curStr;},//反向展示displayReverse: function () {var endNode = this.findLast();var endStr = '';while (endNode.previous != null) {endStr += endNode.element;endNode = endNode.previous;}return endStr;}
}

循环链表

如果你希望可以从后向前遍历链表，但是又不想付出额外代价来创建一个双向链表，那么
就需要使用循环链表。从循环链表的尾节点向后移动，就等于从后向前遍历链表。
创建循环链表，只需要修改 linkedList 类的原型函数：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！