[JS与链表]双向链表

这篇具有很好参考价值的文章主要介绍了[JS与链表]双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

阅读本文前请先阅读

[JS与链表]普通链表_AI3D_WebEngineer的博客-CSDN博客

ES6的Class继承

类的继承可以使用extends,让子类继承父类的属性和方法。

而在子类内部(构造函数constructor)必须调用super()实现继承(super()代表父类构造函数

class A {constructor() {this.name ='abc'}}
class B extends A {constructor() {super()}}
// -----------------------------------------
var b = new B() // {name:'abc'}
class A {constructor(userName) {this.name = userName}}
class B extends A {constructor(yourName) {super(yourName)}}
// ---------------------------------------------------
var b = new B('ddd') // {name:'ddd'}

双向链表

双向链表与普通链表的区别在于:普通链表的节点是链向下一个节点的(单向),双向链表的节点是链向上下两个节点的。

[JS与链表]双向链表

我们先从Node节点开始改造:

以下代码

class DoublyNode extends Node {
    #prev;
    constructor(ele,next,prev) {
        super(ele,next);
        this.prev = prev;
    }
}
class DoublyLinkedList extends LinkedList {
    constructor(equalFn=compareFn) {
        super(equalFn);
        this.tail = undefined
    }
}

新的DoublyLinkedList类的构造函数里会初始化equalsFn、head、count和tail四个属性

[JS与链表]双向链表

所谓双向链表就是可以由头到尾,也能由尾到头,甚至于在中间可以灵活转向(因为doublyNode节点有前后节点),而单向链表如果迭代时错过了要找的元素,则需要重新迭代。

通过下标获得链表节点

同链表的getNodeAt或者叫getElementAt方法(已继承)


getNodeAt(index) {
     if (index>0 && index >=this.count) {return undefined}
     if (this.index === 0) {return this.head}
     let currentNode = this.head;
     for (var i =0;i<index;i++) {
           currentNode = currentNode.next
     }
    return currentNode
}

在任意位置插入新节点

比链表多了一种场景。就是尾部插入。

创建新节点:

const node = new DubblyNode(element);

从开头插入:

①空链表

this.head = node;
this.tail = node;

②非空链表

[JS与链表]双向链表
var currentNode = this.head;

node.next = currentNode;
currentNode.prev = node;
this.head = node

从尾巴插入:

[JS与链表]双向链表
var currentNode = this.Tail;

currentNode.next = node;
node.pre = currentNode;
this.tail = node;

在中间插入:

[JS与链表]双向链表
const originNode = this.getNodeAt(index);
const preNode = this.getNodeAt(index - 1);
node.next = originNode;;
node.prev = preNode;
originNode.prev = node;
preNode.next = node;

整合:

insert(element,index) {
    if (index < 0 || index > this.count) {return false}
    const node = new DoublyNode(element);
    let current = this.head;
    // 开头插入
    if (index === 0) {
         // 链表为空
        if (this.head == null) {
            this.head = node;
            this.tail = node;
        }else {
           // 链表非空
            node.next = currentNode;
            currentNode.prev = node;
            this.head = node
        }
    }
    if (index === this.count) {
        // 最后一项
        currentNode = this.Tail;
        currentNode.next = node;
        node.pre = currentNode;
        this.tail = node;
    }
    // 在中间插入
    const originNode = this.getNodeAt(index);
    const prevNode = this.getNodeAt(index - 1);
    node.next = originNode;
    node.prev = prevNode;
    originNode.prev = node;
    prevNode.next = node;
    // 结束
    this.count ++;
    return true
}

根据下标移除元素

需要判断三种场景:

①移除头部

[JS与链表]双向链表
removeAt(index) {
    if (index < 0 || index > this.count || !this.count) {return undefined}
    let current = this.head;
    if (index === 0) {
        this.head = current.next;
        if (this.count === 1) {
            this.tail = undefined
        }
    }
    this.count --;
    return current.value
}
[JS与链表]双向链表
...
if (index === 0) {
        this.head = current.next;
        if (this.count === 1) {
           ...
        }else {
            this.head.prev = undefined
        }
 }
...

②移除尾部

[JS与链表]双向链表
...
if (index === this.count - 1) {
   current = this.tail;
   this.tail=  current.prev;
   this.tail.next = undefined;
 }
...

③正常移除

...
else  {
    current = this.getElementAt(index);
    const prevElement = current.prev;
    const nextElement = current.next;
    prevElement.next =  nextElement;
    nextElement.prev = prevElement;
}
...

整理一下:

 removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = this.head.next;
        // if there is only one item, then we update tail as well //NEW
        if (this.count === 1) {
          // {2}
          this.tail = undefined;
        } else {
          this.head.prev = undefined;
        }
      } else if (index === this.count - 1) {
        // last item //NEW
        current = this.tail;
        this.tail = current.prev;
        this.tail.next = undefined;
      } else {
        current = this.getElementAt(index);
        const previous = current.prev;
        // link previous with current's next - skip it to remove
        previous.next = current.next;
        current.next.prev = previous; // NEW
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }

循环链表

循环链表有单向循环链表和双向循环链表。

单向循环链表和单向链表的区别在于最后一个元素的next不是指向undefined,而是指向了head。

[JS与链表]双向链表

双向循环链表是双向链表多了指向head元素的tail.next(原本是undefined)和指向tail元素的head.prev(原本是undefined)

[JS与链表]双向链表
单向循环链表CircularLinkedList实现:

CircularLinkedList类不需要任何额外的属性。直接扩展LinkedList类(单向链表)并覆盖插入方法和移除方法。

向单向循环链表中插入元素的逻辑和向单向链表中插入元素的逻辑是一样的。不同之处在于我们需要将循环链表尾部节点的next引用指向头部节点。

单向链表:

  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }

循环单向链表:

insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      let current = this.head;
      if (index === 0) {
        if (this.head == null) {
          // if no node  in list
          this.head = node;
          node.next = this.head;
        } else {
          node.next = current;
          current = this.getElementAt(this.size());
          // update last element
          this.head = node;
          current.next = this.head;
        }
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
  }
[JS与链表]双向链表

其实就是多了在插入下标为0的情况处理

单向链表:

removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        this.head = current.next;
      } else {
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
 }

单向循环链表:

removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head;
      if (index === 0) {
        if (this.size() === 1) {
          this.head = undefined;
        } else {
          const removed = this.head;
          current = this.getElementAt(this.size() - 1);
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
        // no need to update last element for circular list
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
[JS与链表]双向链表

详细代码见:链表代码汇总

有序链表

有序链表是指保持元素有序的链表结构。除了使用排序算法之外。我们还可以将元素插入到正确的位置来保证链表的有序性。

所以我们只需要在单向链表的基础上重写insert、push的逻辑,使得整个链表的插入变得有序。

insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element);
      if (index === 0) {
        const current = this.head;
        node.next = current;
        this.head = node;
      } else {
        const previous = this.getElementAt(index - 1);
        node.next = previous.next;
        previous.next = node;
      }
      this.count++;
      return true;
    }
    return false;
 }

原本的插入逻辑可以自定义插入的位置。但是有序插入只能通过计算得出插入下标。

为了提现有序,我们需要定义一套比较方法。

export const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
export function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
export default class SortedLinkedList extends LinkedList {
  constructor(equalsFn, compareFn = defaultCompare) {
    super(equalsFn);
    this.compareFn = compareFn;
  }
}

我们来看insert的改写:

  insert(element, index = 0) {
    if (this.isEmpty()) {
      return super.insert(element, index === 0 ? index : 0);
    }
    const pos = this.getIndexNextSortedElement(element);
    return super.insert(element, pos);
  }

insert方法为什么要给insert一个默认值0?

因为我们需要继承改写insert方法(super),所以我们不能改变继承的insert的传参结构。但是我们又不能让index生效。

getIndexNextSortedElement的方法是为了纠正插入元素的下标的

getIndexNextSortedElement(element) {
    let current = this.head;
    let i = 0;
    for (; i < this.size() && current; i++) {
      const comp = this.compareFn(element, current.element);
      if (comp === Compare.LESS_THAN) {
        return i;
      }
      current = current.next;
    }
    return i;
  }

