Rumah > hujung hadapan web > tutorial js > JavaScript数据结构之链表的实现方法介绍(图文)

JavaScript数据结构之链表的实现方法介绍(图文)

黄舟
Lepaskan: 2017-03-20 14:24:57
asal
1764 orang telah melayarinya

链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。本文主要介绍JavaScript数据结构中链表的实现,具有很好的参考价值。下面跟着小编一起来看下吧

前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素。如果你在使用数组的时候发现很慢,就可以考虑使用链表。

链表的概念

链表是一种常见的数据结构。它是动态地进行存储分配的一种结构。链表有一个“头指针”变量,以head表示,它存放一个地址,指向一个元素。每个结点都使用一个对象引用指标它的后继,指向另一个结点的引用叫做链。

数组元素依靠下标(位置)来进行引用,而链表元素则是靠相互之间的关系来进行引用。因此链表的插入效率很高,下图演示了链表结点d的插入过程: 

 

删除过程:

基于对象的链表

我们定义2个类,Node类与LinkedList类,Node为结点数据,LinkedList保存操作链表的方法。

首先看Node类:  

function Node(element){
  this.element = element;
   this.next = null;
 }
Salin selepas log masuk

element用来保存结点上的数据,next用来保存指向一下结点的的链接。  

LinkedList类:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}
Salin selepas log masuk

find()方法,从头结点开始,沿着链表结点一直查找,直到找到与item内容相等的element则返回该结点,没找到则返回空。

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据,没找到返回null
}
Salin selepas log masuk

Insert方法。通过前面元素插入的演示可以看出,实现插入简单四步:

1、创建结点

2、找到目标结点

3、修改目标结点的next指向链接

4、将目标结点的next值赋值给要插入的结点的next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }
Salin selepas log masuk

Remove()方法。删除某一节点需要先找到被删除结点的前结点,为此我们定义方法frontNode():

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}
Salin selepas log masuk

简答三步:

1、创建结点

2、找到目标结点的前结点

3、修改前结点的next指向被删除结点的n后一个结点

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }
Salin selepas log masuk

Show()方法:

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}
Salin selepas log masuk

测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());
Salin selepas log masuk
Salin selepas log masuk

输出:

双向链表

从链表的头节点遍历到尾节点很简单,但有的时候,我们需要从后向前遍。此时我们可以通过给 Node 对象增加一个属性,该属性存储指向前驱节点的链接。楼主用下图来双向链表的工作原理。

首先我们先给Node类增加front属性:  

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }
Salin selepas log masuk

当然,对应的insert()方法和remove()方法我们也需要做相应的修改: 

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}
Salin selepas log masuk

反序显示链表:

需要给双向链表增加一个方法,用来查找最后的节点。 findLast() 方法找出了链表中的最后一个节点,可以免除从前往后遍历链。

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}
Salin selepas log masuk

实现反序输出:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}
Salin selepas log masuk

测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());
Salin selepas log masuk

输出:

循环链表

循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。循环链表和单向链表相似,节点类型都是一样的。唯一的区别是,在创建循环链表时,让其头节点的 next 属性指向它本身,即:

head.next = head

这种行为会传导至链表中的每个节点,使得每个节点的 next 属性都指向链表的头节点。楼主用下图来表示循环链表:

修改构造方法

function LinkedList(){
  this.head = new Node('head');//初始化
  this.head.next = this.head;//直接将头节点的next指向头节点形成循环链表
  this.find = find;
  this.frontNode = frontNode;
  this.insert = insert;
  this.remove = remove;
  this.show = show; 
}
Salin selepas log masuk

这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据,没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}
Salin selepas log masuk

测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());
Salin selepas log masuk
Salin selepas log masuk

测试结果:

Atas ialah kandungan terperinci JavaScript数据结构之链表的实现方法介绍(图文). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan