//append, insert, get, indexOf
//单向链表
const log = console.log
class Node {
  constructor(data){
    this.data = data
    this.next = null
  }
}
class LinkedList {
  //属性
  head = null
  length = 0
  
  //一、实现append 方法
    //1.创建新节点
    //2.添加新节点
      //①节点数等于1
      //②节点数大于1
    //3.修改单向链表属性-长度
  append = (data) => {
    let newNode = new Node(data)
    
    if(this.length === 0) {
      this.head = newNode
    }else {
      let current = this.head
      while(current.next) {
        current = current.next
      }
      //循环后，current为最后一个节点
      current.next = newNode
    }
    
    this.length += 1
  }
  toString(){
    let current = this.head
    let listString = ''
    while(current) {
      listString += current.data + ' '
      current = current.next
    }
    //循环后，current为最后一个节点
    return listString
    
  }

  //二、insert
  insert(position, data) {
    
    //1. position越界
    //2. 创建节点
    //3. 插入新节点
      //① 新节点position=0
      //② 新节点position>0
    
    if(position < 0 || position > this.length) {
      log(`failed!!`)
      return false
    }
    let newNode = new Node(data)
    if(position === 0) {
      //①
      newNode.next = this.head
      this.head = newNode

      this.length += 1
      return true
    }
    //②
    let index = 0
    let previous = null
    let current = this.head
    
    while(index++ < position) {
      previous = current
      current = current.next
    }
    //循环结束后 新节点应该被current的指向和previous的指向，夹住
    newNode.next = current
    previous.next = newNode
//     log(current,previous)
    
    this.length += 1
    return true
    
  }

  //三、get
  get(position){
    if(position < 0 || position >= this.length) return null
    let index = 0
    let current = this.head
    while(index++ < position) {
      current = current.next
    }
    return current.data
  }

  //四、indexOf方法 给data返回下标值
  indexOf(data) {
    let current = this.head
    let index = 0
//     while(index++ < this.length) <-- 错误写法
    while(current) {
      if(current.data === data) {
        return index
      }
      current = current.next
      index += 1
    }
    return -1
  }
}

//append
let linkedList = new LinkedList()
linkedList.append('aaa')
linkedList.append('bbb')
linkedList.append('ccc')
// log(linkedList)
linkedList.insert(0, 'ddd')
log(linkedList.toString())
log(`位置1的元素为`, linkedList.get(1))
log(`aaa的位置下标是`,linkedList.indexOf('aaa'))
复制成功
复制

//update(position, newData). removeAt(position), remove(element)
//单向链表
const log = console.log
class Node {
  constructor(data){
    this.data = data
    this.next = null
  }
}
class LinkedList {
  //属性
  head = null
  length = 0
  
  //五、update
  update(position, newData) {
    if(position < 0 || position >= this.length) return false
    let current = this.head
    let index = 0
    while(index++ < position) {
      current = current.next
    }
    current.data = newData
    log(current)
    return true
  }

  //六、removeAt(position)
  removeAt(position) {
    if(position < 0 || position >= this.length) return null
    if(position === 0) {
      this.head = this.head.next
      this.length -= 1
      return true
    }
    let current = this.head
    let previous = null
    let index = 0
    while(index++ < position) {
      previous = current
      current = current.next
    }
    previous.next = current.next
//     delete current
    this.length -= 1
    return true
  }

  //七、 remove(data)
  remove(data) {
    return this.removeAt(this.indexOf(data))
//     let current = this.head
//     let previous = null
//     let isRemoved = false
//     while(current) {
//       if(current.data === data) {
//         if(!previous) {
//           this.head = this.head.next
//         }else {
//         previous.next = current.next
//         }
//         isRemoved = true
//       }
//       previous = current
//       current = current.next
//     }
//     if(!isRemoved) return -1
//     return true
  }
}

//append
let linkedList = new LinkedList()
linkedList.append('aaa')
linkedList.append('bbb')
linkedList.append('ccc')
// log(linkedList)
linkedList.insert(0, 'ddd')
log(linkedList.toString())
// log(`位置1的元素为`, linkedList.get(1))
// log(`aaa的位置下标是`,linkedList.indexOf('aaa'))
log(linkedList.update(3, 'mmm'))
log(linkedList.toString())
// log(linkedList.removeAt(0))
log(linkedList.remove('mmm'))
log(linkedList.toString())
复制成功
复制

// 双向链表
const log = console.log
class DoublyNode {
  constructor(data){
    this.data = data
    this.prev = null
    this.next = null
  }
}
class DoublyLinkedList {
  head = null
  tail = null
  length = 0
  
  append(data) {
    let newNode = new DoublyNode(data)
    if(this.length === 0) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length += 1
    return
  }
  insert(position, data) {
    if (position < 0 || position > this.length) return false;
    
    let newNode = new DoublyNode(data)
    if(position === 0) {
      if(this.length === 0) {
        this.head = newNode
        this.tail = newNode
      }else {
        newNode.next = this.head
        this.head.prev = newNode
        this.head = newNode
      }
      
    }else if(position === this.length){
      this.tail.next = newNode
      newNode.prev = this.tail
      this.tail = newNode
    }else {
      let targetIndex = 0
      let currentNode = this.head;
      let previousNode = null;
      while(targetIndex++ < position) {
        previousNode = currentNode
        currentNode = currentNode.next
      }
      newNode.prev = previousNode
      newNode.next = currentNode
      currentNode.prev = newNode
      previousNode.next = newNode
    }
    
    this.length += 1
    return true
  }
}
const dl = new DoublyLinkedList()
dl.append(4399)
dl.append(8000)
dl.insert(1,"7k7k")
log(dl)
复制成功
复制