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

更新日期: 2018-07-01阅读: 2.1k标签: 数据结构

什么是链表?

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

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

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


创建一个链表类

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; // 最后把这个字符串返回
  }

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


最后

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

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

数据结构有哪几种?

据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。包括三个组成成分:数据的逻辑结构、物理结构(存储结构)、数据运算结构。

为什么我认为数据结构与算法对前端开发很重要?

一个具有层级结构的数据,实现这个功能非常容易,因为这个结构和组件的结构是一致的,递归遍历就可以了。但是,由于后端通常采用的是关系型数据库,所以返回的数据通常会是这个样子:前端这边想要将数据转换一下其实也不难,因为要合并重复项

JS中数据结构之链表

数组不总是组织数据的最佳数据结构,在很多编程语言中,数组的长度是固定的,所以当数组已被数据填满时,再要加入新的元素就会非常困难。在数组中,添加和删除元素也很麻烦,因为需要将数组中的其他元素向前或向后平移。

JS中数据结构之图

图由边的集合及顶点的集合组成。边是有方向的是有序图(有向图),否则就是无序图(无向图)。图中的一系列顶点构成路径,路径中所有的顶点都由边连接。路径的长度用路径中第一个顶点到最后一个顶点之间边的数量表示。

ES6中的Set数据结构以及使用使用场景

Set 是ES6提供的一种新的数据结构,它允许你存储任何类型的唯一值,而且Set中的元素是唯一的。我们用new操作符来生成一个Set对象,set结构的实例有以下属性

JS数据结构与算法_链表

链表更加像是数组。链表和数组都是用于存储有序元素的集合,但有几点大不相同,链表的实现不像之前介绍的栈和队列一般依赖于数组(至少我们目前是这样实现的),它必须自己构建类并组织逻辑实现。我们先创建一个Node类

JS数据结构与算法_集合&字典

集合set是一种包含不同元素的数据结构。集合中的元素成为成员。集合的两个最重要特性是:集合中的成员是无序的;集合中不允许相同成员存在,计算机中的集合与数学中集合的概念相同,有一些概念我们必须知晓:

JS数据结构与算法_树

一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点:关于数的深度和高度的问题,不同的教材有不同的说法

JavaScript数据结构与算法-String

给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。主要就是用到了数组的 split 、 reverse 、 join 、 map 方法,原理:就是把字符串变成数组

数据结构与算法之绪论

什么是数据结构?简单来说可以解释为:程序设计=数据结构+算法;主要是用来研究数据结构的关系,数据元素之间存在的一种或多种特定关系的集合;

点击更多...

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