JavaScript数据结构之双向链表

单向链表在遍历时只能从头到尾或者从尾遍历到头;所以单向链表可以轻松到达下一节点,但是回到上一个节点是很困难的

而双向链表既可以从头遍历到尾, 又可以从尾遍历到头,链表的相联是双向的,一个节点既有向前连接的引用,也有向后连接的引用

但是正因如此,双向链表在插入或者删除某个节点时,需要处理四个节点的引用,并且所占用内存空间也更大一些

双向链表实现

JavaScript 代码实现双向链表

// 创建双向链表的构造函数
function DoublyLinkedList() {
 // 创建节点构造函数
 function Node(element) {
  this.element = element
  this.next = null
  this.prev = null // 新添加的
 }

 // 定义属性
 this.length = 0
 this.head = null
 this.tail = null // 新添加的

 // 定义相关操作方法
 // 在尾部追加数据
 DoublyLinkedList.prototype.append = function (element) {
  // 1.根据元素创建节点
  var newNode = new Node(element)

  // 2.判断列表是否为空列表
  if (this.head == null) {
   this.head = newNode
   this.tail = newNode
  } else {
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  }

  // 3.length+1
  this.length++
 }

 // 在任意位置插入数据
 DoublyLinkedList.prototype.insert = function (position, element) {
  // 1.判断越界的问题
  if (position < 0 || position > this.length) return false

  // 2.创建新的节点
  var newNode = new Node(element)

  // 3.判断插入的位置
  if (position === 0) { // 在第一个位置插入数据
   // 判断链表是否为空
   if (this.head == null) {
    this.head = newNode
    this.tail = newNode
   } else {
    this.head.prev = newNode
    newNode.next = this.head
    this.head = newNode
   }
  } else if (position === this.length) { // 插入到最后的情况
   // 思考: 这种情况是否需要判断链表为空的情况呢? 答案是不需要, 为什么?
   this.tail.next = newNode
   newNode.prev = this.tail
   this.tail = newNode
  } else { // 在中间位置插入数据
   // 定义属性
   var index = 0
   var current = this.head
   var previous = null

   // 查找正确的位置
   while (index++ < position) {
    previous = current
    current = current.next
   }

   // 交换节点的指向顺序
   newNode.next = current
   newNode.prev = previous
   current.prev = newNode
   previous.next = newNode
  }

  // 4.length+1
  this.length++

  return true
 }

 // 根据位置删除对应的元素
 DoublyLinkedList.prototype.removeAt = function (position) {
  // 1.判断越界的问题
  if (position < 0 || position >= this.length) return null

  // 2.判断移除的位置
  var current = this.head
  if (position === 0) {
   if (this.length == 1) {
    this.head = null
    this.tail = null
   } else {
    this.head = this.head.next
    this.head.prev = null
   }
  } else if (position === this.length -1) {
   current = this.tail
   this.tail = this.tail.prev
   this.tail.next = null
  } else {
   var index = 0
   var previous = null

   while (index++ < position) {
    previous = current
    current = current.next
   }

   previous.next = current.next
   current.next.prev = previous
  }

  // 3.length-1
  this.length--

  return current.element
 }

 // 根据元素获取在链表中的位置
 DoublyLinkedList.prototype.indexOf = function (element) {
  // 1.定义变量保存信息
  var current = this.head
  var index = 0

  // 2.查找正确的信息
  while (current) {
   if (current.element === element) {
    return index
   }
   index++
   current = current.next
  }

  // 3.来到这个位置, 说明没有找到, 则返回-1
  return -1
 }

 // 根据元素删除
 DoublyLinkedList.prototype.remove = function (element) {
  var index = this.indexOf(element)
  return this.removeAt(index)
 }

 // 判断是否为空
 DoublyLinkedList.prototype.isEmpty = function () {
  return this.length === 0
 }

 // 获取链表长度
 DoublyLinkedList.prototype.size = function () {
  return this.length
 }

 // 获取第一个元素
 DoublyLinkedList.prototype.getHead = function () {
  return this.head.element
 }

 // 获取最后一个元素
 DoublyLinkedList.prototype.getTail = function () {
  return this.tail.element
 }

 // 遍历方法的实现
 // 正向遍历的方法
 DoublyLinkedList.prototype.forwardString = function () {
  var current = this.head
  var forwardStr = ""

  while (current) {
   forwardStr += "," + current.element
   current = current.next
  }

  return forwardStr.slice(1)
 }

 // 反向遍历的方法
 DoublyLinkedList.prototype.reverseString = function () {
  var current = this.tail
  var reverseStr = ""

  while (current) {
   reverseStr += "," + current.element
   current = current.prev
  }

  return reverseStr.slice(1)
 }

 // 实现toString方法
 DoublyLinkedList.prototype.toString = function () {
  return this.forwardString()
 }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • JavaScript 双向链表操作实例分析【创建、增加、查找、删除等】

    本文实例讲述了JavaScript 双向链表操作.分享给大家供大家参考,具体如下: 一个 双向链表(doubly linked list) 是由一组称为节点的顺序链接记录组成的链接数据结构.每个节点包含两个字段,称为链接,它们是对节点序列中上一个节点和下一个节点的引用 开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点,通常是前哨节点或null,以方便遍历列表.如果只有一个前哨节点,则列表通过前哨节点循环链接.它可以被概念化为两个由相同数据项组成的单链表,但顺序相反. class D

  • JavaScript数据结构之双向链表定义与使用方法示例

    本文实例讲述了JavaScript数据结构之双向链表定义与使用方法.分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. function DoubleLink(

  • js实现双向链表互联网机顶盒实战应用实现

    上实战代码: linkedlistnode.js 节点类 复制代码 代码如下: /* * 链表节点 */ Dare.LinkedListNode = function () { this.data = null;//数据域 this.prev = null;//前驱 this.next = null;//后驱 }; Dare.extend(Dare.LinkedListNode, Dare); Dare.LinkedListNode.prototype.getValue = function (

  • JavaScript数据结构之双向链表和双向循环链表的实现

    双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. 双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针的双向链表,则可以向着两个方向遍历节点.这使得双向链表也可以在任

  • JS双向链表实现与使用方法示例(增加一个previous属性实现)

    本文实例讲述了JS双向链表实现与使用方法.分享给大家供大家参考,具体如下: 前面一篇讲述了<JS基于对象的链表实现与使用方法>,这里的双向链表通过增加一个previous属性实现. 单链表中若需要查找某一个元素时,必须从第一个元素开始进行查找,而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针,这连个指针分别指向前一个节点的地址和后一个节点的地址,这样无论通过那个节点都能够寻找到其他的节点. 原理如下图所示: 示例代码: /*双向链表 * */ function Node(eleme

  • JavaScript数据结构之双向链表

    单向链表在遍历时只能从头到尾或者从尾遍历到头:所以单向链表可以轻松到达下一节点,但是回到上一个节点是很困难的 而双向链表既可以从头遍历到尾, 又可以从尾遍历到头,链表的相联是双向的,一个节点既有向前连接的引用,也有向后连接的引用 但是正因如此,双向链表在插入或者删除某个节点时,需要处理四个节点的引用,并且所占用内存空间也更大一些 双向链表实现 JavaScript 代码实现双向链表 // 创建双向链表的构造函数 function DoublyLinkedList() { // 创建节点构造函数

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • JavaScript数据结构之二叉树的删除算法示例

    本文实例讲述了JavaScript数据结构之二叉树的删除算法.分享给大家供大家参考,具体如下: 从二叉查找树上删除节点的操作复杂程度取决于删除哪个节点.如果删除没有子节点的节点就非常简单,如果节点只有一个子节点,不管是左子节点还是右子节点,就变得稍微有点复杂,如果节点包含两个子节点就最复杂. 如果待删除节点是叶子节点,那么只需要将从父节点指向它的链接指向null. 如果待删除节点只包含一个子节点,那么原本指向它的节点就得使其指向它的子节点. 如果待删除节点包含两个子节点,那么我们可以采用两种方式

  • JavaScript数据结构之二叉树的遍历算法示例

    本文实例讲述了JavaScript数据结构之二叉树的遍历算法.分享给大家供大家参考,具体如下: 三种遍历的代码: function inOrder(node){//中序遍历 if(node!=null){ inOrder(node.left); document.write(node.show()+" "); inOrder(node.right); } } function preOrder(node){//先序遍历 if(node!=null){ document.write(no

  • JavaScript数据结构之二叉树的查找算法示例

    本文实例讲述了JavaScript数据结构之二叉树的查找算法.分享给大家供大家参考,具体如下: 前面文章介绍了二叉树的遍历,现在谈谈在二叉树中进行查找.对二叉查找树来说,一般有以下三类查找:最大值,最小值和给定值. 查找最小值就是遍历左子树,直到找到最后一个结点,这是因为在二叉查找树中较小的值总是在左子节点上的. 代码如下: function getMin(){//查找最小值 var current=this.root;//指向根节点 while(current.left!=null){ cur

  • JavaScript数据结构之二叉树的计数算法示例

    本文实例讲述了JavaScript数据结构之二叉树的计数算法.分享给大家供大家参考,具体如下: 二叉查找树的一个用途就是记录一组数据集中数据出现的次数.比如记录成绩的分布,给定一组考试成绩,如果未出现则加入树,如果已经出现则数量加一. 所以要修改Node对象,添加记录成绩出现次数加一,代码如下: function Node(data,left,right){ this.data=data; this.left=left; this.right=right; this.show=show; thi

  • JavaScript数据结构之二叉查找树的定义与表示方法

    本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法.分享给大家供大家参考,具体如下: 树是一种非线性的数据结构,以分层的方式存储数据.树被用来存储具有层级关系的数据,比如文件系统中的文件:树还被用来存储有序列表.这里将研究一种特殊的树:二叉树.选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样). 树是n个结点的有限集.最上面的为根,下面为根的子树.树的节点包含一个数

  • JavaScript数据结构链表知识详解

    最近在看<javascript数据结构和算法>这本书,补一下数据结构和算法部分的知识,觉得自己这块是短板. 链表:存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的.每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成. 好处:可以添加或移除任意项,它会按需扩容,且不需要移动其他元素. 与数组的区别: 数组:可以直接访问任何位置的任何元素: 链表:想要访问链表中的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素. 做点小笔记. funct

随机推荐