数据结构与算法-单向链表(js实现)
链表有单向链表、双向链表和循环链表,此篇文章只讲解单向链表,另外两种会在下一篇文章中补充,要真正理解和使用链表的话,建议三种链表结构都了解一下。
平时我们使用最多的数据结构应该是数组,很多东西都可以用数组来轻松实现,但在某些编程语言中,数组的长度是预先设定好的,想要额外添加元素或者删除元素是一件比较困难的事。那么使用链表的话恰恰就解决了这些问题,对于链表来说删除或添加一个元素是非常方便的,除了数据的随机访问(可以实现但是比较麻烦,比如可以通过添加和操作索引值来实现),它几乎可以用在任何可以使用一维数组的情况中。
链表的定义
链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一
个节点的引用叫做链。
一般的链表都会额外添加一个头节点(作为辅助)和尾节点,例如下面这种样子
数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在上图中,我们说 bread 跟在 milk 后面,而不说 bread 是链表中的第二个元素。遍历链表,就是跟着链接,从链表的首元素一直走到尾元(但这不包含链表的头节点,头节点常常用来作为链表的接入点)。上图中另外一个值得注意的地方是,链表的尾元素指向一个 null 节点。
插入新元素:
向单向链表中插入一个节点,只需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点。上图演示了如何在 eggs 后加入 cookies。
删除链表中已有元素:
从链表中删除一个元素也很简单。只需要将待删除元素的前驱节点指向待删除元素的后继节点。上图展示了从单向链表中删除Bacon。
除了插入和删除,链表还有其他一些操作,后面将给出讲解。
设计一个基于对象的链表
我们需要设计两个类,Node 类用来表示节点, LinkedList 类提供插入节点、删除节点、显示列表元素的方法,以及其他一些辅助方法。
Node类:
function Node(element) { this.element = element;//当前节点的数据 this.next = null;//下一个节点数据 }
LinkedList 类:
function LList() { this.head = new Node("head");//头节点 } LList.prototype={ //查找某一节点 find:function (item) { var currNode = this.head; while (currNode.element != item) { currNode = currNode.next; } return currNode; }, //向某一元素后面插入新节点 insert:function(newElement,item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; }, //查找某一节点的前一个节点(前驱) findPrevious:function(item){ var currNode = this.head; while (!(currNode.next == null) &&(currNode.next.element != item)) { currNode = currNode.next; } return currNode; }, //删除某一个节点 remove:function(item){ var prevNode = this.findPrevious(item); if (!(prevNode.next == null)) { prevNode.next = prevNode.next.next; } }, //修改某一节点的数据 edit:function(item,newItem){ var element=this.find(item); element.element=newItem; }, //在控制台打印出所有节点(为了方便预览) display:function(){ var currNode = this.head; while (!(currNode.next == null)) { console.log(currNode.next.element); currNode = currNode.next; } } }
测试:
var names = new LList(); names.insert("likek", "head");//往头节点后插入节点likek names.insert("zhangsan", "likek");//往likek后插入节点zhangsan names.insert("lisi", "zhangsan");//往zhangsan后插入节点lisi names.insert("wangwu", "lisi");//往lisi后插入节点wangwu names.display(); /*likek zhangsan lisi wangwu*/ names.remove("zhangsan");//删除zhangsan节点 names.display(); /*likek lisi wangwu*/ names.edit("lisi","wangnima");//将lisi节点改为wangnima names.display(); /*likek wangnima wangwu*/