深入剖析LinkedList:揭秘底层原理

在这里插入图片描述

文章目录

    • 一、 概述LinkedList
      • 1.1 LinkedList简介
      • 1.2 LinkedList的优点和缺点
    • 二、 LinkedList数据结构分析
      • 2.1 Node节点结构体解析
      • 2.2 LinkedList实现了双向链表的原因
      • 2.3 LinkedList如何实现了链表的基本操作(增删改查)
      • 2.4 LinkedList的遍历方式
    • 三、 源码分析
      • 3.1 成员变量
      • 3.2 构造方法
      • 3.3 add()方法
      • 3.4 remove()方法
      • 3.5 get()方法
      • 3.6 set()方法
      • 3.7 clear()方法
      • 3.8 indexOf()方法
    • 四、 总结及实战应用
      • 4.1 LinkedList适用场景
      • 4.2 LinkedList与ArrayList的比较
      • 4.3 LinkedList的使用注意事项
      • 4.4 实战应用:设计一个基于LinkedList的LRU缓存算法

一、 概述LinkedList

1.1 LinkedList简介

LinkedList是Java中的一种双向链表数据结构实现类,它实现了ListDeque接口。

LinkedList的特点主要包括以下几点

  1. 链表结构:LinkedList内部使用链表来存储元素,每个节点都包含当前元素的值以及指向前一个节点和后一个节点的引用。这种链表结构使得插入和删除元素的操作效率较高。
  2. 双向访问:每个节点都有指向前一个节点和后一个节点的引用,这使得在LinkedList中可以通过前向或后向遍历访问元素,而不需要像ArrayList那样进行元素的整体移动。
  3. 动态大小:LinkedList没有固定的容量限制,可以根据需要动态地添加或删除元素,并且不会出现数组扩容的情况。
  4. 随机访问较慢:由于LinkedList是基于链表的数据结构,因此在访问特定索引位置的元素时,需要从头或尾部开始遍历到目标位置。相比之下,ArrayList可以通过索引直接访问元素,因此在随机访问元素时效率更高。
  5. 支持队列和栈操作:作为Deque接口的实现类,LinkedList可以被用作队列(先进先出)和栈(后进先出)的数据结构,可以使用addFirst、removeFirst等方法模拟栈操作,使用addLast、removeFirst等方法模拟队列操作。

总体而言,LinkedList适用于频繁地插入和删除元素的场景,但对于随机访问元素的需求不是很高时,可以考虑使用它。

1.2 LinkedList的优点和缺点

优点

  1. 链表的插入和删除操作比较快速,因为只需要改变指针指向即可。
  2. 可以在任意位置进行插入和删除操作,而不需要像数组那样需要移动其他元素。
  3. 在迭代时可以快速获取下一个元素,因为每个节点都有指向前后节点的指针。

缺点

  1. 链表的访问操作比较慢,因为需要遍历整个链表才能找到对应的元素。
  2. 由于链表每个节点都需要额外存储前后节点的指针,因此占用的内存空间比数组大。
  3. 链表没有像数组那样可以直接访问任意位置的元素,因此不能使用索引随机访问元素。
  4. 当需要频繁进行随机访问时,由于缺乏连续的内存空间,可能会导致缓存命中率降低,从而影响性能。

综上所述,LinkedList 适合在需要频繁进行插入和删除操作,但是不需要频繁随机访问元素的场景下使用。如果需要随机访问或者占用空间比较重要时,可以考虑使用其他数据结构,比如 ArrayList

二、 LinkedList数据结构分析

2.1 Node节点结构体解析

在Java中,LinkedList的实现是通过一个双向链表来实现的。在LinkedList中,每个节点都有一个指向前一个节点和一个指向后一个节点的引用。

在LinkedList中,Node节点结构体可以被定义如下

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(E element, Node<E> next, Node<E> prev) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

上面的代码定义了一个私有静态内部类Node,该类包含了一个泛型元素item,以及两个Node类型的引用nextprev,分别表示指向下一个节点和上一个节点的引用。此外,Node类还有一个带有三个参数的构造函数,用于初始化节点的prev、itemnext属性。

