数据结构与算法—LinkedList–1
链表
链表特点就是插入,删除容易,访问时间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
}
}
}