【算法社区】从零开始的DS生活 轻松从0基础写出链表LRU算法

public class Person {
    String head;
    String body;
    String arm;
    String leg;
}

// 顺序表的类型定义
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final Object[] EMPTY_ELEMENTDATA = {};  // 顺序表的元素
    private int size; // 顺序表的当前长度
}

/**
     * 将指定元素插入到列表中的指定位置。将当前位于该位置的元素(如果有的话)和随后的任何元素向右移动(将一个元素添加到它们的索引中)。
     *
     * @param index   index at which the specified element is to be inserted
     *                要插入指定元素的索引(即将插入元素的位置)
     * @param element element to be inserted 即将插入的元素
     * @throws IndexOutOfBoundsException {@inheritDoc} 如果索引超出size
     */
    public void add(int index, E element) {
        //越界检查
        rangeCheckForAdd(index);
        //确认list容量，如果不够，容量加1。注意：只加1，保证资源不被浪费
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
        //在插入元素之前，要先将index之后的元素都往后移一位
        //arraycopy(原数组，源数组中的起始位置，目标数组，目标数据中的起始位置，要复制的数组元素的数量)
        System.arraycopy(elementData, index, elementData, index + 1,
                size - index);
        //将指定的index位置赋值为element
        elementData[index] = element;
        //实际容量+1
        size++;
    }
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)//插入的位置不能大于size 和小于0，如果是就报越界异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

/**
     * 返回list中指定位置的元素
     *
     * @param index index of the element to return 要返回的元素的索引
     * @return the element at the specified position in this list
     * 位于list中指定位置的元素
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E get(int index) {
        rangeCheck(index);//越界检查
        return elementData(index);//返回索引为index的元素
    }
    /**
     * 检查指定索引是否在范围内。如果不在，抛出一个运行时异常。
     * 这个方法不检查索引是否为负数，它总是在数组访问之前立即优先使用，
     * 如果给出的索引index>=size，抛出一个越界异常
     */
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private String outOfBoundsMsg(int index) {
        return "Index: " + index + ", Size: " + size;
    }
    // Positional Access Operations 位置访问操作
    // 返回索引为index的元素
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

/**
     * 用指定的元素替换列表中指定位置的元素。
     * @param index index of the element to replace 要替换的元素的索引
     * @param element element to be stored at the specified position  要存储在指定位置的元素
     * @return the element previously at the specified position  先前位于指定位置的元素(返回被替换的元素)
     * @throws IndexOutOfBoundsException {@inheritDoc} 如果参数指定索引index>=size，抛出一个越界异常
     */
    public E set(int index, E element) {
        //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);
        //记录被替换的元素（旧值）
        E oldValue = elementData(index);
        //替换元素（新值）
        elementData[index] = element;
        //返回被替换的元素
        return oldValue;
    }