同理,push也需要纠正一下push的下标

push(element) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
 }

完整代码见链表代码汇总

小结:

链表相比数组最重要的优点是无需移动链表中的元素,就能轻松添加和移除元素。当你需要频繁操作(删、增)元素的时候,最好的选择就是链表。文章来源地址https://www.toymoban.com/news/detail-450947.html

到了这里,关于[JS与链表]双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构—LinkedList与链表

    目录 一、链表 1. 链表的概念及结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 二.LinkedList的使用  1.LinkedList概念及结构 2. LinkedList的构造 3. LinkedList的方法 三. ArrayList和LinkedList的区别           链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑

    2024年02月04日
    浏览(51)
  • 数组与链表的区别

    数组是连续存储,数组在创建时需要一个整块的空间。 链表是链式存储,链表在内存空间中不一定是连续的。 数组一般创建在栈区,链表一般创建在堆区,在增加节点时需要new或malloc新节点,相较于数组长度不固定,自由度高。 数组可以通过下标随机访问,单向链表只能通

    2024年02月05日
    浏览(73)
  • 【数据结构】LinkedList与链表

    上节课已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素: 由于其底层是一段连续空间,当 在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此A rrayLi

    2024年02月07日
    浏览(44)
  • 顺序表与链表的区别

    目录 一、顺序表和链表的比较 顺序表 优点: 缺点: 链表 优点 缺点 二、顺序表和链表的区别 1.顺序表和链表都具有增、删、查、改功能,但算法复杂度却不相同。 2、从数据元素存储的内存角度来看 三、顺序表与链表选取方案 顺序表的特点是逻辑上相邻数据元素,物理存

    2024年02月08日
    浏览(122)
  • 【算法系列篇】与链表相关的算法

    链表是我们在日常生活中使用较为广泛的一种数据结构,链表因为其可扩展性高和方便插入、删除的特性在一些领域发挥着很大的作用。但是因为链表独特的结构,在内存上的逻辑连续而不是物理连续的特性,也使得当一些算法的作用对象是链表的时候就有些许的差别,那么

    2024年02月08日
    浏览(24)
  • 中间件存储设计 - 数组与链表

    中间件主要包括如下三方面的基础:数据结构、JUC 和 Netty,接下来,我们先讲数据结构。 数据结构主要解决的是数据的存储方式问题,是程序设计的基座。 按照重要性和复杂程度,我选取了数组和链表、键值对 (HashMap)、红黑树、LinkedHashMap 和 PriorityQueue 几种数据结构重点解

    2024年01月23日
    浏览(45)
  • C语言链表的含义与链表数据操作代码详解!

            在讲解开始前,我们先来看一张图片:         如图我们可以看到一列火车,它由车头和车厢组成,同时由链条连接,从整个火车我们可以看出,前一节的车厢尾总有着一个链条,让它紧密与后一个车厢相连。这样,如果我们找到了前一个车厢,那么我们就可以同

    2024年04月23日
    浏览(39)
  • 数据结构(Java实现)LinkedList与链表(上)

    链表 逻辑结构 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。 无头双向链表:在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。 链表的实现 创建一个链表 遍历单链表 、 得到

    2024年02月11日
    浏览(52)
  • 数据结构(Java实现)LinkedList与链表(下)

    ** ** 结论 让一个指针从链表起始位置开始遍历链表,同时让一个指针从判环时相遇点的位置开始绕环运行,两个指针都是每次均走一步,最终肯定会在入口点的位置相遇。 LinkedList的模拟实现 单个节点的实现 尾插 运行结果如下: 也可以暴力使用 全部代码 MyLinkedList IndexOut

    2024年02月11日
    浏览(45)
  • 《数据结构与算法》之队列与链表复习

    我们在上一次学习了堆栈的数据结构以后,可以了解到它是受限制的操作,比如我们操作只能在栈顶,现在我们要学习的东西叫做队列,它也是受限制的一种数据结构,它的特点是队头只出数据,而队尾只入数据, 它的结构就和它的名字,像我们平时排队一样先来的人肯定要

    2024年02月08日
    浏览(65)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包