七、Typescript数据结构与算法-双向链表

双向链表

既可以从头遍历到尾, 又可以从尾遍历到头.

一个节点既有向前连接的引用 prev, 也有一个向后连接的引用 next.

缺点

• 每次在插入或删除某个节点时, 需要处理四个引用, 而不是两个. 也就是实现起来要困难一些
• 并且相当于单向链表, 必然占用内存空间更大一些.
• 但是这些缺点和我们使用起来的方便程度相比, 是微不足道的

还是继承自单向链表

import ILinkedList from "./ILinkedList";
import { Node } from "./Node";
export default class LinkedList<T> implements ILinkedList<T> {
  // protected 子类可访问
  protected head: Node<T> | null = null;
  protected length: number = 0;
  protected tail: Node<T> | null = null;
  get size() {
    return this.length;
  }
  private isTail(node: Node<T>) {
    return this.tail === node;
  }
  // 根据下标获取节点
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) current = current.next;
    return current;
  }
  // 追加元素 重构
  append(value: T): void {
    const node = new Node(value);
    if (!this.head) {
      this.head = node;
    } else {
      // let current = this.head;
      // while (current.next) current = current.next;
      // current.next = node;
      this.tail!.next = node;
    }
    this.tail = node;
    this.length++;
  }
  // 遍历
  traverse(): string {
    const value: T[] = [];
    let current = this.head;
    while (current) {
      value.push(current.val);
      // 针对循环链表 避免无限循环打印
      if (this.isTail(current)) {
        current = null;
      } else {
        current = current.next;
      }
    }
    // 针对循环链表
    if (this.tail!.next === this.head) value.push(this.head!.val);
    return value.join("->");
  }
  peek() {
    return this.head?.val;
  }
  // 下标插入
  insert(value: T, position: number): boolean {
    // 判断越界
    if (position < 0 || position > this.size) return false;
    // 添加到第一个位置
    const newNode = new Node(value);
    let current = this.head;
    if (position === 0) {
      this.head = newNode;
      newNode.next = current;
    } else {
      const previous = this.getNode(position - 1);
      newNode.next = previous!.next;
      previous!.next = newNode;
      if (position === this.length) this.tail = newNode;
    }
    this.length++;
    return true;
  }
  // 删除指定元素
  removeAt(position: number): T | null {
    // 越界
    if (position < 0 || position > this.size) return null;
    let current = this.head;
    let remove: Node<T> | null = null;
    // 删除head
    if (position === 0) {
      this.head = current?.next ?? null;
      if (this.length === 1) {
        this.head = null;
        this.tail = null;
      }
    } else {
      const previous = this.getNode(position - 1);
      remove = previous!.next;
      previous!.next = previous?.next?.next ?? null;

      if (position === this.length - 1) {
        this.tail = previous;
      }
    }
    this.length--;
    return remove?.val ?? null;
  }
  get(position: number): T | null {
    if (position < 0 || position > this.size) return null;
    return this.getNode(position)?.val ?? null;
  }
  // 更新指定位置节点
  update(value: T, position: number): boolean {
    if (position < 0 || position > this.size) return false;
    this.getNode(position)!.val = value;
    return true;
  }
  indexOf(value: T): number {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.val === value) return index;
      if (this.isTail(current)) {
        current = null;
      } else {
        current = current.next;
      }
      index++;
    }
    return -1;
  }
  // 删除指定value的节点
  remove(value: T): T | null {
    return this.removeAt(this.indexOf(value));
  }
  isEmpty(): boolean {
    return this.length === 0;
  }
}
export {};

双向链表实现

双向链表中添加、删除方法的实现和单向链表有较大的区别，可以对其方法进行重新实现：

• append 方法：在尾部追加元素
• prepend 方法：在头部添加元素
• postTraverse 方法：从尾部遍历所有节点
• insert 方法：根据索引插入元素
• removeAt 方法：根据索引删除元素

export class Node<T> {
  next: Node<T> | null = null;
  constructor(public val: T) {
    this.val = val;
  }
}

export class DoubleNode<T> extends Node<T> {
  pre: DoubleNode<T> | null = null;
  next: DoubleNode<T> | null = null;
}

append

class DoubleLinkList<T> extends LinkedList<T> {
  /**
   * 重写
   * 因为父类head tail是Node类 子类是DoubleNode类
   */
  protected head: DoubleNode<T> | null = null;
  protected tail: DoubleNode<T> | null = null;
  append(value: T): void {
    const newNode = new DoubleNode(value);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.pre = this.tail;
      this.tail = newNode;
    }
  }
}

prepend 方法：在头部添加元素

