重学数据结构(三)——使用单链表实现LRU淘汰缓存机制

栏目: IT技术 · 发布时间: 4年前

使用单链表实现LRU(Least Recently Used)淘汰缓存机制

需求:存在一个单链表,在单链表尾部的都是越早之前添加的元素。

  1. 当元素被访问到时,会添加进缓存(也就是这个单链表中)。
  2. 如果这个元素在之前已经被缓存到了链表中,则将这个元素从原来的位置删除,用头插法放到链表的头部。
  3. 如果这个元素不在链表中,则根据链表的容量进行判断
    1. 缓存容量未满时,直接用头插法,放到链表的头部
    2. 缓存容量已满时,首先删除链表尾部的元素,再将元素进行插入到头部。

创建Node对象

package com.codezs.datastruct.mylinkedlist;

public class Node<T> {
    T data;
    Node<T> next;

    Node(Node<T> next) {
        this.next = next;
    }

    public Node(T data, Node<T> next) {
        this.data = data;
        this.next = next;
    }

    public T getData(){
        return data;
    }
    public Node<T> getNext(){
        return next;
    }
    public void setNext(Node<T> next){this.next = next;};
    
}

对单链表实现LRU淘汰缓存机制的实现

package com.codezs.datastruct.mylinkedlist;

public class MyLinkedList<T> {

    //默认链表容量
    private final static Integer DEFAULT_CAPACITY = 10;

    //头结点
    private Node head;

    //链表长度
    private Integer length;

    //链表容量
    private Integer capacity;


    public MyLinkedList() {
        this.capacity = DEFAULT_CAPACITY;
        this.head = new Node(null);
        this.length = 0;
    }

    public MyLinkedList(Integer capacity) {
        this.capacity = capacity;
        this.head = new Node(null);
        this.length = 0;
    }

    public Node getHead(){
        return head;
    }

    //添加新的元素
    public void add(T data){
        Node<T> preNode = findPreNode(data);

        if (preNode != null){
            remove(preNode);
            insertNode(data);
        } else {
            if (length >= this.capacity){
                deleteNodeAtEnd();
            }
            insertNode(data);
        }
    }

    //获取查找到元素的前一个节点
    private Node<T> findPreNode(T data){
        Node node = head;
        while(node.getNext() != null){
            if (data.equals(node.getNext().getData())){
                return node;
            }
            node = node.getNext();
        }
        return null;
    }

    //删除node结点下一个元素
    private void remove(Node preNode){
        Node node = preNode.getNext();
        preNode.setNext(node.getNext());
        node = null;
        length--;
    }

    //头插法
    private  void insertNode(T data){
        Node node = head.getNext();
        head.setNext(new Node(data,node));
        length++;
    }

    //删除链表中最后一个元素
    private void deleteNodeAtEnd(){
        Node node = head;

        if (node.getNext() == null) {
            return;
        }

        while (node.getNext().getNext() != null) {
            node = node.getNext();
        }
        Node nextNode = node.getNext();
        node.setNext(null);
        nextNode = null;
        length--;
    }


    public boolean isEmpty(){
        return length == 0;
    }

    public int size(){
        return length;
    }

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Android软件安全与逆向分析

Android软件安全与逆向分析

丰生强 / 人民邮电出版社 / 2013-2 / 69.00元

本书由浅入深、循序渐进地讲解了Android 系统的软件安全、逆向分析与加密解密技术。包括Android软件逆向分析和系统安全方面的必备知识及概念、如何静态分析Android 软件、如何动态调试Android 软件、Android 软件的破解与反破解技术的探讨,以及对典型Android 病毒的全面剖析。 本书适合所有Android 应用开发者、Android 系统开发工程师、Android ......一起来看看 《Android软件安全与逆向分析》 这本书的介绍吧!

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具