登录  /  注册
首页 > web前端 > js教程 > 正文

在JavaScript中详细讲解双向链表和双向循环链表

亚连
发布： 2018-06-23 17:23:25
原创
1212人浏览过

本篇文章主要介绍了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; 
  }; 
}
登录后复制

上面是我整理给大家的，希望今后会对大家有帮助。

相关文章：

在Jstree中如何实现选中父节点时被禁用的子节点也会选中

在vue.js中如何整合mint-ui里的轮播图

在AngularJS中如何实现集合数据遍历显示

以上就是在JavaScript中详细讲解双向链表和双向循环链表的详细内容，更多请关注php中文网其它相关文章！

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题，提供实时的代码和解决方案，帮助你解决各种难题。不仅如此，它还能提供编程资源和学习指导，帮助你快速提升编程技能。无论你是初学者还是专业人士，AI智能助手都能成为你的可靠助手，助力你在编程领域取得更大的成就。
我要提问
相关标签：
JavaScript vue.js 循环 指针 数据结构 JS ui
来源：php中文网
收藏 点赞
上一篇：在vue-music中关于Player播放器组件的使用说明 下一篇：在JS中如何实现的找零张数最小问题
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
作者最新文章
最新问题
子窗口操作父窗口，输出没反应 前两句可执行，最后一句没法应
P粉722478067来自于2024-04-19 15:37:47
0 0 19
父窗口没有输出 document.onclick = function(){ window.opener.document.write('我是子窗口的输出');  &nb...
P粉722478067来自于2024-04-18 23:52:34
0 0 40
关于CSS思维导图的课件在哪？ 课件
凡人来自于2024-04-16 10:10:18
0 0 130
PX自动转换为REM错误  <style>html {   font-size: calc(100vw / 3.75);      }...
凡人来自于2024-04-16 09:34:16
0 0 772
PHP数组从URL参数中获取的行为不如预期 我有一个包含类别ID的URL参数，我想将其视为一个数组，如下所示：http://example.com?cat[]=3,9,13在PHP中，我使用它从URL参数获取数组：$catI...
P粉785905797来自于2024-04-06 22:09:02
0 1 438
通过添加 Width 属性将内容向左移动 我已经为主体提供了边距。主要{左边缘：200px;右边距：200px；文本对齐：居中}由于我想以两行而不是一行显示文本，因此我在样式中添加了width属性。.p{字体大小：12px...
P粉738046172来自于2024-04-06 22:01:35
0 2 317
我应该在 apache 中哪里放置 CustomLog 指令 我正在使用php:7.2-apachedocker。我需要禁用运行状况检查url登录访问日志。基于此链接，他们提到了有关修改Customlog指令的信息。我不是关于需要更改Cust...
P粉573809727来自于2024-04-06 22:03:59
0 1 442
返回值中变量的格式是什么？ 我是php的新学习者。我发现有一段代码：if($x<time()){return[false,'error'];}逻辑或变量并不重要，但我不明白[false,'error']...
P粉757556355来自于2024-04-06 21:55:20
0 1 266
页面突然无法拉动 css 或 bootstrap 所以我正在开发一个页面，我昨天做了一部分，效果很好，今天我继续做剩下的部分，一切都很好。当我尝试将其作为普通html页面打开时，CSS或BOOTSTRAP不起作用，仅显示页面文本，...
P粉771233336来自于2024-04-06 21:58:04
0 1 357
如何在 React 中的排序方法上触发渲染（带有过滤器和分页）？ 这是我的Sort.js样式组件：<SortWrapper><SortText>SortBy</SortText><SortSelecton...
P粉970736384来自于2024-04-06 21:28:37
0 1 1863
相关专题
更多>
热门推荐
热门教程
更多>
相关推荐
热门推荐
最新课程
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网：公益在线php培训，帮助PHP学习者快速成长！
关注服务号 技术交流群
app下载
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号

  • 精品班

  • 技术支持

  • 技术咨询

  • 学习群

  • 会员优惠

  • 返回顶部