// 双向链表

// 节点
export class Node2 {
  [x: string]: any;
  constructor(data: any) {
    this.data = data; // 数据
    this.next = null; // 指向下一个节点的指针
    this.prev = null; // 指向上一个节点
  }
}

// 双向链表
export class LinkedList2 {
  [x: string]: any;
  constructor(head: any = null) {
    if (head) {
      this.head = new Node2(head);
    } else {
      this.head = null;
    }
  }
  // 添加节点(尾部添加)
  append(data: any) {
    const newNode = new Node2(data);
    const currNode = this.getLast();
    if (currNode) {
      currNode.next = newNode;
      newNode.prev = currNode;
    } else {
      this.head = newNode;
    }
  }
  // 查找节点
  find(data: any) {
    let currNode = this.head;
    while (currNode && currNode.data !== data) {
      currNode = currNode.next;
    }
    return currNode;
  }
  // 插入节点
  // target:链表中存在的节点值
  // data:要插入的节点值
  // data插入的位置在target的后面
  insert(target: any, data: any) {
    const tagNode = this.find(target);
    if (!tagNode) return; // 如果目标节点不存在，则返回
    const newNode = new Node2(data);

    if (tagNode.next) {
      newNode.next = tagNode.next;
      newNode.prev = tagNode;
      tagNode.next = newNode;
      newNode.next.prev = newNode;
    } else {
      // 如果目标节点是最后一个节点
      tagNode.next = newNode;
      newNode.prev = tagNode;
    }
  }
  // 返回链表的最后一个节点
  getLast() {
    let lastNode = this.head;
    if (lastNode) {
      while (lastNode.next) {
        lastNode = lastNode.next;
      }
    }
    return lastNode;
  }
  // 转数组
  toArr() {
    let p = this.head;
    const arr = [];
    while (p) {
      arr.push(p.data);
      p = p.next;
    }
    return arr;
  }
}