/**
 * 单向链表
 */

// 封装
function LinkedList() {
    // 1. 内部类
    function Node(data) {
        this.data = data
        this.next = null
    }

    // 2. 属性
    this.head = null
    this.length = 0

    // 3. append
    LinkedList.prototype.append = function(data) {
        var newNode = new Node(data)
        if (this.length == 0) {
            this.head = newNode
        } else {
            var current = this.head
            while (current.next) {
                current = current.next
            }
            current.next = newNode
        }
        this.length += 1
    }
    // 4. toString
    LinkedList.prototype.toString = function() {
        var current = this.head
        var listString = ""
        while (current) {
            listString += current.data + " "
            current = current.next
        }
        return listString
    }
    // 5. insert
    LinkedList.prototype.insert = function(position, data) {
        // 越界判断
        if (position < 0 || position > this.length)  return false

        var newNode = new Node(data)
        // 判断插入的节点是否为第一个
        if (position == 0) {
            newNode.next = this.head
            this.head = newNode
        } else {
            var index = 0
            var current = this.head
            var previous = null
            while (index++ < position) {
                previous = current
                current = current.next
            }
            newNode.next = current
            previous.next = newNode
        }
        // length+1
        this.length += 1
        return true
    }
    // 6. get
    LinkedList.prototype.get = function(position) {
        // 越界判断
        if (position < 0 || position >= this.length)  return null

        // 读取data
        var current = this.head
        var index = 0
        while (index >= position) {
            current = current.next
        }
        // 返回数据
        return current.data
    }
    // 7. indexOf
    LinkedList.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
    }
    // 8. update
    LinkedList.prototype.update = function(position, newData) {
        // 越界判断
        if (position < 0 || position >= this.length) return false
        
        // 定义属性
        var current = this.head
        var index = 0
        while (index++ < position) {
            current = current.next
        }
        current.data = newData
        return true
    }
    // 9. removeAt
    LinkedList.prototype.removeAt = function(position) {
        // 越界判断
        if (position < 0 || position >= this.length) return false

        // 判断移除的节点是否是第一个
        if (position == 0) {
            this.head = this.head.next
        } else {
            var current = this.head
            var index = 0
            var previous = null
            while (index++ < position) {
                previous = current
                current = current.next
            }
            previous.next = current.next
        }
        // length-1
        this.length -= 1
        return true
    }
    // 10. remove
    LinkedList.prototype.remove = function(data) {
        // 找到data的position
        var position = this.indexOf(data)
        // 移除元素
        return this.removeAt(position)
    }
    // 11. isEmpty
    LinkedList.prototype.isEmpty = function() {
        return this.length == 0
    }
    // 12. size
    LinkedList.prototype.size = function() {
        return this.length
    }
}


// 测试代码
var link = new LinkedList()
link.append('a')
link.append('b')
link.append('c')
link.append('d')
link.append('e')
link.append('f')
console.log(link.toString()) // a b c d e f

link.insert(0, 'g')
link.insert(3, 'h')
console.log(link.toString()) // g a b h c d e f

link.update(2, 'i')
link.update(4, 'j')
console.log(link.toString()) // g a i h j d e f

console.log(link.get(3)) // g
console.log(link.indexOf('e')) // 6

link.removeAt(3)
link.remove('e')
console.log(link.toString()) // g a i j d f

console.log(link.isEmpty()) // false
console.log(link.size()) // 6