avatar

`2019年`文章归档

未分类

淘汰算法LRU

T 发表于    标签： 算法

基于双链表实现LRU
原理： 将Cache的所有位置都用双连表连接起来，当一个位置被命中之后，就将通过调整链表的指向，将该位置调整到链表头的位置，新加入的Cache直接加到链表头中。这样，在多次进行Cache操作后，最近被命中的，就会被向链表头方向移动，而没有命中的，而想链表后面移动，链表尾则表示最近最少使用的Cache。当需要替换内容时候，链表的最后位置就是最少被命中的位置，我们只需要淘汰链表最后的部分即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
public class LRUCache {  
	
	//缓存大小
    private int cacheSize;
    //缓存容器
    private Hashtable<K, CacheNode<K, V>> nodes;
    //当前缓存对象数量
    private int currentSize;
    //(实现双链表)链表头
    private CacheNode first;
    //(实现双链表)链表尾
    private CacheNode last;

    public LRUCache(int i) {
        currentSize = 0;
        cacheSize = i;
        nodes = new Hashtable(i);//缓存容器
    }

    /**
     * 链表节点
     *
     */
    private static class CacheNode<K,V> {
        CacheNode prev;
        CacheNode next;
        K key;
        V value;
        CacheNode() {
        }
    }

    public V get(K key){
        CacheNode<K, V> node = nodes.get(key);
        if(node!=null){
            moveToHead(node);
            return node.value;
        }else{

            return null;
        }
    }

    public void put(K key, V value){
        CacheNode<K, V> node = nodes.get(key);
        if(node == null){
            if(currentSize >= cacheSize){
                if(last != null){
                    nodes.remove(last.key);
                }
                removeLast();
            }else{
                currentSize++;
            }
            node = new CacheNode<>();
        }
        node.value=value;
        node.key=key;
        moveToHead(node);
        nodes.put(key, node);
    }

    private void removeLast(){
        if(last!=null){
            if(last.prev != null){
                last.prev.next = null;
            }else{
                first = null;
            }
            last = last.prev;
        }
    }

    private void moveToHead(CacheNode node){
        if(node == first){
            return;
        }

        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        if (last == node) {
            last = node.prev;
        }
        if (first != null) {
            node.next = first;
            first.prev = node;
        }
        first = node;
        node.prev = null;
        if (last == null) {
            last = first;
        }
    }
}

阅读剩下更多

默认配图
未分类

链表相关算法

T 发表于    标签： 算法

1.删除链表指定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LinkedNode{
	public LinkedNode removeElement(LinkedNode head, int val){
		
		//先从头结点开始删
		while(head != null && head.val == val){
			head = head.next;
		}
		
		if(head==null){
			return head;
		}
		
		LinkedNode pre = head;
		while(pre.next!=null){
			if(pre.next.val==val){
				pre.next = pre.next.next;
			}else{
				pre = pre.next;
			}
		}
		return head;
	}
}

2.有序链表插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LinkedNode{
	public void insertElement(LinkedNode node){
		LinkedNode pre = null;
		LinkedNode current = first;
		while(current!=null&&node.value<current.value){
			pre = current;
			current = current.next;
		}
		
		if(pre==null){
			first = node;
		}else{
			pre.next = node;
		}
		node.next = current;
	}
}

3.判断链表是否有环

1
2
3
4
5
6
7
8
9
10
11
12
13
public static <T> boolean isLoopList(ListNode<T> head){
	ListNode<T> slowPointer, fastPointer;

	slowPointer = fastPointer = head;
	while(fastPointer != null && fastPointer.next != null){
		slowPointer=slowPointer.next;
		fastPointer=fastPointer.next.next;
		if(slowPointer == fastPointer){
			return true;
		}
	} 
	return false;
}

阅读剩下更多

默认配图
返回顶部