链表!比数组更适合做增删操作的数据结构

更新日期: 2018-07-01阅读量: 1224标签: 数据

什么是链表?

链表和数组的对比:在大多数语言中,数组的大小是固定的,从数组的起点或中间添加或删除元素的成本很高,因为需要移动元素。

链表中的每一个元素在内存中不是连续放置的,和它左右两侧元素是没有关系的。每个元素有一个存储元素本身的节点和指向下一个元素的引用组成。相对于数组,链表的好处在于添加或删除元素的时候不需要移动其它元素。在数组中我们可以直接访问任何位置的任何元素,而要想访问链表中的某一个元素,则需要从起点(链表头)开始迭代链表直到找到所需的元素。

举个栗子: 一列火车是由一系列车厢组成的。每节车厢或车皮都相互连接,你很容易分离一节车箱,改变它的位置、添加或移除它。每节车厢相当于链表的元素,车厢间的对接扣就是元素的引用。


创建一个链表类

const defaultCompare = function (a, b) { // 一个比较函数
  if (a === b) return 0;
  return a < b ? -1 : 1;
}

class Node { // 一个助手类,用来表示我们想要添加到链表中的元素
  constructor(element, next) {
    this.element = element; // 元素的值
    this.next = next; // 指向链表中下一个元素的指针
  }
}

class LinkedList { // 链表类
    constructor(equalsFn = defaultEquals) {
    this.equalsFn = equalsFn; // 比较链表中的元素是否相等,默认a===b
    this.count = 0; // 链表中的元素数量
    this.head = undefined; // 表头
  }
}


创建几个链表的方法

向链表的尾部添加元素

push(element) {
    const node = new Node(element); // 创建node项
    let current; // 声明一个指向链表中的临时项
    if (this.head == undefined) { // 如果链表头为空,即链表为空
      this.head = node; // 直接让表头等于当前元素就好了,下一项(next)未传,因此为undefined
    } else {
      current = this.head; // 先让current等于第一个元素
      while (current.next != null) { // 只要当前元素的下一项元素不是假的,便继续循环
        current = current.next;
      }
      current.next = node; // 找到最后一个元素后,让它的下一个元素等于传进来的元素
    }
    this.count++;// 最后把总长度自增就好了
  }

首先初始化node类,把element作为值传入。尾部添加元素分为两种情况,一种是链表为空,一种是链表有值,在后者时,因为链表只有链表头的引用,因此在向链表尾部添加元素时,我们需要循环列表,直到找到最后一个元素,为此 我们需要一个指向链表中current项的变量。如果链表头没值表示在向链表添加第一个元素,直接让表头等于当前元素就好了,下一项的引用(next)未传,因此为undefined

然后就是第二种情况,首先让current等于链表头,然后循环访问列表,直到找到最后一个元素,然后就是让最后一个元素的下一项的引用指向想要添加到链表的节点。最后把总长度自增就好了

从特定位置移除一个元素

removeAt(index) {
    if (index >= 0 && index < this.count) { // 检查越界值
      let current = this.head;
      if (index === 0) { // 如果是表头
        this.head = current.next; // 就让表头等于下一个引用
      } else {
        let previous;
        for (let i = 0; i < index; i++) { // 嗯,开始迭代把~~~
          previous = current;
          current = current.next;
        }
        previous.next = current.next;
        // 上一个的下一个等于现在的下一个,,,(现在内心os:我是谁,我在哪???)当前节点就会被丢弃在计算机内存中,等着被垃圾回收器移除
      }
      this.count--;// 长度自减
      return current.element; // 返回移除的元素
    }

    return undefined;
  }

由于该方法需要得到移除元素的index(位置),我们需要验证该index是从0到链表的长度之间的。如果不是就返回undefined。如果移除的是链表中的第一个元素,就要让head指向列表的第二个元素。我们将current变量创建一个对链表中第一个元素的引用。这样current变量就是对链表中第一个元素的引用。这时候如果如果把head赋为current.next,就会移除第一个元素。我们也可以直接把head赋为head.next,不使用current。