通过这样的设计,LinkedList可以通过Node节点来构建双向链表结构,实现了在任意位置进行节点的插入和删除操作。

2.2 LinkedList实现了双向链表的原因

Java中的LinkedList实现了双向链表是因为双向链表具有以下优点

  1. 双向链表可以从前向后或从后向前遍历,而单向链表只能从前往后遍历,这使得双向链表更加灵活和高效。
  2. 双向链表能够提供O(1)时间复杂度的前驱和后继节点访问操作,而单向链表则需要O(n)时间复杂度的遍历操作才能找到前驱节点。
  3. 双向链表相对于单向链表来说,其插入和删除节点的操作更加高效,因为只需要改变前后节点的指针指向即可,而单向链表需要先找到前驱节点再进行操作。

因此,双向链表在实现一些需要频繁插入和删除操作的场景下,比单向链表更加适用。Java中的LinkedList就是基于双向链表实现的,所以它能够高效地支持插入、删除等操作,同时也提供了迭代器和列表迭代器等许多方便的操作。

2.3 LinkedList如何实现了链表的基本操作(增删改查)

在Java中,LinkedList类实现了链表的基本操作,包括增加(添加)、删除、修改和查询等功能。下面是一些常用的方法:

  1. 添加操作:
    • addFirst(E e):在链表的开头添加元素。
    • addLast(E e):在链表的末尾添加元素。
    • add(int index, E element):在指定位置插入元素。
  2. 删除操作
    • removeFirst():删除链表的第一个元素。
    • removeLast():删除链表的最后一个元素。
    • remove(int index):删除指定位置的元素。
    • remove(Object o):删除指定元素。
  3. 修改操作
    • set(int index, E element):将指定位置的元素替换为新的元素。
  4. 查询操作
    • getFirst():返回链表的第一个元素。
    • getLast():返回链表的最后一个元素。
    • get(int index):返回指定位置的元素。
    • indexOf(Object o):返回指定元素在链表中的索引位置。
    • contains(Object o):判断链表是否包含指定元素。

LinkedList类还提供了其他一些方法用于获取链表的大小、清空链表、判断链表是否为空等。

2.4 LinkedList的遍历方式

在Java中,你可以使用以下几种方式对LinkedList进行遍历:

1.使用迭代器(Iterator)进行遍历

LinkedList<String> linkedList = new LinkedList<>();
// 假设已经向linkedList中添加了元素
Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    // 对element进行处理
}

2.使用增强型for循环(foreach)进行遍历

LinkedList<String> linkedList = new LinkedList<>();
// 假设已经向linkedList中添加了元素
for (String element : linkedList) {
    // 对element进行处理
}

这两种方式都可以用来遍历LinkedList中的元素,你可以根据实际情况选择其中一种来进行遍历操作。

三、 源码分析

3.1 成员变量

在这里插入图片描述

3.2 构造方法

/**
 * 默认构造函数,它不带任何参数,用来创建一个空的 LinkedList 对象
 */
public LinkedList() {
}

/**
 * 带有参数的构造函数,它接受一个类型为 Collection 的参数 c
 */
public LinkedList(Collection<? extends E> c) {
    // 调用无参构造函数
    this();
    // 将参数 c 中的所有元素添加到新创建的 LinkedList 对象中
    addAll(c);
}

/**
 * LinkedList 类中的 addAll 方法的定义
 */
public boolean addAll(Collection<? extends E> c) {
    // size表示为当前 LinkedList 中的元素数量
    // 调用另一个名为 addAll 的方法来将参数 c 中的所有元素添加到 LinkedList 对象中
    return addAll(size, c);
}

