算法 - ts实现链表 - 《数据结构与算法》

创建链表
向链表尾部添加元素
循环迭代链表直到目标位置
从链表中移除元素
链表包含元素个数
判断链表是否为空
获取元素在链表索引
从链表中移除元素
向链表插入元素
返回整个链表的字符串
js版本

要存储多个元素,数组可能是最常用的数据结构,但是数组有个缺点是他的大小是固定的,从数组的起点或中间插入或移除项的成本很高,因为需要移动元素.而相对于传统的数组,链表的一个好处在于,添加或移除原属的时候不需要移动其他元素.因为链表使用的是指针,所以当我们要访问链表中间的一个元素的时候,我们需要从起点(表头)开始迭代链表,而不能像数组一样直接访问任何位置的任何元素.
因为链表不是ts的基础数据类型,所以想通过ts去实现一个链表的类.

创建链表

以下是LinkedList类的骨架:

class LinkedList<T> {
  /**
   * 用来存储链表中的元素数量
   */
  protected count = 0;
  /**
   * 保存引用,由于链表是动态的,需要将第一个元素的引用保存下来
   * Node助手类,表示我们想要添加到链表的项
   */
  protected head: Node<T> | undefined;
  constructor() {}
/**
 * 比较链表中的元素是否相等
 * @param a
 * @param b
 * @returns boolean
 */
  equalsFn<T>(a: T, b: T): boolean {
    return a === b;
  }
}

助手类Node:通过这个类,我们可以很好的处理我们想要实现的链节点的类型和结构

/**
 * 想要添加到链表的项
 */
export class Node<T> {
  /**
   * @param element 要加入链表元素的值
   * @param next 指向链表中下一个元素的指针
   */
  constructor(public element: T, public next?: Node<T>) {}
}

接下来要实现的是LinkedList类的方法:

push(element):向链表尾部添加一个元素;
insert(element,position):向链表的特定位置插入一个新元素;
getElementAt(index):返回链表中特定位置的元素.如果链表中不存在这样的元素,则返回undefined;
remove(element):从链表中移除一个元素;
indexOf(element):返回元素在链表中的索引,如果链表中没有该元素则返回-1;
removeAt(position):从链表的特定位置移除一个元素;
isEmpty():如果链表中不包含任何元素,返回true,如果链表长度大于0则返回false;
size():返回链表包含的元素个数,与数组的length属性类似;

toString():返回表示整个链表的字符串.由于列表项使用了Node类,就需要重写继承自JavaScript对象默认的toString方法.让其只输出元素的值;

向链表尾部添加元素

push(element: T) {
  // 创建Node项
  const node = new Node(element);
  // 指向链表current项的变量
  let current;
  // head元素为undefined或null,意味向链表添加第一个元素
  if (this.head == null) {
    //  head指向node元素,node.next为null
    this.head = node;
  } else {
    // 链表不为空
    current = this.head;
    // 循环访问链表,直到找到最后一项,最后一项的next为null
    while (current.next != null) {
      current = current.next;
    }
    // 最后一项next指向node
    current.next = node;
  }
  // 递增链表的长度
  this.count++;
}

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

/**
 * 循环迭代链表直到目标位置
 * @param index 目标索引
 * @returns undefeated||Node
 */
getElementAt(index: number) {
  // 检查越界值
  if (index >= 0 && index <= this.count) {
    // 初始化current,从head开始
    let current = this.head;
    // 循环至index
    for (let i = 0; i < index && current != null; i++) {
      current = current.next;
    }
    return current;
  }
  return undefined;
}

从链表中移除元素

移除元素,参数为元素在链表的位置

/**
 * 从链表移除元素
 * @param index 要移除的元素位置
 * @returns undefined||element
 */
removeAt(index: number) {
  // 检查越界值
  if (index >= 0 && index < this.count) {
    // 对链表中第一个元素的引用
    let current = this.head;
    // 移除第一项
    if (index === 0) {
      this.head = current.next;
    } else {
      // 获取指定位置的元素
      const previous = this.getElementAt(index - 1);
      // previous.next为要移除的元素
      current = previous.next;
      // 移除元素的next赋予previous.next,current会被丢弃在内存中,等着被垃圾回收器处理
      previous.next = current.next;
    }
    // 减小链表长度
    this.count--;
    return current.element;
  }
  return undefined;
}

链表包含元素个数

该方法可以当做工具方法,因为count是protected,对外部是不可获取的,所以需要通过方法return出去,同时后面几个方法也是都有使用到

size() {
  return this.count;
}

判断链表是否为空

跟size同样是工具方法,直接使用size去判断长度是否为0

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

获取元素在链表索引

/**
 *
 * @param element 获取index的元素
 * @returns -1~
 */
indexOf(element: T) {
  let current = this.head;
  // 循环迭代比较是否是要查找的元素,返回index
  for (let i = 0; i < this.size() && current != null; i++) {
    if (this.equalsFn(element, current.element)) {
      return i;
    }
    current = current.next;
  }
  // 迭代完找不到返回-1
  return -1;
}

从链表中移除元素

/**
 * 从链表中移除元素
 * @param element 所要移除的元素
 * @returns undefined||element
 */
remove(element: T) {
  // 使用indexOf查找到该元素在链表的索引
  const index = this.indexOf(element);
  // 使用索引来移除元素
  return this.removeAt(index);
}

向链表插入元素

/**
 * 向链表的特定位置插入新元素
 * @param element 所要插入的元素
 * @param index 元素插入位置
 * @returns boolean
 */
insert(element: T, index: number) {
  // 排除临界值
  if (index >= 0 && index <= this.count) {
    // 新建Node类型
    const node = new Node(element);
    //在表头插入
    if (index === 0) {
      // 常规链表插入方式 head=>current,current=>node.next,node=>head
      const current = this.head;
      node.next = current;
      this.head = node;
    } else {
      // 非表头插入,获取插入点前一个node
      const previous = this.getElementAt(index - 1);
      node.next = previous.next;
      previous.next = node;
    }
    this.count++;
    return true;
  }
  // index超出临界值
  return false;
}

返回整个链表的字符串

// 返回整个链表的字符串
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;
}

js版本

下面的为js版本,不用进行编译,方便运行

class Node {
constructor(element, next) {
  this.element = element;
  this.next = next;
}
}
class LinkedList {
constructor() {
  this.count = 0;
  this.head = undefined;
}
equalsFn(a, b) {
  return a === b;
}

push(element) {
  const node = new Node(element);
  let current;
  if (this.head == null) {
    // catches null && undefined
    this.head = node;
  } else {
    current = this.head;
    while (current.next != null) {
      current = current.next;
    }
    current.next = node;
  }
  this.count++;
}
getElementAt(index) {
  if (index >= 0 && index <= this.count) {
    let node = this.head;
    for (let i = 0; i < index && node != null; i++) {
      node = node.next;
    }
    return node;
  }
  return undefined;
}
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;
}
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;
}
remove(element) {
  const index = this.indexOf(element);
  return this.removeAt(index);
}
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;
}
isEmpty() {
  return this.size() === 0;
}
size() {
  return this.count;
}
getHead() {
  return this.head;
}
clear() {
  this.head = undefined;
  this.count = 0;
}
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;
}
}