如果我们要移除的是链表的最后一个元素或者中间的某个元素。就需要对链表进行迭代,直到到达目标位置。在到达目标位置后,current变量就会变成我们想要从链表中移除的节点。因此,要从链表中移除当前元素,要做的就是将previous.next和current.next链接起来。这样,当前节点就会被丢弃在计算机内存中,等着被垃圾回收器清除。

循环迭代链表直到目标位置

getElementAt(index) {
    if (index >= 0 && index <= this.count) return undefined; // 检查越界值
    let node = this.head; // 默认等于表头
    for (let i = 0; i < index && node != null; i++) { // 嗯,开始迭代把~~~
      node = node.next;
    }
    return node;
  }

在remove方法中,我们需要迭代整个链表直到到达我们的目标索引index(位置)。循环到目标index的代码片段在链表方法中会经常用到。因此,我们可以将这部分逻辑独立为单独的办法,这样就可以在不同的地方复用它。

然后我们可以使用刚刚创建的getElementAt方法来重构remove方法

if(index===0){
    // 第一个位置的逻辑
} else {
    const previous = this.getElementAt(index - 1);
    current = previous.next;
    previous.next = current.next;
}
this.count--;

在任何位置插入元素

insert(element, index) {
    if (index >= 0 && index <= this.count) { // 边界处理
      const node = new Node(element); // 实例化当前元素
      if (index === 0) { // 如果插在表头
        const current = this.head;// 声明一个变量,等于原来的表头
        node.next = current;// 传入元素的下一个引用等于current
        this.head = node; // 当前表头等于传入的元素
      } else {
        const previous = this.getElementAt(index - 1);// 找到传入索引的上一个值
        previous.next = node;// 上一个的引用等于传入的值
        node.next = previous.next;// 传入值的下一个引用等于上一个的下一个引用
        
      }
      this.count++;// 总长度自增
      return true; // 最后返回true
    }
  return false; // 如果位置未找到返回false
}

先惯例的做一下边界处理。首先如果是插在链表头,我们先声明一个变量等于原来的链表头,再让插入元素的先一个引用等于原来的current变量,最后让当前表头等于传入的元素。如果是在链表中间或者末尾我们需要用getElementAt方法先找到目标位置的上一个元素,然后让上一个的引用等于传入的值。再把传入值的下一个引用等于上一个的下一个引用。最后一定记得把总长度加一,返回true

返回一个元素的位置

indexOf(element) {
    let current = this.head; // 等于表头
    for (let i = 0; i < this.size() && current != null; i++) { // 循环迭代所有元素
      if (this.equalsFn(element, current.element)) { // 找到和当前元素相等的第一个元素
        return i;// 返回索引
      }
      current = current.next;// 如果不相等,就继续迭代下一个
    }
    return -1; // 如果都没找到,就返回-1
  }

indexOf方法接收一个元素的值,如果在链表中找到了它,就返回元素的位置,否则返回-1。一如既往,需要一个变量来帮助我们循环访问列表。该变量是current,它的初始值是head

然后迭代元素,从链表头开始,直到链表长度为止。为了确保不会发生运行时错误,我们可以验证一下current变量是否为null或undefined。循环迭代所有元素直到找到和当前元素相等的第一个元素,返回它的所在位置

如果没找到,就返回-1,移除传入的元素

remove(element) { 
    const index = this.indexOf(element); // 先找到这个元素的第一个索引
    return this.removeAt(index); // 利用删除指定位置元素的方法,搞掉它
  }

我们已经有了一个用来移除给定位置元素的方法,也有了indexOf方法。利用indexOf方法找到它的位置,利用删除指定位置元素的方法,搞掉它。检查是否为空,长度,获取链表头