/**
 * 用于将指定集合中的元素插入到指定位置
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 检查索引的有效性,确保索引在范围内
    checkPositionIndex(index);

    // 将集合 c 转换为数组,并将其赋值给对象数组 a
    Object[] a = c.toArray();
    // 获取新添加元素的数量
    int numNew = a.length;
    // 如果新添加元素的数量为 0,则直接返回 false
    if (numNew == 0)
        return false;

    // 定义两个节点,pred 表示当前节点的前一个节点,succ 表示当前节点的后一个节点
    LinkedList.Node<E> pred, succ;
    // 根据插入位置确定 succ 和 pred 的值
    // 如果插入位置在末尾,则将 succ 设置为 null,将 pred 设置为最后一个节点
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        // 否则,通过 node(index) 方法找到指定位置的节点,并将其设置为 succ,同时将其前一个节点设置为 pred
        succ = node(index);
        pred = succ.prev;
    }

    // 遍历数组 a 中的元素
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        // 将每个元素转换为泛型类型 E,并创建一个新的节点 newNode,该节点的前一个节点为 pred,值为 e,后一个节点为 null
        LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, null);
        // 如果 pred 为 null,则将 newNode 设置为链表的第一个节点
        if (pred == null)
            first = newNode;
        else
            // 否则,将 pred 的下一个节点设置为 newNode
            pred.next = newNode;
        // 将 pred 更新为 newNode
        pred = newNode;
    }

    // 根据 succ 是否为 null 来确定插入后的链表结构
    // 如果 succ 为 null,则表示插入位置在末尾,将 pred 设置为最后一个节点
    if (succ == null) {
        last = pred;
    } else {
        // 否则,将 pred 的下一个节点设置为 succ,并将 succ 的前一个节点设置为 pred
        pred.next = succ;
        succ.prev = pred;
    }

    // 更新链表的大小和修改计数器
    size += numNew;
    modCount++;
    // 返回 true,表示添加操作成功完成
    return true;
}

3.3 add()方法

/**
 * 用于向链表末尾添加一个元素 e
 */
public boolean add(E e) {
    // 将元素 e 添加到链表的末尾
    linkLast(e);
    // 添加操作成功
    return true;
}

/**
 * 向链表末尾添加一个元素的操作
 */
void linkLast(E e) {
    // 创建一个名为 l 的局部变量,用于保存当前链表的最后一个节点的引用,通过访问 last 字段获取最后一个节点的引用
    final LinkedList.Node<E> l = last;
    // 创建一个新的节点 newNode,并将其初始化为一个具有前驱节点为 l、元素为 e、后继节点为 null 的节点
    final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
    // 将链表的 last 指针指向新的节点 newNode,使其成为最后一个节点
    last = newNode;
    // 如果 l 为空(即链表为空),则将链表的 first 指针指向新的节点 newNode,否则将 l 节点的后继节点指向新的节点 newNode
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    // 增加链表的大小,将链表中元素的数量加1
    size++;
    // 增加修改计数器 modCount 的值,用于追踪链表结构的修改次数
    modCount++;
}

3.4 remove()方法

/**
 * 用于从 LinkedList 中删除指定的元素
 */