// prepend方法：在头部添加元素
  prepend(value: T) {
    const newNode = new DoubleNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.tail!.prev = newNode;
      this.head = newNode;
    }
  }

postTraverse 方法：从尾部遍历所有节点

// postTraverse方法：从尾部遍历所有节点
  postTraverse() {
    let current = this.tail;
    const value: T[] = [];
    while (current) {
      value.push(current.val);
      current = current.prev;
    }
    return value.join("->");
  }

insert 方法：根据索引插入元素

insert(value: T, position: number): boolean {
    if (position < 0 || position > this.length) return false;

    if (position === 0) this.prepend(value);
    else if (position === this.length) this.append(value);
    else {
      const newNode = new DoubleNode(value);
      const current = this.getNode(position) as DoubleNode<T>;

      newNode.next = current;
      current.prev!.next = newNode;
      newNode.prev = current.prev;
      current.prev = newNode;
      this.length++;
    }

    return true;
  }

removeAt 方法：根据索引删除元素

removeAt(position: number): T | null {
    let current = this.head;
    if (position < 0 || position >= this.length) return null;
    // 删除第一个节点
    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail === null;
      } else {
        this.head = this.head!.next;
        this.head!.prev = null;
      }
      // 删除最后节点
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail!.prev;
      this.tail!.next = null;
      // 删除中间节点
    } else {
      current = this.getNode(position) as DoubleNode<T>;
      current.prev!.next = current.next;
      current.next!.prev = current.prev;
    }
    return current?.val ?? null;
  }

注意边界问题 position 是从 0 开始

完整代码

import LinkedList from "./01_单向链表-重构";
import { DoubleNode } from "./Node";
class DoubleLinkList<T> extends LinkedList<T> {
  /**
   * 重写
   * 因为父类head tail是Node类 子类是DoubleNode类
   */
  protected head: DoubleNode<T> | null = null;
  protected tail: DoubleNode<T> | null = null;
  append(value: T): void {
    const newNode = new DoubleNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail!.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
  }
  // prepend方法：在头部添加元素
  prepend(value: T) {
    const newNode = new DoubleNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.length++;
  }
  // postTraverse方法：从尾部遍历所有节点
  postTraverse() {
    let current = this.tail;
    const value: T[] = [];
    while (current) {
      value.push(current.val);
      current = current.prev;
    }
    return value.join("->");
  }

  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.length) return false;

    if (position === 0) this.prepend(value);
    else if (position === this.length) this.append(value);
    else {
      const newNode = new DoubleNode(value);
      const current = this.getNode(position) as DoubleNode<T>;

      newNode.next = current;
      current.prev!.next = newNode;
      newNode.prev = current.prev;
      current.prev = newNode;
      this.length++;
    }

    return true;
  }
  removeAt(position: number): T | null {
    let current = this.head;
    console.log(position, this.length);
    if (position < 0 || position >= this.length) return null;
    // 删除第一个节点
    if (position === 0) {
      if (this.length === 1) {
        this.head = null;
        this.tail === null;
      } else {
        this.head = this.head!.next;
        this.head!.prev = null;
      }
      // 删除最后节点
    } else if (position === this.length - 1) {
      current = this.tail;
      this.tail = this.tail!.prev;
      this.tail!.next = null;
      // 删除中间节点
    } else {
      current = this.getNode(position) as DoubleNode<T>;
      current.prev!.next = current.next;
      current.next!.prev = current.prev;
    }
    return current?.val ?? null;
  }

  indexOf(value: T): number {
    return super.indexOf(value);
  }
  isEmpty(): boolean {
    return super.isEmpty();
  }
  remove(value: T): T | null {
    console.log(this.indexOf(value));
    return this.removeAt(this.indexOf(value));
  }

  update(value: T, position: number): boolean {
    return super.update(value, position);
  }
}

const dLinkList = new DoubleLinkList();
dLinkList.append("AAA");
dLinkList.append("BBB");
dLinkList.append("CCC");
dLinkList.append("DDD");
dLinkList.prepend("ABC");
dLinkList.prepend("ACB");

dLinkList.insert("000", 0);
dLinkList.insert("999", 7);
dLinkList.insert("333", 3);
// console.log(dLinkList.traverse());
// console.log(dLinkList.postTraverse());

// dLinkList.removeAt(0);
// dLinkList.removeAt(8);
// dLinkList.removeAt(2);
console.log(dLinkList.traverse());

// console.log(dLinkList.indexOf("CCC"));
// console.log(dLinkList.isEmpty());
dLinkList.remove("999");
dLinkList.update("GGG", 2);
console.log(dLinkList.traverse());