欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法-单向链表(js实现)

程序员文章站 2024-01-23 21:16:22
...

  链表有单向链表、双向链表和循环链表,此篇文章只讲解单向链表,另外两种会在下一篇文章中补充,要真正理解和使用链表的话,建议三种链表结构都了解一下。

  平时我们使用最多的数据结构应该是数组,很多东西都可以用数组来轻松实现,但在某些编程语言中,数组的长度是预先设定好的,想要额外添加元素或者删除元素是一件比较困难的事。那么使用链表的话恰恰就解决了这些问题,对于链表来说删除或添加一个元素是非常方便的,除了数据的随机访问(可以实现但是比较麻烦,比如可以通过添加和操作索引值来实现),它几乎可以用在任何可以使用一维数组的情况中。

链表的定义

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

个节点的引用叫做链。

  一般的链表都会额外添加一个头节点(作为辅助)和尾节点,例如下面这种样子数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript

  数组元素靠它们的位置进行引用,链表元素则是靠相互之间的关系进行引用。在上图中,我们说 bread 跟在 milk 后面,而不说 bread 是链表中的第二个元素。遍历链表,就是跟着链接,从链表的首元素一直走到尾元(但这不包含链表的头节点,头节点常常用来作为链表的接入点)。上图中另外一个值得注意的地方是,链表的尾元素指向一个 null 节点。

  插入新元素:

数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript

  向单向链表中插入一个节点,只需要修改它前面的节点(前驱),使其指向新加入的节点,而新加入的节点则指向原来前驱指向的节点。上图演示了如何在 eggs 后加入 cookies。

  删除链表中已有元素:

数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript

  从链表中删除一个元素也很简单。只需要将待删除元素的前驱节点指向待删除元素的后继节点。上图展示了从单向链表中删除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*/
  • 数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript
  • 大小: 24.8 KB
  • 数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript
  • 大小: 38.2 KB
  • 数据结构与算法-单向链表(js实现)
            
    
    博客分类: 数据结构与算法学习笔记 数据结构算法javascript
  • 大小: 30.6 KB