资讯专栏INFORMATION COLUMN

Javascript数据结构与算法(二)循环链表与有序链表

YacaToy / 905人阅读

摘要:循环链表可以像单向链表引用,也可以像双向链表有双向引用。以下就以如何创建栈数据结构为例。

循环链表可以像单向链表引用,也可以像双向链表有双向引用。性能上也跟双向链表差不多,如果position大于length/2,那就可以从尾部开始迭代,可以减少迭代的元素。唯一的区别在于最后一个元素指向下一个元素的指针(tail.next)不是undefine,而是第一个元素(head)。接下来来看一下循环链表的代码

循环链表 创建循环链表
class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
  }
添加操作 尾插法
push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.getElementAt(this.size() - 1);
      current.next = node;
    }
    // set node.next to head - to have circular list
    node.next = this.head;
    this.count++;
  }
任意位置添加元素
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;
  }
删除操作 删除任意位置元素
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;
  }
}

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

有序链表 创建有序链表
const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};
function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
};
function defaultEquals(a, b) {
  return a === b;
};
class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn);
    this.equalsFn = equalsFn;
    this.compareFn = compareFn;
};
查询操作
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(element) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
  }
任意位置有序添加元素
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);
  }

以上就是常见的四种链表结构,当然我们也可以使用链表实现其他数据结构,例如栈,队列,双向队列。以下就以如何创建栈数据结构为例。

链表创建栈数据结构
class StackLinkedList {
  constructor() {
    this.items = new DoublyLinkedList();
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items.removeAt(this.size() - 1);
    return result;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items.getElementAt(this.size() - 1).element;
  }

  isEmpty() {
    return this.items.isEmpty();
  }

  size() {
    return this.items.size();
  }

  clear() {
    this.items.clear();
  }

  toString() {
    return this.items.toString();
  }
}
总结

链表相对数组最大的优点就是无需移动链表中的元素,就能轻松的添加和移除元素,所以需要实现添加和移除元素操作时,最好的选择是链表而非数组。

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

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

相关文章

  • 数据结构》第章 | 线性表 知识梳理(应对期末考)

    摘要:案例引入一元多项式的运算了解每一项的指数与其在线性表中的对应关系。线性表的链式表示又称为非顺序映像或链式映像。问题三头结点的数据域内装的是什么答头结点的数据域可以为空,也可存放线性表长度等附加信息,但此结点不能计入链表长度值。 ...

    ChanceWong 评论0 收藏0
  • 叉树那些事儿

    摘要:大家在聊到二叉树的时候,总会离不开链表。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。存储结构线性表主要由顺序表示或链式表示。链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。 大家在聊到二叉树的时候,总会离不开链表。这里先带大家一起了解一些基本概念。 线性表 概念 线性表是最基本、最简单、也是最常用的一种数据结构。 线性表中数据元素之间的关...

    Little_XM 评论0 收藏0
  • JavaScript 数据结构算法之美 - 线性表(数组、栈、队列、链表

    摘要:每个线性表上的数据最多只有前和后两个方向。数组链表队列栈等就是线性表结构。非线性表数据之间并不是简单的前后关系。不包含任何元素的栈称为空栈。移除栈顶的元素,同时返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言 基础知识就像是一座大楼的地基,它决定了我们的技术高度。 我们应该多掌握一些可移值的...

    kaka 评论0 收藏0
  • [个人心得]数据结构之双链表

    摘要:一般我们都构造双向循环链表。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。单向循环链表双向循环链表单向循环链表是在单链表基础上,将最后一个节点的指针指向链表头。 维基百科 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构...

    jokester 评论0 收藏0
  • [ JavaScript ] 数据结构算法 —— 链表

    摘要:每个元素由一个存储元素本身的节点和一个指向下一个元素的引用也称指针或链接组成。相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。 本篇主要有三部分 什么是链表 链表的实现 链表的变种 源码地址:https://github.com/yhtx1997/S... 另外,今天2019年2月18日上午发现 20...

    wfc_666 评论0 收藏0

发表评论

0条评论

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