/**
     * 删除list中位置为指定索引index的元素
     * 索引之后的元素向左移一位
     *
     * @param index the index of the element to be removed 被删除元素的索引
     * @return the element that was removed from the list 被删除的元素
     * @throws IndexOutOfBoundsException {@inheritDoc} 如果参数指定索引index>=size，抛出一个越界异常
     */
    public E remove(int index) {
        //检查索引是否越界。如果参数指定索引index>=size，抛出一个越界异常
        rangeCheck(index);
        //结构性修改次数+1
        modCount++;
        //记录索引处的元素
        E oldValue = elementData(index);
        // 删除指定元素后，需要左移的元素个数
        int numMoved = size - index - 1;
        //如果有需要左移的元素，就移动（移动后，该删除的元素就已经被覆盖了）
        if (numMoved > 0)
            System.arraycopy(elementData, index + 1, elementData, index, numMoved);
        // size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
        elementData[--size] = null; // clear to let GC do its work
        //返回被删除的元素
        return oldValue;

public class Node<E> { // 单链表定义
    E data; //创建一个存储数据的属性
    Node<E> next; //创建存储下一个节点地址的属性
}
public class Node { // 双链表定义
    E data; //创建一个存储数据的属性
    Node<E> prev; //创建存储上一个节点地址的属性
    Node<E> next; //创建存储下一个节点地址的属性
}
public class Node{ // 静态链表定义
    int data;
    int cur;
}
// 使用 Node[] linkList = null; linkList[i] = new Node();

public class Node {
    Object data; //创建一个存储数据的属性
    Node next; //创建存储下一个节点地址的属性
    int length = 0;
    /**
     * 逆向创建一个链表-头插法是将新形成的节点的下一个赋值为header，再把新形成的节点地址传给header即将header向前移动
     *
     * @param temp 添加的数据
     * @return 链表第一个节点地址
     */
    public Node add(Integer temp) {
        Node newnode, header;  //定义链表的节点
        header = null; //header永远存储第一个节点的地址，tailer永远存储最后一个节点的地址
        newnode = new Node(); // 创建一个临时节点
        newnode.data = temp; //为属性赋值
        //判断当前链表是否第一次赋值
        if (header == null) {
            header = newnode;
        } else {
            newnode.next = header; //将新节点连接到链表的头部
            header = newnode; //header永远存储第一个节点的地址
        }
        //长度
        length++;
        return header;
    }
    /**
     * 创建一个链表-尾插法相对于头插法有些许不同 因为要返回头,头不能动,所以需要一个tailer来记录最后一个值 tailer右移   
     *
     * @param temp 添加的数据
     * @return 链表第一个节点地址
     */
    public static Node creat(Integer temp) {
        Node newnode, header, tailer; // 定义链表的节点
        header = tailer = null; // header永远存储第一个节点的地址，tailer永远存储最后一个节点的地址
        newnode = new Node();// 创建一个临时节点
        newnode.data = temp; // 为属性赋值
        //判断当前链表是否第一次赋值
        if (header == null) {
            header = tailer = newnode;
        } else {
            tailer.next = newnode; // 将新节点连接到链表的尾部
            tailer = newnode; // tailer永远存储最后一个节点的地址
        }
        //长度
        length++;
        return header;
    }
}

// 方法一-直接删除p结点
p.data = p.next.data; // 令p和p.next的数据对调
p.next = p.next.next; // 将p指向p.next的下一个
// 方法二-查找删除节点的前驱结点q
q = getElem(list, i-1); // 遍历链表查找删除位置的前驱
q.next = p.next; // 令q为p结点的后继
p.next = null; // GC回收

// 图一将s结点插入到P结点后
s.next = p.next;   
p.next.prev = s;
s.prev = p;  
p.next = s;
// 图二删除结点
p.next.prev = p.prev;
p.pre.next = p.next;

/**
 * 带哨兵的双向链表
 *
 * @author fmc
 * @date 2020/5/1-19:19
 */
public class DoubleLinkedList {
    private Node nil; // 哨兵节点
    public DoubleLinkedList() {
        nil = new Node(null); // NIL节点的key值没有实际的意义
        nil.pre = nil;  // NIL.next指向自己
        nil.next = nil; // NIL.pre也指向自己
    }
    // 当添加了若干个节点之后，NIL.next指向头节点，而NIL.pre则指向尾节点；
    public void insert(Object o) {
        Node e = new Node(o);
        e.next = nil.next; // ① 如果是第一次插入，nil的next指向第一个节点，如果是n(n>1)次，新e的后继指向前一个插入节点(老e)
        nil.next.pre = e;  // ② 如果是第一次插入，nil的pre指向头结点，如果是n(n>1)次，老e的前驱指向新e
        nil.next = e; // ③ nil节点next 指向新插入的节点（尾结点）
        e.pre = nil; // ④ 新插入的节点的前驱指向 哨兵节点
    }
    // 查询
    public Node search(Object o) {
        Node e = nil.next;
        while (e != nil && e.key != o) { // 从nil节点开始遍历
            e = nil.next;  // 向后查询
        }
        return e;
    }
    // 删除
    public void delete(Object o) {
        Node e = search(o);
        e.pre.next = e.next;
        e.next.pre = e.pre;
    }
    // 节点定义为双链
    public class Node {
        public Object key;
        private Node pre;
        private Node next;
        public Node(Object x) {
            this.key = x;
        }
    }
}

public class LruLinkedList<T> {
    //节点的信息
    class Node {
        T data;
        Node next;
        public Node(T data, Node node) {
            this.data = data;
            this.next = node;
        }
    }
    Node list; // 保存链表
    int size; // 链表有多少个节点
    int memory_size; // 用于限定内存空间大小，也就是缓存的大小
    static final int DEFAULT_CAP = 5;
    public LruLinkedList() {
        this(DEFAULT_CAP);
    }
    public LruLinkedList(int default_memory_size) {
        memory_size = default_memory_size;
    }
    // LRU添加节点
    public void lruPut(T data) {
        if (size >= memory_size) {
            removeLast();
            put(data);
        } else {
            put(data);
        }
    }
    // 在头部添加节点
    public void put(T data) {
        Node head = list;
        Node curNode = new Node(data, list);
        list = curNode;
        size++;
    }
    // LRU删除
    public T lruRemove() {
        return removeLast();
    }
    // LRU访问
    public T lruGet(int index) {
        checkPositionIndex(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 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;
    }
    // 检测index是否在链表范围以内
    public void checkPositionIndex(int index) {
        if (!(index >= 0 && index <= size)) {
            throw new IndexOutOfBoundsException("index: " + index + ", size: " + size);
        }
    }
}