public boolean remove(Object o) {
    // 判断传入的参数 o 是否为 null
    // 如果 o 为 null,则说明要删除的元素是 null 值
    if (o == null) {
        // 因此需要遍历 LinkedList 中的所有节点并查找 item 属性为 null 的节点
        // 循环体中的变量 x 表示当前正在遍历的节点,初始化为 first(即头节点),在每次迭代后更新为下一个节点,直到遍历完整个 LinkedList
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            // 如果当前节点的 item 属性为 null(在 o 为 null 的情况下),则调用辅助方法 unlink 删除该节点并返回 true
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        // 否则需要遍历所有节点并查找 item 属性等于 o 的节点
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            // 如果当前节点的 item 属性等于 o(在 o 不为 null 的情况下),则调用辅助方法 unlink 删除该节点并返回 true
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * 这是一个辅助方法,用于删除指定节点 x
 */
E unlink(LinkedList.Node<E> x) {
    // assert x != null;
    // 保存被删除节点的元素值
    final E element = x.item;
    // 存储被删除节点的前驱和后继节点
    final LinkedList.Node<E> next = x.next;
    final LinkedList.Node<E> prev = x.prev;

    // 如果被删除节点是头节点,则将头指针指向其后继节点
    if (prev == null) {
        first = next;
    } else {
        // 否则更新被删除节点的前驱节点的 next 属性为其后继节点,并将被删除节点的 prev 属性设为 null
        prev.next = next;
        x.prev = null;
    }

    // 如果被删除节点是尾节点,则将尾指针指向其前驱节点
    if (next == null) {
        last = prev;
    } else {
        // 否则更新被删除节点的后继节点的 prev 属性为其前驱节点,并将被删除节点的 next 属性设为 null
        next.prev = prev;
        x.next = null;
    }

    // 将被删除节点的 item 属性设为 null
    x.item = null;
    // 更新 LinkedList 的元素数量和修改次数
    size--;
    modCount++;
    // 返回被删除节点的元素值
    return element;
}

3.5 get()方法

/**
 * 用于获取指定索引处的元素
 */
public E get(int index) {
    // 检查索引的有效性,然后调用另一个私有辅助方法 node 来获取对应索引处的节点
    checkElementIndex(index);
    // 返回该节点的元素值
    return node(index).item;
}

/**
 * 检查指定索引是否在有效范围内
 */
private void checkElementIndex(int index) {
    // 调用 isElementIndex 方法来判断索引是否在有效范围内
    if (!isElementIndex(index))
        // 如果不在,则抛出 IndexOutOfBoundsException 异常,异常消息由 outOfBoundsMsg 方法返回
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 判断指定索引是否在有效范围内
 */
private boolean isElementIndex(int index) {
    // 如果索引大于等于 0 并且小于 size,则返回 true;否则返回 false
    return index >= 0 && index < size;
}

3.6 set()方法

/**
 * 用于将指定索引(index)位置的元素替换为新的元素,并返回被替换掉的旧元素
 */
public E set(int index, E element) {
    // 用于将指定索引(index)位置的元素替换为新的元素,并返回被替换掉的旧元素
    checkElementIndex(index);
    // 获取指定索引位置上的节点
    LinkedList.Node<E> x = node(index);
    // 将指定索引位置上的节点的元素值赋给变量 oldVal,即记录旧元素的值
    E oldVal = x.item;
    // 将指定索引位置上的节点的元素值替换为新的元素值 element
    x.item = element;
    // 返回被替换掉的旧元素值
    return oldVal;
}

/**
 * 检查指定索引是否在有效范围内
 */
private void checkElementIndex(int index) {
    // 调用 isElementIndex 方法来判断索引是否在有效范围内
    if (!isElementIndex(index))
        // 如果不在,则抛出 IndexOutOfBoundsException 异常,异常消息由 outOfBoundsMsg 方法返回
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * 判断指定索引是否在有效范围内
 */
private boolean isElementIndex(int index) {
    // 如果索引大于等于 0 并且小于 size,则返回 true;否则返回 false
    return index >= 0 && index < size;
}

3.7 clear()方法

/**
 * 用于清空整个链表的内容,并释放相关的内存空间
 */
public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // 解释了清除所有节点之间链接的操作虽然“不必要”,但有两个原因:
    // - helps a generational GC if the discarded nodes inhabit
    // 帮助分代垃圾回收(generational GC)
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    // 和确保释放内存即使存在可达的迭代器
    // 循环体中的变量 x 初始化为头节点 first,然后在每次迭代中更新为下一个节点,直到遍历完整个链表
    for (LinkedList.Node<E> x = first; x != null; ) {
        // 用于保存当前节点 x 的后继节点的引用,以防止在清空当前节点之后丢失对后继节点的引用
        LinkedList.Node<E> next = x.next;
        // 将当前节点 x 的元素值、前驱节点和后继节点都设置为 null,从而切断当前节点与前后节点的关联
        x.item = null;
        x.next = null;
        x.prev = null;
        // 将 x 更新为下一个节点,以便进行下一次循环迭代
        x = next;
    }
    // 清空头节点和尾节点的引用,使整个链表为空
    first = last = null;
    // 将链表的大小设置为 0,表示链表中不再包含任何元素
    size = 0;
    // 更新修改次数计数器,用于在迭代过程中检测并发修改
    modCount++;
}

3.8 indexOf()方法

/**
 * 用于查找指定元素在链表中第一次出现的位置(索引)
 */
public int indexOf(Object o) {
    // 初始化索引变量为 0,表示从头节点开始查找
    int index = 0;
    // 如果要查找的元素 o 是 null,则执行下面的 for 循环,按顺序遍历链表,查找第一个元素值为 null 的节点
    if (o == null) {
        // 变量 x 初始化为头节点 first,然后在每次迭代中更新为下一个节点,直到遍历完整个链表
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            // 判断当前节点 x 的元素值是否为 null,如果是,则说明找到了要查找的元素,返回当前索引 index 表示该元素在链表中的位置
            if (x.item == null)
                return index;
            // 如果当前节点不是要查找的元素,则将索引变量 index 加 1,继续向下查找
            index++;
        }
    } else {
        // 如果要查找的元素 o 不是 null,则执行下面的 for 循环,按顺序遍历链表,查找第一个元素值与 o 相等的节点
        for (LinkedList.Node<E> x = first; x != null; x = x.next) {
            // 判断当前节点 x 的元素值是否与要查找的元素 o 相等,如果是,则说明找到了要查找的元素,返回当前索引 index 表示该元素在链表中的位置
            if (o.equals(x.item))
                return index;
            // 如果当前节点不是要查找的元素,则将索引变量 index 加 1,继续向下查找
            index++;
        }
    }
    // 如果整个链表都遍历完了还没有找到要查找的元素,则返回 -1,表示该元素不存在于链表中
    return -1;
}

四、 总结及实战应用

4.1 LinkedList适用场景

LinkedList在Java中适用于以下场景

  1. 需要频繁进行插入和删除操作:由于LinkedList是基于链表结构实现的,插入和删除操作的时间复杂度为O(1),因此适合在需要频繁执行这些操作的场景下使用。
  2. 需要实现队列(Queue)或双端队列(Deque)功能:LinkedList实现了QueueDeque接口,可以作为队列或双端队列来使用。
  3. 不需要频繁进行随机访问:由于LinkedList对于随机访问的效率较低,如果不需要频繁通过索引来访问元素,而是更多地进行顺序访问或者在头尾进行操作,那么LinkedList比较适合。
  4. 对内存占用没有过高要求:相比于ArrayList,在一些情况下,由于它的存储结构,LinkedList可能会占用更多的内存空间。

需要注意的是,在某些特定的场景下,可能需要根据具体的需求进行性能测试和选择,以确定使用LinkedList是否能够带来性能上的提升。

4.2 LinkedList与ArrayList的比较

LinkedList和ArrayList是Java中两种常见的集合实现类,它们具有一些不同的特点和适用场景。

LinkedList的特点

  • 基于双向链表实现,每个节点都包含指向前一个节点和后一个节点的引用。
  • 高效地支持插入和删除操作,因为只需要改变前后节点的指针指向即可。
  • 在使用迭代器进行遍历时,效率较高。
  • 对于频繁的插入和删除操作,LinkedList通常比ArrayList更加高效。

ArrayList的特点

  • 基于动态数组实现,内部使用数组来存储元素。
  • 支持随机访问,通过索引可以快速访问元素。
  • 在获取元素和遍历操作方面,ArrayList相对更高效。
  • 对于需要频繁随机访问元素的操作,ArrayList通常比LinkedList更加高效。

综上所述,选择LinkedList还是ArrayList取决于具体的使用场景和需求

  • 如果需要频繁进行插入和删除操作,而对于随机访问的需求较少,则选择LinkedList更合适。
  • 如果需要频繁进行随机访问,插入和删除操作相对较少,则选择ArrayList更合适。

需要注意的是,在多线程环境下,LinkedList和ArrayList都不是线程安全的,如果需要在多线程环境下使用,需要进行适当的同步处理或使用线程安全的集合类。

4.3 LinkedList的使用注意事项

在使用 Java 中的 LinkedList 时,有一些需要注意的事项,包括但不限于以下几点:

  1. 插入和删除效率高:LinkedList 在插入和删除操作上有较高的效率,因为它基于双向链表实现。因此,在需要频繁进行插入和删除操作的场景下,可以考虑使用 LinkedList。
  2. 随机访问效率低:相比于 ArrayList,LinkedList 对于随机访问的效率较低,因为要通过指针一个个地找到目标位置。因此,在需要频繁进行随机访问的场景下,最好选择 ArrayList。
  3. 迭代器遍历高效:LinkedList 的迭代器遍历效率较高,可以高效地进行前向和后向遍历操作。
  4. 注意空间开销:由于 LinkedList 中每个节点都需要存储额外的指针信息,因此相比于 ArrayList,它在存储同样数量的元素时会占用更多的内存空间。
  5. 不是线程安全的:LinkedList 不是线程安全的,如果需要在多线程环境中使用,需要进行适当的同步处理或考虑使用线程安全的集合类。
  6. 谨慎使用大数据量:在处理大数据量的情况下,由于 LinkedList 涉及频繁的节点创建和指针操作,可能会导致性能下降,需要谨慎使用。

综上所述,使用 LinkedList 时需要根据具体的场景和需求进行权衡,特别是在涉及到插入、删除、遍历和空间占用等方面需要特别留意。

4.4 实战应用:设计一个基于LinkedList的LRU缓存算法

LRU(Least Recently Used)算法是一种缓存置换策略,它根据数据最近被访问的时间来决定哪些数据会被保留,哪些数据会被淘汰。在 Java 中,可以通过 LinkedList HashMap 来实现 LRU 缓存算法。

具体实现步骤如下

1.定义一个双向链表和一个哈希表,用于存储缓存数据和快速定位数据。

private class CacheNode {
  private String key;
  private Object value;
  private CacheNode prev;
  private CacheNode next;

  public CacheNode(String key, Object value) {
    this.key = key;
    this.value = value;
  }
}

private Map<String, CacheNode> cacheMap;
private CacheNode head;
private CacheNode tail;
private int capacity;

2.在构造函数中初始化双向链表和哈希表,并设置缓存容量。

public LRUCache(int capacity) {
  this.capacity = capacity;
  cacheMap = new HashMap<>(capacity);
  head = new CacheNode(null, null);
  tail = new CacheNode(null, null);
  head.next = tail;
  tail.prev = head;
}

3.实现 get 方法,每次获取数据时,将数据移到链表头部,并更新哈希表中的位置信息。

public Object get(String key) {
  CacheNode node = cacheMap.get(key);
  if (node == null) {
    return null;
  }
  // 将节点移动到链表头部
  moveToHead(node);
  return node.value;
}

private void moveToHead(CacheNode node) {
  // 先将节点从原有位置删除
  removeNode(node);
  // 将节点插入到链表头部
  insertNodeAtHead(node);
}

private void removeNode(CacheNode node) {
  node.prev.next = node.next;
  node.next.prev = node.prev;
}

private void insertNodeAtHead(CacheNode node) {
  node.next = head.next;
  node.next.prev = node;
  head.next = node;
  node.prev = head;
}

4.实现 put 方法,每次存储数据时,如果缓存已满,则淘汰链表尾部的数据,并在哈希表中删除相应的位置信息。

public void put(String key, Object value) {
  CacheNode node = cacheMap.get(key);
  if (node != null) {
    // 如果键已经存在,则更新值,并移到链表头部
    node.value = value;
    moveToHead(node);
  } else {
    // 如果键不存在,则插入新节点到链表头部,并添加位置信息到哈希表
    node = new CacheNode(key, value);
    cacheMap.put(key, node);
    insertNodeAtHead(node);
    if (cacheMap.size() > capacity) {
      // 如果缓存已满,则淘汰链表尾部的节点,并删除相应位置信息
      CacheNode removedNode = removeNodeAtTail();
      cacheMap.remove(removedNode.key);
    }
  }
}

private CacheNode removeNodeAtTail() {
  CacheNode removedNode = tail.prev;
  removeNode(removedNode);
  return removedNode;
}

这样,一个基于 LinkedList 的 LRU 缓存算法就实现了。

可以通过如下代码进行简单的测试

LRUCache cache = new LRUCache(2);
cache.put("A", 1);
cache.put("B", 2);
System.out.println(cache.get("A")); // 输出 1
cache.put("C", 3);
System.out.println(cache.get("B")); // 输出 null

盈若安好,便是晴天

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/271313.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

静态HTTP的未来:探讨新技术趋势

在Web的世界里&#xff0c;静态HTTP一直是个不可或缺的角色。它就像一个尽职尽责的邮递员&#xff0c;确保数据安全、准确地送达目的地。但随着时代的发展&#xff0c;邮递员也需要跟上潮流&#xff0c;不断学习和进步。那么&#xff0c;静态HTTP的未来会是怎样的呢&#xff1f…

CMMI-项目总体计划模版

目录 1、总体目录结构 2、重点章节概要示例 2.1 第四章 项目管理 2.2 第六章 实施与交付计划 2.3 第七章 运维计划 1、总体目录结构 2、重点章节概要示例 2.1 第四章 项目管理 2.2 第六章 实施与交付计划 2.3 第七章运维计划

从流星雨启程:Python和Pygame下载与安装全过程

文章目录 一、前言二、下载安装过程1.官网下载安装包2.安装python过程第一步第二步第三步第四步第五步安装完成 3.简单测试Python3.1 检查 Python 版本号3.2 打开 Python 解释器3.3 输入你的第一个代码3.4 运行 Python 脚本 4.安装Pygame4.1 cmd命令安装Pygame4.2 pip升级4.3 安…

C++的面向对象学习(6):运算符的重载

文章目录 前言&#xff1a;什么是运算符重载&#xff1f;针对自定义的类与对象类型。一、加号的运算符重载1.引入背景2.所以运算符重载的作用&#xff1a;3.实现对象间的相加代码&#xff1a;号运算符重载①在类中实现加号运算符重载②设计全局函数实现加号运算符重载③改写函数…

基于QListWidget的多段曲线展示器

目录 1 开发背景 2 创建程序 3 更改main window函数 4 测试构造函数 5 文件打开函数 6 拖放的实现 1 开发背景 由于视图控件的拖放逻辑比较难&#xff0c;需要同时子类化视图和模型&#xff0c;那么对于小数据而言&#xff0c;不如使用便捷类。因此&#xff0c;决定对多…

JavaOOP篇----第十八篇

系列文章目录 文章目录 系列文章目录前言一、什么是成员内部类二、Static Nested Class 和 Inner Class的不同三、什么时候用assert四、Java有没有goto前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女…

探索音乐创作的新境界——PreSonus Studio One Pro 6

音乐是人类情感的表达方式之一&#xff0c;而音乐制作编曲软件则是让人们将创意转化为音乐作品的重要工具之一。在众多软件中&#xff0c;PreSonus Studio One Pro 6凭借其强大的功能和出色的用户体验&#xff0c;成为了许多音乐制作人的首选。 首先&#xff0c;PreSonus Stud…

App应用如何在应用市场获得更多下载量?

App的转化率至关重要&#xff0c;App如何获得更多用户&#xff0c;提高应用的下载量&#xff1f; 据 Apple 称&#xff0c;每周有 6.5亿访问者访问应用商店&#xff0c;77%的应用下载来自 iOS 应用商店的自然搜索。随着 Apple 默认关闭了IDFA&#xff0c;自然搜索比以往任何时…

git之UGit可视化工具使用

一、下载安装UGit 链接&#xff1a;https://pan.baidu.com/s/1KGJvWkFL91neI6vAxjGAag?pwdsyq1 提取码&#xff1a;syq1 二 、使用SSH进行远程仓库连接 1.生成SSH密钥 由于我们的本地 git仓库和 gitee仓库之间的传输是通过SSH加密的&#xff0c;所以我们需要配置SSH公钥。才…

结合教学经验谈计量经济学与Stata软件的学习

1.经济金融专业学生计量学习之痛 教学实践中&#xff0c;很多学生跟我抱怨计量经济学难学的问题&#xff0c;也有很多研0的同学感觉本科阶段没学好&#xff0c;或者跨专业考研的同学&#xff0c;在知道了计量经济学的重要性之后&#xff0c;对于经济金融领域的“无计量、不科研…

Kind创建k8s - JAVA操作控制

kind 简介kind 架构安装 Kind (必备工具)docker官网kubectl官网kind官网校验安装结果 关于kind 命令 安装一个集群查看当前 Kubernetes 集群中的节点信息。查看当前命名空间下中的Pod&#xff08;容器实例&#xff09;的信息。使用 kind create cluster 安装&#xff0c;关于安…

智能优化算法应用:基于浣熊算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于浣熊算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于浣熊算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.浣熊算法4.实验参数设定5.算法结果6.参考文献7.MA…

中后缀表达式

一、利用后缀表达式进行计算 1&#xff09;解题思路 如果当前字符串是操作数&#xff0c;就将该操作数入栈&#xff1b;如果当前字符串是操作符&#xff0c;就取栈顶的两个操作数进行运算&#xff08;注意&#xff1a;第一个出栈的数为计算时的右操作数&#xff1b;第二个出栈…

继电器负载的使用方法有哪些?

继电器是通过电磁效应或电热效应实现电路的自动开关。继电器负载是指继电器所控制的负载&#xff0c;通常包括电机、灯泡、加热器等。正确使用继电器负载可以确保设备的正常运行和安全。以下是一些使用继电器负载的方法&#xff1a; 选择合适的继电器&#xff1a;根据负载的类型…

基于java+控件台+mysql的学生信息管理系统(含演示视频)

基于java控件台mysql的学生信息管理系统_含演示视频 一、系统介绍二、功能展示1.项目内容2.项目骨架3.数据库4.登录系统5.新增学生6.查询学生7.修改学生8.删除学生9.退出系统 四、其它1.其他系统实现五.获取源码 一、系统介绍 项目类型&#xff1a;Java SE项目&#xff08;控制…

大数据开发之Sqoop详细介绍

测试环境 CDH 6.3.1 Sqoop 1.4.7 一.Sqoop概述 Apache Sqoop&#xff08;SQL-to-Hadoop&#xff09;项目旨在协助RDBMS与Hadoop之间进行高效的大数据交流。用户可以在 Sqoop 的帮助下&#xff0c;轻松地把关系型数据库的数据导入到 Hadoop 与其相关的系统 (如HBase和Hive)中&…

Java经典框架之Spring MVC

Spring MVC Java 是第一大编程语言和开发平台。它有助于企业降低成本、缩短开发周期、推动创新以及改善应用服务。如今全球有数百万开发人员运行着超过 51 亿个 Java 虚拟机&#xff0c;Java 仍是企业和开发人员的首选开发平台。 课程内容的介绍 1. Spring MVC 入门案例 2. 基…

Github 2023-12-23 开源项目日报 Top10

根据Github Trendings的统计&#xff0c;今日(2023-12-23统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目6C项目2C项目1Jupyter Notebook项目1HTML项目1Go项目1非开发语言项目1 免费API集体清单 创建周期…

【中小型企业网络实战案例 二】配置网络互连互通

​【中小型企业网络实战案例 一】规划、需求和基本配置-CSDN博客 热门IT技术视频教程&#xff1a;https://xmws-it.blog.csdn.net/article/details/134398330?spm1001.2014.3001.5502 配置接入层交换机 1.以接入交换机ACC1为例&#xff0c;创建ACC1的业务VLAN 10和20。 <…

哪些超声波清洗机值得买?五款超声波清洗机实测大对比!

在当今快节奏的生活中&#xff0c;我们对于日常用品的清洁度要求越来越高。为了满足这一需求&#xff0c;超声波清洗机应运而生&#xff0c;以其高效、便捷的清洁方式赢得了广泛的市场。然而&#xff0c;面对市场上琳琅满目的超声波清洗机品牌和型号&#xff0c;很多时候都是无…