链表

链表特点就是插入，删除容易，访问时间O(n)
数组正好相反。

用链表实现LruLinkedList

class LruLinkedList<T> {
    private var head:Node<T>? = null
    private var maxSize:Int = -1
    private var currentSize = -1

    constructor(size:Int){
        this.maxSize = size
        if(size<=1){
            /*保证必要的缓存大小*/
            maxSize = 1
        }
    }

    fun dump(){
        var stringBuilder = StringBuilder()
        var p = head
        while(p!=null){
            stringBuilder.append("${p.value},")
            p = p.next
        }
        AppLog.d(stringBuilder.toString())
    }

    fun addNote(value:T){
        if(head == null){
            //first node
            head = Node(value)
            currentSize = 1
            return
        }else{
            if(head?.value == value){
                //do nothing
                return
            }else{
                removeNote(value)
            }
            dump()
            addNewOne(value)
            trimMaxSize()
        }
    }

    private fun trimMaxSize() {
        if(currentSize>maxSize){
            AppLog.i("cur:$currentSize,max:$maxSize")
            var tempSize = 0
            var p = head
            while(p!=null){
                tempSize++
                if(tempSize<=maxSize){
                    p = p.next
                }else{
                    p.next = null
                    currentSize = maxSize
                    return
                }
            }
        }
    }

    private fun addNewOne(value: T) {
        val tempNode = Node(value)
        val tempH = head
        head = tempNode
        head?.next = tempH
        currentSize +=1
    }

    fun removeNote(value: T):Boolean {
        var p = head
        var tempP = head
        var flag  = false
        while(p!=null){
            if(p.value!! == value){
                AppLog.i("find value:$value")
                flag = true
                break
            }
            tempP = p
            p =p.next
        }
        /*delete old one*/
        if(flag){
            val nextOne = p?.next
            tempP?.next = nextOne
            currentSize -=1
            return true
        }else{
            /*not find*/
            return false
        }
    }
}