isEmpty() {
    return this.size() === 0;
  }
  size() {
    return this.count;
  }
  getHead() {
    return this.head;
  }

还是比较简单的。把所有元素转换成字符串

toString() {
    if (this.head == null) { // 如果列表为空,就返回空字符串
      return '';
    }
    let objstring = `${this.head.element}`; // 创建一个变量,先让他等于表头的元素
    let current = this.head.next; // 等于表头的下一个引用
    for (let i = 1; i < this.size() && current != null; i++) { // 循环迭代所有元素
      objstring = `${objString},${current.element}`; // 让这个字符串等于原来的字符串加上当前元素
      current = current.next; // 当前元素等于当前的下一个引用
    }
    return objString; // 最后把这个字符串返回
  }

首先,如果链表为空,我们就返回一个空字符串。如果有值我们就用链表第一个元素的值来初始化方法最后返回的字符串。然后我们迭代链表中的所有其它元素,将元素值添加到字符串上。最后把这个字符串返回。


最后

今天的随手笔记就记到这里了,等有时间我会再写一篇关于链表的各种增强版本。总之,在我阅读完这一章后觉得链表相比数组,更适合做增删操作,而数组更适合存储一些比较固定不变的有序集合。

站长推荐

1.云服务推荐: 国内主流云服务商/虚拟空间,各类云产品的最新活动,优惠券领取。领取地址:阿里云腾讯云硅云

链接: https://www.fly63.com/article/detial/3999

双向数据绑定与单向数据绑定的各自优势和关系

在react中是单向数据绑定,而在vue和augular中的特色是双向数据绑定。为什么会选择两种不同的机制呢?我猜测是两种不同的机制有不同的适应场景,查了一些资料后,总结一下。

原生JS数据绑定的实现

双向数据绑定是非常重要的特性 —— 将JS模型与HTML视图对应,能减少模板编译时间同时提高用户体验。我们将学习在不使用框架的情况下,使用原生JS实现双向绑定 —— 一种为Object.observe

JavaScript判断数据类型的多种方法【 js判断一个变量的类型】

js判断数据类型的多种方法,主要包括:typeof、instanceof、 constructor、 prototype.toString.call()等,下面就逐一介绍它们的异同。

javascript中的typeof返回的数据类型_以及强制/隐式类型转换

由于js为弱类型语言拥有动态类型,这意味着相同的变量可用作不同的类型。 typeof 运算符返回一个用来表示表达式的数据类型的字符串,目前typeof返回的字符串有以下这些: undefined、boolean、string、number、object、function、“symbol

使用typeof obj===‘object’潜在的问题,并不能确定obj是否是一个对象?

在js中我们直接这样写typeof obj===‘object’有什么问题呢?发现Array, Object,null都被认为是一个对象了。如何解决这种情况,能保证判断obj是否为一个对象

js进制数之间以及和字符之间的转换

js要处理十六进制,十进制,字符之间的转换,发现有很多差不多且书写不正确的方法.一个一个实践才真正清楚如何转换,现在来记录一下它们之间转换的方法。

js判断数字是奇数还是偶数的2种方法实现

奇数和偶数的判断是数学运算中经常碰到的问题,这篇文章主要讲解通过JavaScript来实现奇偶数的判断。2种判断方法:求余% 、&1

js算法_判断数字是否为素数/质数

质数又称素数。指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。比如100以内共25个,js实现代码如下。

Js数据类型转换_JavaScript 那些不经意间发生的数据类型自动转换

JavaScript自动类型转换真的非常常见,常用的一些便捷的转类型的方式,都是依靠自动转换产生的。比如 转数字 : + x 、 x - 0 , 转字符串 : \\\"\\\" + x 等等。现在总算知道为什么可以这样便捷转换。

Js中实现XML和String相互转化

XML是标准通用标记语言 (SGML) 的子集,非常适合 Web 传输。XML 提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。 这篇文章主要介绍Js中实现XML和String相互转化

点击更多...

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!