欢迎来到雅狐站长网!
兔子CDN

Javascript/Ajax

当前位置:主页 > 网页制作 > Javascript/Ajax >

JavaScript数据结构之双向链表

时间:2021-04-23 21:24:21|栏目:Javascript/Ajax|点击:

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

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

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

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()
 }
}

上一篇:JavaScript实现二叉搜索树

栏    目:Javascript/Ajax

下一篇:小程序录音功能实现

本文标题:JavaScript数据结构之双向链表

本文地址:http://www.cnzzww.cn/JavaScript/56469.html

广告投放 | 联系我们 | 版权申明

重要申明:本站所有的文章、图片、评论等,均由网友发表或上传并维护或收集自网络,属个人行为,与本站立场无关。

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ: | 邮箱:111#qq.com(#换成@)

Copyright © 2015-2020 雅狐站长网 版权所有 苏ICP备20040415号