周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

数据结构——双向链表

2022-08-13 65点热度 0人点赞 0条评论

一、区分单/双向链表

单向链表相连的过程是单向的,只能从一个方向遍历

  • 可以获取当前节点的下一个节点,但是很难回到上一个节点,但是实际开发中经常会有类似的需求

双向链表可以从两个方向遍历

  • 一个节点既有向前连接的引用,也有向后连接的引用
  • 每次插入和删除的时候,需要处理四个引用,比单向链表更加复杂
  • 相对于单向链表,占用的内存空间相对更大

image-20220812225006047

image-20220812225401006

双向链表的特点

  • 使用一个head和tail分别指向头部和尾部的节点
  • 每个节点分别包括前指针/后指针/保存的元素
  • 双向链表第一个节点的前指针指向null
  • 双向链表最后一个节点的后指针指向null

二、双向链表常见的操作

在单向链表的基础上进行补充:

数据结构:单向链表

forwardString():返回正向遍历的节点字符串形式

backwordString:返回反向遍历的节点字符串形式

三、封装双向链表

1、按照位置插入数据(insert)方法图解:

  • position=0

image-20220813121226757

  • position=length

image-20220813121140741

  • 0<position<length

image-20220813121241579

2、按照位置删除元素

  • 删除头部元素

image-20220813135523670

  • 删除尾部元素

image-20220813135538066

  • 删除中间元素

image-20220813135555431

四、代码实现

/**
 * 封装双向链表
*/
function DoudlyLinkedList() {
  // 属性
  this.head = null
  this.tail = null
  this.length = 0

  // 内部类(用于创建节点)
  function Node(data) {
    this.data = data
    this.prev = null
    this.next = null
  }

  // 尾部追加数据
  DoudlyLinkedList.prototype.append = function (data) {
    // 创建节点
    let newNode = new Node(data)

    // 判断添加之前是否为空链表
    if (this.head == null) {
      this.head = newNode
      this.tail = newNode
    } else {
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }

    // 修改长度
    this.length += 1
  }
  // 正向遍历的方法
  DoudlyLinkedList.prototype.forwardString = function () {
    let flag = this.head
    let result = ''
    while (flag) {
      result += flag.data + ' '
      flag = flag.next
    }
    return result
  }
  // insert
  DoudlyLinkedList.prototype.insert = function (position, data) {
    // position判断
    if (position < 0 || position > this.length) return false
    // 创建节点
    let newNode = new Node(data)
    // 判断插入位置
    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 {
      let index = 0
      let flag = this.head
      this.previous = null
      while (index < position) {
        previous = flag
        flag = flag.next
        index++
      }
      newNode.next = flag
      newNode.prev = previous
      flag = prev = newNode
      previous.next = newNode
    }

    this.length += 1
    return true
  }
  // removeAt
  DoudlyLinkedList.prototype.removeAt = function (position) {
    if (position < 0 || position >= this.length) return null
    // 判断移除的位置
    let flag = this.head
    if (position == 0) {
      if (this.length == 0) {
        this.head = null
        this.tail = null
      } else {
        this.head = this.head.next
        this.head.prev = null
      }
    } else if (position == this.length - 1) {
      flag = this.tail
      this.tail = this.tail.prev
      this.tail.next = null
    } else {
      let index = 0
      let previous = null
      while (index < position) {
        previous = flag
        flag = flag.next
        index++
      }
      previous.next = flag.next
      flag.next.prev = previous
    }

    this.length -= 1
    return flag.data
  }

  // 获取元素的位置
  DoudlyLinkedList.prototype.indexOf = function (data) {
    let flag = this.head
    let index = 0
    while (flag) {
      if (flag.data == data) {
        return index
      }
      index++
      flag = flag.next
    }
    return -1
  }

  // 根据元素删除
  DoudlyLinkedList.prototype.remove = function (data) {
    let index = this.indexOf(data)
    return this.removeAt(index)
  }

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

  // 获取链表长度
  DoudlyLinkedList.prototype.size = function () {
    return this.length
  }
  // 获取第一个元素
  DoudlyLinkedList.prototype.getHead = function () {
    return this.head.data
  }
  // 获取最后一个元素
  DoudlyLinkedList.prototype.getTail = function () {
    return this.tail.data
  }
}
let Dlist = new DoudlyLinkedList()
Dlist.append('a')
Dlist.append('b')
Dlist.append('c')
Dlist.append('d')
console.log(Dlist.forwardString())  // a b c d
console.log(Dlist.insert(1, 'ok'))
console.log(Dlist.insert(Dlist.length, 'no'))
console.log(Dlist.insert(0, 'first'))
console.log(Dlist.forwardString())  // first a ok b c d no
console.log(Dlist.removeAt(1))  // a
console.log(Dlist.forwardString())  // first ok b c d no
console.log(Dlist.indexOf('no'))  // 5
console.log(Dlist.remove('first'))  // first
console.log(Dlist.forwardString())  // ok b c d no
console.log(Dlist.isEmpty())  // false
console.log(Dlist.size())     // 5
console.log(Dlist.getHead())  // ok
console.log(Dlist.getTail())  // no
标签: 双向链表 数据结构
最后更新:2022-08-13

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇
下一篇 >

文章评论

取消回复
目录
  • 一、区分单/双向链表
  • 二、双向链表常见的操作
  • 三、封装双向链表
  • 四、代码实现

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号