Java LinkedList原理及实例详解

什么是LinkedList

LinkedList是Java中的一个双向链表数据结构。双向链表数量级比较大时，性能好于ArrayList，但是在随机访问的情况下性能不如ArrayList。因为LinkedList内部存储元素的方式是基于链表节点的引用来存储，而不是基于数组下标的方式。

LinkedList的基本操作

创建LinkedList对象

创建LinkedList对象可以使用默认构造函数，也可以直接使用初始化器创建。

LinkedList<String> linkedList = new LinkedList<>();

或者

LinkedList<Integer> linkedList = new LinkedList<>(Arrays.asList(1, 2, 3));

添加元素

LinkedList提供了两种添加元素的方法：add() 和 addFirst()。

linkedList.add("a");
linkedList.add(1);
linkedList.addFirst("First");

获取元素

获取LinkedList中的元素也提供了两种方式：get() 和 getFirst()。

String a = linkedList.get(1);
String first = linkedList.getFirst();

删除元素

LinkedList提供了三种删除元素的方式：remove()、removeFirst()和removeLast()。

linkedList.remove("a");
linkedList.removeFirst();
linkedList.removeLast();

修改元素

LinkedList中的元素可以使用set()方法进行修改。

linkedList.set(0, "newFirst");

LinkedList实例演示

实例一：用LinkedList实现队列

public class Queue<E> {
    private LinkedList<E> linkedList = new LinkedList<>();

    public void add(E element) {
        linkedList.add(element);
    }

    public E remove() {
        return linkedList.removeFirst();
    }

    public E peek() {
        return linkedList.getFirst();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }
}

实例二：用LinkedList实现LRU Cache（Least Recently Used Cache）

public class LRUCache<K, V> {
    private final int MAX_CACHE_SIZE;
    private final float DEFAULT_LOAD_FACTOR = 0.75f;

    private LinkedHashMap<K, V> map;

    public LRUCache(int cacheSize) {
        MAX_CACHE_SIZE = cacheSize;
        int capacity = (int)Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1;
        map = new LinkedHashMap<K, V>(capacity, DEFAULT_LOAD_FACTOR, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > MAX_CACHE_SIZE;
            }
        };
    }

    public synchronized V get(K key) {
        return map.get(key);
    }

    public synchronized void put(K key, V value) {
        map.put(key, value);
    }

    public synchronized void clear() {
        map.clear();
    }

    public synchronized int usedSize() {
        return map.size();
    }

    public void print() {
        for (Map.Entry<K, V> entry : map.entrySet()) {
            System.out.println(String.format("%s:%s", entry.getKey(), entry.getValue()));
        }
    }
}

以上就是Java LinkedList的原理及实例详解。