手写单链表，实现增删改查

package top.zcwfeng.java.arithmetic.lru;

//单链表
public class LinkedList<T> {


    Node list;
    int size;//链表节点个数

    public LinkedList() {

    }

    // 添加
    public void put(T data) {
        Node head = list;//保存一下
        Node currentNode = new Node(data,list);
        list = currentNode;
        size ++;
    }

    public void put(int index, T data) {
        checkPositonIndex(index);
        Node cur = list;
        Node head = list;// 保存当前的节点前面的节点

        for (int i = 0; i < index; i++) {
            head = cur;
            cur = cur.next;
        }

        Node node  = new Node(data,cur);
        head.next = node;
        size++;


    }

    /**
     * 检查index 是否在链表的范围内
     * @param index
     */
    public void checkPositonIndex(int index) {
        if(!(index >= 0 && index <= size)){
            throw new IndexOutOfBoundsException("index:" + index + ",size:"+size);
        }
    }

    //    修改
    public void set(int index, T newData) {
        checkPositonIndex(index);
        Node head = list;// 保存当前的节点前面的节点
        for (int i = 0; i < index; i++) {
            head = head.next;
        }

       head.data = newData;
    }
//    删除

    /**
     * 删除头部
     *
     * @return
     */
    public T remove() {
        if(list != null){
            Node node = list;
            list = list.next;
            node.next = null;
            size--;
            return node.data;
        }
        return null;

    }

    public T remove(int index) {
        checkPositonIndex(index);
        Node head = list;
        Node cur = list;
        for (int i = 0; i < index; i++) {
            head = cur;
            cur = cur.next;
        }

        head.next = cur.next;
        cur.next = null;
        size--;
        return cur.data;
    }

    public T removeLast() {
        if(list != null){
            Node node = list;
            Node cur = list;
            while (cur.next != null){
                node = cur;
                cur = cur.next;
            }
            node.next = null;
            size --;
            return cur.data;
        }

        return null;
    }
//    查询

    /**
     * get head
     *
     * @return
     */
    public T get() {
        Node node = list;
        if(node != null){
            return list.data;
        } else {
        return null;
        }
    }

    public T get(int index) {
        checkPositonIndex(index);
        Node node = list;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node.data;

    }

    @Override
    public String toString() {
        Node node = list;
        for (int i = 0; i < size; i++) {
            System.out.println(node.data + " ");
            node = node.next;
        }
        System.out.println();
        return super.toString();
    }

    // 节点信息
    class Node {
        T data;
        Node next;

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




    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i < 5; i++) {
            list.put(i);
        }
        list.toString();
        list.put(3,3);
        list.toString();
        list.put(8);
        list.toString();
    }

}

根据单链表操作，实现LRU算法

新数据插入到链表头部
当缓存命中(即缓存数据被访问)，数据要移到表头
当链表满的时候，将链表尾部的数据丢弃

package top.zcwfeng.java.arithmetic.lru;

public class LruLinkedList<T> extends LinkedList<T> {
    static final int DEFAULT_CAP = 5;
    int memeory_size;//用于限定内存大小，也就是缓存大小

    public LruLinkedList() {
        this(DEFAULT_CAP);
    }

    public LruLinkedList(int memeory_size) {
        this.memeory_size = memeory_size;
    }

    public void lruPut(T data) {
        if(size >= memeory_size){
            removeLast();
            put(data);
        }else{
            put(data);
        }
    }

    public T lruRemove(){
        return removeLast();
    }

    public T lruGet(int index){
        checkPositonIndex(index);
        Node node = list;
        Node pre = list;
        for (int i = 0; i < index; i++) {
            pre = node;
            node = node.next;
        }

        T resultData = node.data;
        // 将访问节点放到表头
        pre.next = node.next;
        Node head = list;
        node.next = head;
        list = node;
        return resultData;
    }

    public static void main(String[] args) {
        LruLinkedList<Integer> lruLinkedList = new LruLinkedList<>();
        for (int i = 0; i < 4; i++) {
            lruLinkedList.lruPut(i);
        }
        lruLinkedList.toString();
        System.out.println(lruLinkedList.lruGet(3));
        lruLinkedList.toString();
        lruLinkedList.lruPut(20);
        lruLinkedList.toString();
        lruLinkedList.lruPut(18);
        lruLinkedList.toString();
    }
}

给LinkeList 添加翻转单链表方法

public void reverse(){
        //单链表为空或只有一个节点，直接返回原单链表
        if (list == null || list.next == null){
            return;
        }
        Node head = list;
        Node next = list.next;
        list.next = null;
        Node temp;
        while(next !=null){
            temp = next.next;
            next.next = head;
            head = next;
            next = temp;

        }
        list = head;

    }