JS数据结构-双向链表

//先定义节点类
class Node {
    constructor(data) {
        this.value = data
        this.next = null
    }
}

// 定义链表
class LinkedList {
    head = null
    count = 0

    // 1.添加节点
    push(element) {
        let node = new Node(element)
        //判断是否为空
        if (this.head === null) {
            //链表为空 新加的节点就是头
            this.head = node
        } else {
            let current = this.head
            while (current.next) {       //while循环到最后一个节点
                current = current.next
            }
            current.next = node
        }
        this.count++
    }
    // 2.删除指定位置的节点: xyz x.next = y.next 删除y
    removeAt(position) {
        if (position >= 0 && position < this.count) {
            let current = this.head
            if (position === 0) {
                this.head = this.head.next
            } else {
                let previous = null
                for (let i = 0; i < position; i++) {
                    previous = current        //不断往右移动
                    current = current.next
                }
                previous.next = current.next
                current.next = null
            }
            this.count--
            return current
        }
        return;
    }
    // 3.在指定位置插入一个节点
    insert(element, position) {
        if(position<0||position>this.count) return false
        let node = new Node(element)
        if (position === 0) {
            node.next = this.head
            this.head = node
        }else if(position === this.count){
            this.push(element)
        }else{
            let previous = this.head
            for(let i =0;i<position-1;i++){
                previous = previous.next
            }
            node.next = previous.next
            previous.next = node
        }
        this.count++
        return true
    }
    // 4.获取指定位置的节点
    getElementAt(index){
        if(index<0 || index>this.count) return undefined
        else{
            let current = this.head
            for(let i=0;i<index-1;i++){
                current = current.next
            }
            return current
        }
    }
    // 5.返回某个节点的下标
    indexOf(element){
        let current = this.head
        for(let i=0;i<this.count;i++){
            if(this.isEqual(current.value,element)){
                return i
            }
            current = current.next
        }
        return -1
    }
    // ** 封装一个递归判断相等的函数 这里暂时先用JSON.stringify **
    isEqual(a,b){
        return JSON.stringify(a)===JSON.stringify(b)
    }
    // 6.从链表中删除一个元素
    remove(element){
        const index = this.indexOf(element)
        return this.removeAt(index)
    }
    // 7.获取链表的大小
    size(){
        return this.count
    }
    // 8.判断是否为空
    isEmpty(){
        return this.count===0
    }
    // 9.重写toString方法输出所有值
    toString(){
        let str = ''
        let current = this.head
        for(let i=0;i<this.count;i++){
            str+=String(current.value)
            current = current.next
        }
        return str
    }
}

// 双端链表节点继承Node
class DoublyNode extends Node{
  constructor(element){
    super(element)
    this.prev = null
  }
}
// 双端链表继承LinkedList
class DoublyLinkedList extends LinkedList{
  constructor(){
    super()
    this.tail = null 
  }
  
  push(element){
    const node = new DoublyNode(element)
    if(this.head===null){ //第一个
      this.head=node
      this.tail=node
    }else{
      this.tail.next=node
      node.prev=this.tail
      this.tail=node
    }
    this.count++
  }
  
  insert(element,position){
    const node = new DoublyNode(element)
    if(position<0||position>this.count) return false;
    else if(position===0 && this.head===null){
      this.head=node
      this.tail=node
    }else if(position===0 && this.head){
      this.head.prev=node
      node.next=this.head
      this.head=node
    }else if(position===this.count){
      this.tail.next=node
      node.prev=this.tail
      this.tail=node
    }else{
      const previous = this.getElementAt(position-1)   //之前封装好的方法
      let current = previous.next
      node.next = current
      current.prev=node
      previous.next = node
      node.prev=previous
    
    }
    this.count++
    return true
  }
  
  removeAt(){
    // 与普通链表差别不大
  }
  
  getHead(){
    // 与普通链表差别不大
  }
}

const Db = new DoublyLinkedList()
Db.push(1)	// 1
Db.push(5)	// 1 <> 5
Db.push(7)	// 1 <> 5 <> 7
Db.insert(10,1)  //t 1 <> 10 <> 5 <> 7