资讯专栏INFORMATION COLUMN

JS数据结构学习:链表

XanaHopper / 1433人阅读

摘要:在存储多个元素时,我们最常用的数据结构可能是数组,究其原因可能是数组访问方便,可以直接通过访问,但是数组也存在一定的缺点,数组的大小是固定,数组在执行插入或者删除的时候成本很高。

在存储多个元素时,我们最常用的数据结构可能是数组,究其原因可能是数组访问方便,可以直接通过[]访问,但是数组也存在一定的缺点,数组的大小是固定,数组在执行插入或者删除的时候成本很高。

链表存储的是有序的元素集合,和数组不同的是,链表中的元素在内存并不是连续放置,每个元素由一个存储元素本身的节点和一个指向下一个元素的引用组成,结构如下图所示:

和数组相比,链表的优势在于:添加或者删除元素不需要移动其他元素,劣势在与链表相对于数组结构更复杂,需要一个指向下一个元素的指针,在访问链表中的某个元素也需要从头迭代,而不是像数组一样直接访问

链表的创建

首先让我们来看一下链表的大概骨架,需要定义一些什么属性:

function LinkedList() {
  let Node = function (element) {
    this.element = element
    this.next = null
  }
  let length = 0
  let head = null
  this.append = function (element) {
  }
  this.insert = function (position, element) {
  }
  this.removeAt = function (position) {
  }
  this.remove = function (element) {
  }
  this.indexOf = function (element) {
  }
  this.isEmpty = function () {
  }
  this.size = function () {
  }
  this.getHead = function () {
  }
  this.toString = function () {
  }
  this.print = function () {
  }
}

首先LinkedList里面需要定义一个Node辅助类,表示要加入链表的项,包含一个element属性和一个指向下一个节点的指针next,接下来定义了一个指针的头head和指针的长度length,然后就是最重要的类里面的方法,接下来就让我们一起来看这些方法的职责和实现

append(向链表尾部追加元素)

链表在向尾部追加元素的时候有两种情况:链表为空,添加的是第一个元素,或者链表不为空,追加元素,下面来看具体实现:

this.append = function (element) {
    let node = new Node(element), current
    if (head === null) {
      head = node // 链表为空时,插入
    } else {
      current = node
      while (current.next) { // 循环链表,直到最后一项
        current = current.next
      }
      current.next = node // 找到最后一项,将新增元素连接
    }
    length++
  }

现在让我们先来看第一个种情况,链表为空时,插入就直接是头,因此直接将node赋值给head就行,第二种情况,当链表有元素时,就需要先循环链表,找到最后一项,然后将最后一项的next指针指向node

removeAt(移除元素)

现在让我们来看看怎么从指定位置移除元素,移除元素也有两个场景,第一种是移除第一个元素,第二种是移除第一个以外的任意一个元素,来看具体实现:

this.removeAt = function (position) {
    if (position > -1 && position < length) { // 判断边界
      let previous, index = 0, current = head
      if (position === 0) { // 移除第一项
        head = current.next
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      length--
      return current.element
    } else {
      return null
    }
  }

接下来一起来分析一下上面的代码,首先判断要删除的位置是不是有效的位置,然后来看第一种情况,当移除的元素是第一项是时,此时直接将head指向第二个元素就行了,第二种情况就会稍微复杂一点,首先需要一个index控制递增,previous记录前一个位置,移除当前元素,就是将前一个元素的next指向下一个元素,来看一个示意图:

因此在while循环中始终用previous记录上一个位置元素,current记录下一个元素,跳出循环时,上一个元素的next指针指向当前元素的next指针指向的元素,就将当前元素移出链表

insert(任意位置插入)

接下来来看在任意位置插入的insert方法,这个方法同样需要考虑两种情况,插入位置在头部和插入位置不在头部,下面来看一下具体实现:

this.insert = function (position, element) {
    if (position > -1 && position <= length) {
      let node = new Node(element),previous, index = 0, current = head
      if (position === 0) {
        node.next = current
        head = node
      } else {
        while (index++ < position) {
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current
      }
      length++
      return true
    } else {
      return false
    }
  }

先来看第一种情况,链表起点添加一个元素,将node.next指向current,然后再将node的引用赋值给head,这样就再链表的起点添加了一个元素,第二种情况,在其他位置插入一个元素,previous是插入元素的前一个元素,current为插入元素的后一个元素,想要插入一个元素,就需要将前一个元素的next指向要插入的元素,要插入元素的next指向下一个元素,来看示意图:

如上图所示:将新项node插入到previous和current之间,需要将previous.next指向node,node.next指向current,这样就在链表中插入了一个新的项

toString

toString方法会把LinkedList对象转换成一个字符串,下面来看具体实现:

this.toString = function () {
    let current = head, string = ""
    while (current) {
      string += current.element + (current.next ? "n" : "")
      current = current.next
    }
    return string
  }

循环遍历所有元素,以head为起点,当存在下一个元素时,就将其拼接到字符串中,直到next为null

indexOf

indexOf方法返回对应元素的位置,存在就返回对应的索引,不存在返回-1,来看具体的实现:

this.indexOf = function (element) {
    let current = head, index = 0
    while (current) {
      if (current.element === element) {
        return index
      }
      index++
      current = current.next
    }
    return -1
  }

遍历链表,当前元素的值与目标值一致时返回元素的位置index,遍历完链表还没找到则返回-1

remove、isEmpty、size、getHead

由于这几个方法实现比较简单,直接来看具体实现:

this.remove = function (element) { // 移除指定元素
    let index = this.indexOf(element)
    return this.removeAt(index)
  }
this.isEmpty = function () { // 判断链表是否为空
    return length === 0
  }
this.size = function () { // 获取链表长度
    return length
  }
this.getHead = function () { // 获取链表头
    return head
  }
总结

这篇文章主要对链表做了简单介绍,对链表的简单实现。如果有错误或不严谨的地方,欢迎批评指正,如果喜欢,欢迎点赞。

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/102042.html

相关文章

  • 我对JS链表的简单学习

    摘要:我对链表的学习什么是链表要存储多个元素,数组可能是最常用的数据结构。链表的学习创建一个链表各种方法表示要加入列表的项,它包含一个属性以及一个属性,表示要添加到列表的值,表示指向列表下一个节点项的指针。 我对JS链表的学习 什么是链表 要存储多个元素,数组可能是最常用的数据结构。这种数据结构非常方便,但是有一个缺点:从数组的起点或者中间插入或移除项的成本非常高,因为需要移动元素(比如你插...

    余学文 评论0 收藏0
  • 我对JS散列表的简单学习

    摘要:对散列表的简单学习类也叫类,是类的一种散列表实现方式。键值散列函数散列值形成散列表地址数据键值对相关操作方法创建一个散列表实现一个散列函数,即将码值相加的方法。 对JS散列表的简单学习 HashTable类也叫HashMap类,是Dictionary类的一种散列表实现方式。 散列算法的作用是尽可能快的在数据结构中找到一个值。 在之前的学习中,如果你想要获得数据结构中的一个值,需要遍历整...

    lindroid 评论0 收藏0
  • JS数据结构与算法_链表

    摘要:上一篇数据结构与算法栈队列下一篇数据结构与算法集合字典写在前面说明数据结构与算法系列文章的代码和示例均可在此找到上一篇博客发布以后,仅几天的时间竟然成为了我写博客以来点赞数最多的一篇博客。 上一篇:JS数据结构与算法_栈&队列下一篇:JS数据结构与算法_集合&字典 写在前面 说明:JS数据结构与算法 系列文章的代码和示例均可在此找到 上一篇博客发布以后,仅几天的时间竟然成为了我写博客以...

    NeverSayNever 评论0 收藏0
  • CSS技巧

    摘要:技巧使你的更加专业这是上关于技巧的一篇译文,另外你也可以在本项目看到原文。列举了一些很实用的技巧,比如给空内容的标签添加内容,逗号分隔列表等等。排序算法看源码,把它背下来吧排序算法的封装。主要帮助初学者更好的掌握排序算法的实现。 成为专业程序员路上用到的各种优秀资料、神器及框架 成为一名专业程序员的道路上,需要坚持练习、学习与积累,技术方面既要有一定的广度,更要有自己的深度。 Java...

    DangoSky 评论0 收藏0

发表评论

0条评论

XanaHopper

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<