双向链表

封装思想

implements

默认能打印树结构是因为它有对应属性 left、right、value，但是如果别人定义的和对应属性不符合则无法打印

可以使用 implements 实现对应接口，之后通过 get 方法控制其展示内容

class Node<T> {
  data: T
  constructor(value: T) {
    this.data = value
  }
}
interface PrintableNode {
  left: PrintableNode | null
  right: PrintableNode | null
  value: any
}
class TreeNode<T> extends Node<T> implements PrintableNode {
  left: TreeNode<T> | null = null
  right: TreeNode<T> | null = null
  get value() {
    const data = this.data as Product
    return `${data.name}-${data.price}`
  }
}
class BSTree<T> {
  private root: TreeNode<T> | null = null
  print() {
    btPrint(this.root)
  }
}
class Product {
  constructor(public name: string, public price: number) {}
  valueOf() {
    return this.price
  }
}
const bst = new BSTree<Product>()

大小比较

JS 取巧的方式

class Product {
  constructor(public name: string, public price: number) {}
  valueOf() {
    return this.price
  }
}
const bst = new BSTree<Product>()

Java 里一般会采取如下方式进行比较

interface IComparator<T> {
  (c1: T, c2: T): number
}
class BSTree<T> {
  private comparator: IComparator<T>
  constructor(comparator: IComparator<T>) {
    this.comparator = comparator
  }
  private searchNode(value: T): TreeNode<T> | null {
    let current = this.root
    let parent: TreeNode<T> | null = null
    while (current) {
      if (current.data === value) return current
      parent = current
      // 使用比较器进行比较
      if (this.comparator(current.data, value)) {
        current = current.right
      } else {
        current = current.left
      }
      if (current) current.parent = parent
    }
    return null
  }
}
class Product {
  constructor(public name: string, public price: number) {}
}
const bst = new BSTree<Product>((c1, c2) => {
  return c1.price - c2.price
})

认识循环链表

循环链表（Circular LinkedList）是一种特殊的链表数据结构:

• 在普通链表的基础上，最后一个节点的下一个节点不再是 null，而是指向链表的第一个节点
• 这样形成了一个环，使得链表能够被无限遍历
• 这样，我们就可以在单向循环链表中从任意一个节点出发，不断地遍历下一个节点，直到回到起点

重构单向链表

为什么要重构？是为了让循环链表继承自 LinkedList

• 增加 tail 属性

class LinkedList<T> implements ILinkedList<T> {
  protected tail: Node<T> | null = null
  private isTail(node: Node<T>) {
    return this.tail === node
  }
  append(value: T) {
    if (this.head) {
      this.tail!.next = newNode
    }
    this.tail = newNode
  }
  insert(value: T, position: number) {
    if (position === this.length) {
      this.tail = newNode
    }
  }
  removeAt(position: number) {
    if (position === 0) {
      if (this.length === 1) {
        this.tail = null
      }
    } else {
      if (position === this.length - 1) {
        this.tail = previous
      }
    }
  }
  traverse() {
    while (current) {
      if (this.isTail(current)) {
        current = null
      } else {
        current = current.next
      }
    }
    if (this.head && this.tail?.next === this.head) {
      values.push(this.head.value)
    }
  }
  indexOf(value: T) {
    while (current) {
      if (this.isTail(current)) {
        current = null
      } else {
        current = current.next
      }
    }
  }
}

循环链表实现

有些方法需要在单向链表基础上重新实现一下

class CircularLinkedList<T> extends LinkedList<T> {
  append(value: T): void {
    super.append(value)
    this.tail!.next = this.head
  }
  insert(value: T, position: number): boolean {
    const isSuccess = super.insert(value, position)
    if (isSuccess && (position === this.length - 1 || position === 0)) {
      this.tail!.next = this.head
    }
    return isSuccess
  }
  removeAt(position: number): NonNullable<T> | null {
    const value = super.removeAt(position)
    if (value && this.tail && (position === 0 || position === this.length)) {
      this.tail!.next = this.head
    }
    return value
  }
}

认识双向链表

双向链表:

• 既可以从头遍历到尾,又可以从尾遍历到头
• 也就是链表相连的过程是双向的
• 一个节点既有向前连接的引用 previous, 也有一个向后连接的引用 next

双向链表有什么缺点呢？

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

节点封装

双向链表的节点，需要进一步添加一个 prev 属性，用于指向前一个节点

class Node<T> {
  value: T
  next: Node<T> | null = null
  constructor(value: T) {
    this.value = value
  }
}
export class DoublyNode<T> extends Node<T> {
  prev: DoublyNode<T> | null = null
  next: DoublyNode<T> | null = null
}

双向链表实现

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

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

class DoublyLinkedList<T> extends LinkedList<T> {
  protected head: DoublyNode<T> | null = null
  protected tail: DoublyNode<T> | null = null
  append(value: T): void {
    const newNode = new DoublyNode(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(value: T): void {
    const newNode = new DoublyNode(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() {
    const values: T[] = []
    let current = this.tail
    while (current) {
      values.push(current.value)
      current = current.prev
    }
    console.log(values.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 DoublyNode(value)
      const current = this.getNode(position) as DoublyNode<T>
      current.prev!.next = newNode
      newNode.next = current
      newNode.prev = current.prev
      current.prev = newNode
      this.length++
    }
    return true
  }
  removeAt(position: number): NonNullable<T> | null {
    if (position < 0 && position >= this.length) return null
    let current = this.head
    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 DoublyNode<T>
      current.next!.prev = current.prev
      current.prev!.next = current.next
    }
    this.length--
    return current?.value ?? null
  }
}