数据结构与算法学习之有序链表

有序链表

有序链表是指从头节点开始到链表结尾，链表中的数据项按照某种顺序有序排列的链表结构。

实现有序链表

定义节点类

class Node {
    constructor(element) {
      this.element = element;
    this.next = undefined;
  }
}

定义比较常量

const COMPARE = {
    LESS_THAN: -1,
  BIGER_THAN: 1
}

定义比较函数

const defaultEquals = (a, b) => {
  return a === b;
}
const defaultCompare = (a, b) => {
    if (a === b) {
      return 0;
  }
  return a < b ? COMPARE.LESS_THAN : COMPARE.BIGER_THAN;
}

定义有序链表类

class SortedLinkedList {
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
      this.count = 0;
    this.head = undefined;
    this.equalsFn = equalsFn;
    this.compareFn = defaultCompare;
  }
}

接下来，我们为链表定义一些链表的方法：
append(element) 向有序链表尾部添加一个新元素
insert(element, index) 向有序链表的特定位置插入一个新元素
getElementAt(index) 返回有序链表中特定位置的元素，若元素不存在，返回 undefined
remove(element) 从有序链表中移除一个元素
removeAt(index) 从现有链表的特定位置移除一个元素
removeHead() 移除首节点
removeTail() 移除尾结点
indexOf(element) 返回指定元素在有序链表中的索引，若没有该元素则返回 -1
head() 返回首节点
tail() 返回尾结点
size() 返回有序链表包含的元素个数，即返回链表的长度
isEmpty() 判断有序链表是否为空
clear() 清空有序链表
toString() 返回表示整个有序链表的字符串

下面，我们逐一实现这些方法：

append 向有序链表尾部添加一个新元素

append(element) {
    if (this.isEmtpy()) {
  } else {
      const index = this.getIndexNextSortedElement(element)
  }
}

insert 向有序链表的特定位置插入一个新元素

getElementAt 返回有序链表中特定位置的元素，若元素不存在，返回 undefined

remove 从有序链表中移除一个元素

removeAt 从现有链表的特定位置移除一个元素

removeHead 移除首节点

removeTail 移除尾结点

indexOf 返回指定元素在有序链表中的索引，若没有该元素则返回 -1

head 返回首节点

tail 返回尾结点

size 返回有序链表包含的元素个数，即返回链表的长度

isEmpty 判断有序链表是否为空

clear 清空有序链表

toString 返回表示整个有序链表的字符串