/**
 * 双向链表
 */

// 封装
function DoublyLinkedList() {
    function Node(data) {
        this.data = data
        this.prev = null
        this.next = null
    }
    this.head = null
    this.tail = null
    this.length = 0

    // append方法
    DoublyLinkedList.prototype.append = function(data) {
        // 1. 创建节点
        var newNode = new Node(data)
        // 2. 判断添加的是否为第一个节点
        if (this.length == 0){
            this.head = newNode
            this.tail = newNode
        } else {
            newNode.prev = this.tail
            this.tail.next = newNode
            this.tail = newNode
        }
        // 3. length+1
        this.length += 1
    }
    // toString方法
    DoublyLinkedList.prototype.toString = function() {
        return this.backwordString()
    }
    // forwardString方法
    DoublyLinkedList.prototype.forwardString = function() {
        var current = this.tail
        var doubleListString = ""
        while (current) {
            doubleListString += current.data + " "
            current = current.next
        }
        return doubleListString
    }
    // backwordString方法
    DoublyLinkedList.prototype.backwordString = function() {
        var current = this.head
        var doubleListString = ""
        while (current) {
            doubleListString += current.data + " "
            current = current.next
        }
        return doubleListString
    }
    // insert方法
    DoublyLinkedList.prototype.insert = function(position, data) {
        // 1. 越界判断
        if (position < 0 || position > this.length) return -1
        // 2. 插入数据
        var newNode = new Node(data)
        if (this.length == 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            if (position == 0) { // 2.1 插入首节点
                this.head.prev = newNode
                newNode.next = this.head
                this.head = newNode
            } else if (position == this.length) { // 2.2 插入尾节点
                newNode.prev = this.tail
                this.tail.next = newNode
                this.tail = newNode
            } else { // 2.3 插入中间节点
                var current = this.head
                var index = 0
                while (index++ < position) {
                    current = current.next
                }
                // 修改指针
                newNode.next = current
                newNode.prev = current.prev
                current.prev.next = newNode
                current.prev = newNode
            }
        }
        // 3. length+1
        this.length += 1
        return true
    }
    // get方法
    DoublyLinkedList.prototype.get = function(position) {
        // 1. 越界判断
        if (position < 0 || position >= this.length) return null
        // 2. 获取数据
        var current = this.head
        var index = 0
        while (index++ < position) {
            current = current.next
        }
        return current.data
    }
    // indexOf方法: 获取数据索引
    DoublyLinkedList.prototype.indexOf = function(data) {
        var current = this.head
        var index = 0
        while (current) {
            if (current.data == data) {
                return index
            }
            current = current.next
            index += 1
        }
        return -1
    }
    // update方法
    DoublyLinkedList.prototype.update = function(position, newData) {
        // 1. 越界判断
        if (position < 0 || position >= this.length) return false
        // 2. 更新数据
        var current = this.head
        var index = 0
        while (index++ < position) {
            current = current.next
        }
        current.data = newData
        return true
    }
    // removeAt方法
    DoublyLinkedList.prototype.removeAt = function(position) {
        // 1. 越界判断
        if (position < 0 || position >= this.length) return false
        // 2. 删除数据
        var current = this.head
        if (this.length == 1) {
            this.head = null
            this.tail = null
        } else {
            if (position == 0) {
                this.head.next.prev = null
                this.head = this.head.next
            } else if (position == this.length - 1) {
                current = this.tail
                this.tail.prev.next = null
                this.tail = this.tail.prev
            } else {
                var index = 0 
                while (index++ < position) {
                    current = current.next
                }
                current.prev.next = current.next
                current.next.prev = current.prev
            }
        }
        // 3. length-1
        this.length -= 1
        return true
    }
    // remove方法
    DoublyLinkedList.prototype.remove = function(data) {
        var index = this.indexOf(data)
        return this.removeAt(index)
    }
    // isEmpty方法
    DoublyLinkedList.prototype.isEmpty = function() {
        return this.length == 0
    }
    // size方法
    DoublyLinkedList.prototype.size = function() {
        return this.length
    }
}

// 测试代码
var doubly = new DoublyLinkedList()
doubly.append("1")
doubly.append("2")
doubly.append("3")
console.log(doubly.toString()) // 1 2 3
console.log(doubly.forwardString()) // 3 2 1
console.log(doubly.backwordString()) // 1 2 3

doubly.insert(0, "4")
doubly.insert(1, "5")
doubly.insert(2, "6")
console.log(doubly.toString()) // 4 5 6 1 2 3

console.log(doubly.indexOf('5')) // 1

doubly.update(1, 9)
console.log(doubly.toString()) // 4 9 6 1 2 3

doubly.removeAt(2)
doubly.remove(3)
console.log(doubly.toString()) // 4 9 1 2
console.log(doubly.isEmpty()) // false
console.log(doubly.size()) // 4