JavaScript双向链表和双向循环链表的实现-js教程-PHP中文网

首页

web前端

js教程

JavaScript双向链表和双向循环链表的实现

小云云

Dec 07, 2017 pm 03:51 PM

javascript js 实现

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。本文主要介绍JavaScript数据结构之双向链表和双向循环链表的实现。

双向链表：单向链表只能向着一个方向遍历链表节点，而在节点指针域中增加了前向指针的双向链表，则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。

function DoublyLinkedList() { 
  var Node = function(element) { 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = Node(element), 
      current, 
      previous; 
     
    if(!head){ 
      head = node; 
      tail = node; 
    }else{ 
      current = head; 
      while(current){ 
        previous = current; 
        current = current.next; 
      } 
 
      node.next = current; 
      current.prev = node; 
      previous.next = node; 
      node.prev = previous; 
    } 
 
    length++; 
    return true; 
  } 
 
  this.insert = function(position,element){ 
    if(position > -1 && position < length){ 
      var node = new Node(element), 
        current = head, 
        previous, 
        index = 0; 
 
      if(position === 0){ 
 
        if(!head){ 
          head = node; 
          tail = node; 
        }else{ 
          node.next = current; 
          current.prev = node; 
          head = node; 
        } 
 
      }else if (position === length -1){ 
        current = tail; 
        current.next = node; 
        node.prev = current; 
      }else { 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
        node.next = current; 
        previous.next = node; 
        current.prev = node; 
        node.prev = previous; 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
      var current = head, 
        index = 0, 
        previous; 
 
      if (position === 0) { 
        head = current.next; 
 
        if(length === 1){ 
          tail = null; 
        }else{ 
          head.prev = null; 
        } 
      }else if(position === length - 1){ 
        current = tail; 
        tail = current.prev; 
        tail.next = null; 
      } else{ 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
      }; 
      length-- ; 
 
      return current.element; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous; 
 
    if(current.element === element){ 
      head = current.next; 
    } 
    previous = current; 
    current = current.next; 
 
    while(current){ 
      if (current.element = element) { 
        previous.next = current.next; 
        current.next.prev = previous; 
      }else{ 
        previous = current; 
        current = current.next; 
      } 
    } 
    return false; 
  }; 
 
  this.remove = function(){ 
    if (length === 0) { 
      return false; 
    }; 
 
    var current = head, 
      previous; 
 
    if(length === 1){ 
      head = null; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(current){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = null; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if (current.element === element) { 
        return index; 
      }; 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      string = &#39;&#39;; 
 
    while(current){ 
      string += current.element; 
      current = current.next; 
    } 
    return string; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
}

登录后复制

双向循环链表：将双向链表的头尾指针相连，就构成了双向循环链表。这种链表从任意一个节点都可以同时向两个方向进行节点遍历，查询节点的速度也是最快的。

/*双向循环链表*/ 
function DoublyCircularLinkedList(){ 
  var Node = function(element){ 
    this.element = element; 
    this.next = null; 
    this.prev = null; 
  }; 
 
  var length = 0, 
    head = null, 
    tail = null; 
 
  this.append = function(element){ 
    var node = new Node(element), 
      current, 
      previous; 
 
    if (!head) { 
      head = node; 
      tail = node; 
      head.prev = tail; 
      tail.next = head; 
    }else{ 
      current = head; 
 
      while(current.next !== head){ 
        previous = current; 
        current = current.next; 
      } 
 
      current.next = node; 
      node.next = head; 
      node.prev = current; 
    }; 
 
    length++; 
    return true; 
  }; 
 
  this.insert = function(position, element){ 
    if(position >= 0 && position <= length){ 
      var node = new Node(element), 
        index = 0, 
        current = head, 
          previous; 
 
      if(position === 0){ 
         
        if(!head){ 
 
          node.next = node; 
          node.tail = node; 
          head = node; 
          tail = node; 
 
        }else{ 
 
          current.prev = node; 
          node.next = current; 
          head = node; 
          node.prev = tail; 
 
        } 
         
      }else if(position === length){ 
        current = tail; 
 
        current.next = node; 
        node.prev = current; 
        tail = node; 
        node.next = head; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        current.prev = node; 
        node.next = current; 
        previous.next = node; 
        node.prev = previous; 
 
      } 
 
      length++; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.removeAt = function(position){ 
    if(position > -1 && position < length){ 
 
      var current = head, 
        index = 0, 
        previous; 
 
      if(position === 0){ 
 
        current.next.previous = tail; 
        head = current.next; 
 
      }else if(position === length - 1){ 
 
        current = tail; 
 
        current.prev.next = head; 
        head.prev = current.prev; 
        tail = current.prev; 
      }else{ 
 
        while(index++ < position){ 
          previous = current; 
          current = current.next; 
        } 
 
        previous.next = current.next; 
        current.next.prev = previous; 
 
      } 
 
      length--; 
      return true; 
    }else{ 
      return false; 
    } 
  }; 
 
  this.remove = function(element){ 
    var current = head, 
      previous, 
      indexCheck = 0; 
 
    while(current && indexCheck < length){ 
      if(current.element === element){ 
        if(indexCheck === 0){ 
          current.next.prev = tail; 
          head = current.next; 
        }else{ 
          current.next.prev = previous; 
          previous.next = current.next; 
        } 
        length--; 
        return true; 
      } 
 
      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; 
      tail = null; 
      length--; 
      return current.element; 
    } 
 
    while(indexCheck++ < length){ 
      previous = current; 
      current = current.next; 
    } 
 
    previous.next = head; 
    tail = previous.next; 
    length--; 
    return current.element; 
  }; 
 
  this.indexOf = function(element){ 
    var current = head, 
      index = 0; 
 
    while(current && index++ < length){ 
      if(current.element === element){ 
        return index; 
      } 
      current = current.next; 
    } 
 
    return false; 
  }; 
 
  this.toString = function(){ 
    var current = head, 
      indexCheck = 0, 
      string = &#39;&#39;; 
 
    while(current && indexCheck < length){ 
      string += current.element; 
      indexCheck++; 
      current = current.next; 
    }   
 
    return string; 
  }; 
 
  this.isEmpty = function(){ 
    return length === 0; 
  }; 
 
  this.getHead = function(){ 
    return head; 
  }; 
 
  this.getTail = function(){ 
    return tail; 
  }; 
 
  this.size = function(){ 
    return length; 
  }; 
}

登录后复制

热AI工具

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

免费脱衣服图片

Clothoff.io

AI脱衣机

AI Hentai Generator

免费生成ai无尽的。

显示更多

热工具

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里

7530

CakePHP 教程

1378

steam的账户名称是什么格式

win11激活密钥永久

NYT连接提示和答案

显示更多

Related knowledge

华为手机如何实现双微信登录？ Mar 24, 2024 am 11:27 AM

华为手机如何实现双微信登录？随着社交媒体的兴起，微信已经成为人们日常生活中不可或缺的沟通工具之一。然而，许多人可能会遇到一个问题：在同一部手机上同时登录多个微信账号。对于华为手机用户来说，实现双微信登录并不困难，本文将介绍华为手机如何实现双微信登录的方法。首先，华为手机自带的EMUI系统提供了一个很便利的功能——应用双开。通过应用双开功能，用户可以在手机上同

推荐：优秀JS开源人脸检测识别项目 Apr 03, 2024 am 11:55 AM

人脸检测识别技术已经是一个比较成熟且应用广泛的技术。而目前最为广泛的互联网应用语言非JS莫属，在Web前端实现人脸检测识别相比后端的人脸识别有优势也有弱势。优势包括减少网络交互、实时识别，大大缩短了用户等待时间，提高了用户体验；弱势是：受到模型大小限制，其中准确率也有限。如何在web端使用js实现人脸检测呢？为了实现Web端人脸识别，需要熟悉相关的编程语言和技术，如JavaScript、HTML、CSS、WebRTC等。同时还需要掌握相关的计算机视觉和人工智能技术。值得注意的是，由于Web端的计

PHP编程指南：实现斐波那契数列的方法 Mar 20, 2024 pm 04:54 PM

编程语言PHP是一种用于Web开发的强大工具，能够支持多种不同的编程逻辑和算法。其中，实现斐波那契数列是一个常见且经典的编程问题。在这篇文章中，将介绍如何使用PHP编程语言来实现斐波那契数列的方法，并附上具体的代码示例。斐波那契数列是一个数学上的序列，其定义如下：数列的第一个和第二个元素为1，从第三个元素开始，每个元素的值等于前两个元素的和。数列的前几个元

如何在华为手机上实现微信分身功能 Mar 24, 2024 pm 06:03 PM

如何在华为手机上实现微信分身功能随着社交软件的普及和人们对隐私安全的日益重视，微信分身功能逐渐成为人们关注的焦点。微信分身功能可以帮助用户在同一台手机上同时登录多个微信账号，方便管理和使用。在华为手机上实现微信分身功能并不困难，只需要按照以下步骤操作即可。第一步：确保手机系统版本和微信版本符合要求首先，确保你的华为手机系统版本已更新到最新版本，以及微信App

掌握Golang如何实现游戏开发的可能性 Mar 16, 2024 pm 12:57 PM

在当今的软件开发领域中，Golang（Go语言）作为一种高效、简洁、并发性强的编程语言，越来越受到开发者的青睐。其丰富的标准库和高效的并发特性使它成为游戏开发领域的一个备受关注的选择。本文将探讨如何利用Golang来实现游戏开发，并通过具体的代码示例来展示其强大的可能性。1.Golang在游戏开发中的优势作为一种静态类型语言，Golang在构建大型游戏系统

PHP游戏需求实现指南 Mar 11, 2024 am 08:45 AM

PHP游戏需求实现指南随着互联网的普及和发展，网页游戏的市场也越来越火爆。许多开发者希望利用PHP语言来开发自己的网页游戏，而实现游戏需求是其中一个关键步骤。本文将介绍如何利用PHP语言来实现常见的游戏需求，并提供具体的代码示例。1.创建游戏角色在网页游戏中，游戏角色是非常重要的元素。我们需要定义游戏角色的属性，比如姓名、等级、经验值等，并提供方法来操作这些

如何在Golang中实现精确除法运算 Feb 20, 2024 pm 10:51 PM

在Golang中实现精确除法运算是一个常见的需求，特别是在涉及金融计算或其它需要高精度计算的场景中。Golang的内置的除法运算符“/”是针对浮点数计算的，并且有时会出现精度丢失的问题。为了解决这个问题，我们可以借助第三方库或自定义函数来实现精确除法运算。一种常见的方法是使用math/big包中的Rat类型，它提供了分数的表示形式，可以用来实现精确的除法运算

js和vue的关系 Mar 11, 2024 pm 05:21 PM

js和vue的关系：1、JS作为Web开发基石；2、Vue.js作为前端框架的崛起；3、JS与Vue的互补关系；4、JS与Vue的实践应用。

See all articles

JavaScript双向链表和双向循环链表的实现

热AI工具

Undresser.AI Undress

AI Clothes Remover

Undress AI Tool

Clothoff.io

AI Hentai Generator

热门文章

热工具

记事本++7.3.1

SublimeText3汉化版

禅工作室 13.0.1

Dreamweaver CS6

SublimeText3 Mac版

热门话题