自定义LinkedList简单实现LRU

1. 描述

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。
当有一个新的数据被访问时，我们从链表头开始顺序遍历链表
1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从
原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

2. 代码

package org.feng.linklist;

import java.util.Objects;

/**
 * Created by Feng on 2019/11/14 19:58
 * CurrentProject's name is leetcode-demo
 * @author Feng
 */
public class LinkedList<E>{

    /** 数据 */
    private Node<E> root;
    /** 真实大小 */
    private int size;
    /** 最大容量 */
    private static final int MAX_SIZE = 10;

    /**
     * 增加节点的方法：新来的结点放在最前边。
     * 越早进入的结点越放在后边。
     * @param element
     */
    public Node<E> add(E element){
        checkSize();
        return addElement(element);
    }


    private Node<E> addElement(E element){
        Node<E> newNode = new Node<>(element);
        newNode.next = root;
        root = newNode;

        size ++;
        return newNode;
    }


    /**
     * 维护链表：新的数据进来时，先调用该方法
     * 查看该数据是否已经存在，若存在先删除原先的数据，再将其增加到头部；
     * 若不存在，则直接插入到头部
     * @param element
     */
    public Node<E> findAndUpdate(E element){
        if(root == null){
            addElement(element);
            return root;
        }

        Node<E> node = root;
        if(Objects.equals(node.data, element)){
            return node;
        }

        // 先删除原先的
        while(node.next != null){
            if(Objects.equals(node.next.data, element)){
                node.next = node.next.next;
                size --;
                break;
            }
            node = node.next;
        }
        return add(element);
    }


    /**
     * 删除最后一个节点：最早进入的那个
     */
    public void removeLast(){
        if(root == null){
            return;
        }

        Node<E> node = root;
        if(node.next == null){
            root = null;
            size --;
            return;
        }

        // 当不只有root节点时
        while(node.next != null && node.next.next != null){
            node = node.next;
        }
        node.next = null;
        size --;
    }



    private void checkSize(){
        if(size == MAX_SIZE) {
            removeLast();
        }
    }


    public int size(){
        return size;
    }

    @Override
    public String toString() {
        Node<E> temp = root;
        if(temp == null){
            return "{}";
        }

        StringBuilder stringBuilder = new StringBuilder("{");
        while (temp != null){
            stringBuilder.append(temp).append(", ");
            temp = temp.next;
        }

        int len = stringBuilder.length();
        stringBuilder.delete(len - 2, len);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }
}

package org.feng.linklist;

/**
 * Created by Feng on 2019/11/14 19:22
 * CurrentProject's name is leetcode-demo
 */
public class Node<E> {
    public E data;

    public Node<E> next;

    public Node(E data){
        this.data = data;
    }

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

    @Override
    public String toString() {
        return data.toString();
    }
}

package org.feng.linklist;

/**
 * Created by Feng on 2019/11/14 19:25
 * CurrentProject's name is leetcode-demo
 * @author Feng
 */
public class Movie {
    /** 电影名 */
    private String name;
    /** 评分 */
    private Integer grade;

    public Movie(String name, Integer grade) {
        this.name = name;
        this.grade = grade;
    }


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getGrade() {
        return grade;
    }

    public void setGrade(Integer grade) {
        this.grade = grade;
    }

    @Override
    public String toString() {
        return "Movie{" +
                "name='" + name + '\'' +
                ", grade=" + grade +
                '}';
    }


    @Override
    public boolean equals(Object obj) {
        return this.name.equals(((Movie)obj).getName());
    }
}

package org.feng.linklist;

/**
 * Created by Feng on 2019/11/14 19:18
 * CurrentProject's name is leetcode-demo
 * 思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。
 * 当有一个新的数据被访问时，我们从链表头开始顺序遍历链表
 * 1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从
 * 原来的位置删除，然后再插入到链表的头部。
 * 2. 如果此数据没有在缓存链表中，又可以分为两种情况：
 * 如果此时缓存未满，则将此结点直接插入到链表的头部；
 * 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
 * @author Feng
 */
public class LruDemo {

    public static void main(String[] args) {
        LinkedList<Movie> linkedList = new LinkedList<>();

        linkedList.add(new Movie("阿凡达", 9));
        linkedList.add(new Movie("阿凡达2", 10));
        linkedList.add(new Movie("哪吒", 9));
        linkedList.add(new Movie("海王", 8));
        linkedList.add(new Movie("加勒比海盗", 9));
        linkedList.add(new Movie("澳门风云", 10));

        System.out.println(linkedList);

        linkedList.removeLast();
        System.out.println(linkedList);

        System.out.println("------------------");
        System.out.println(linkedList.findAndUpdate(new Movie("海王", 8)));
        System.out.println(linkedList);
        System.out.println(linkedList.size());
    }
}

3. 测试结果

{Movie{name='澳门风云', grade=10}, Movie{name='加勒比海盗', grade=9}, Movie{name='海王', grade=8}, Movie{name='哪吒', grade=9}, Movie{name='阿凡达2', grade=10}, Movie{name='阿凡达', grade=9}}
{Movie{name='澳门风云', grade=10}, Movie{name='加勒比海盗', grade=9}, Movie{name='海王', grade=8}, Movie{name='哪吒', grade=9}, Movie{name='阿凡达2', grade=10}}
------------------
Movie{name='海王', grade=8}
{Movie{name='海王', grade=8}, Movie{name='澳门风云', grade=10}, Movie{name='加勒比海盗', grade=9}, Movie{name='哪吒', grade=9}, Movie{name='阿凡达2', grade=10}}
5