Java LinkedList 类详解及实例代码

介绍

Java中的LinkedList类是一个双向链表的实现，是List接口的有序集合。LinkedList类提供了方便的操作链表的方法，可以很容易地实现添加、删除、插入以及访问节点等操作。

以下是创建一个LinkedList的示例：

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

常用方法

以下是一些常用的LinkedList方法：

1. add(E e) - 在链表末尾添加一个元素
2. add(int index, E element)- 在链表指定位置添加一个元素
3. remove() - 删除链表的头元素
4. remove(int index) - 删除链表中指定位置的元素
5. get(int index) - 返回链表中指定位置的元素
6. size() - 返回链表中元素的数量
7. clear() - 删除链表中的所有元素

以下是示例代码：

LinkedList<String> linkedList = new LinkedList<String>();
linkedList.add("Java");
linkedList.add("Python");
linkedList.add("JavaScript");
linkedList.add("PHP");

//获取链表的元素数
System.out.println("链表元素数量：" + linkedList.size());

//获取链表中指定位置的元素
System.out.println("链表第二个元素：" + linkedList.get(1));

//在链表指定位置添加一个元素
linkedList.add(1, "C++");

//删除链表末尾的元素
linkedList.removeLast();

输出结果：

链表元素数量：4
链表第二个元素：Python

示例说明

示例1 - 使用LinkedList实现LRU Cache

以下示例展示了使用LinkedList实现LRU Cache。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class LRUCache {

    private Map<Integer, Integer> cache; //用来存储缓存的键值对
    private LinkedList<Integer> list; //用来存储缓存的键
    private int capacity; //LRU Cache的容量

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<Integer, Integer>();
        list = new LinkedList<Integer>();
    }

    public int get(int key) {
        if(cache.containsKey(key)) {
            //将键移动到链表头部
            list.remove((Integer)key);
            list.addFirst(key);
            return cache.get(key);
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            list.remove((Integer)key);
        } else {
            if(cache.size() == capacity) {
                int lastKey = list.removeLast();
                cache.remove(lastKey);
            }
        }
        list.addFirst(key);
        cache.put(key, value);
    }
}

以上代码实现了LRU Cache的基本功能，包括了缓存容量的限制、查找缓存、添加缓存等操作。

示例2 - 使用LinkedList实现栈

以下示例展示了使用LinkedList实现栈。

import java.util.LinkedList;

class Stack<T> {

    private LinkedList<T> list; //用来存储栈中的元素

    public Stack() {
        list = new LinkedList<T>();
    }

    //将一个元素压入栈顶
    public void push(T data) {
        list.addFirst(data);
    }

    //从栈顶弹出一个元素
    public T pop() {
        if(list.isEmpty()) {
            return null;
        } else {
            return list.removeFirst();
        }
    }

    //返回栈顶的元素，但不弹出
    public T peek() {
        if(list.isEmpty()) {
            return null;
        } else {
            return list.getFirst();
        }
    }

    //判断栈是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }
}

以上代码实现了栈的基本功能，包括了压入元素、弹出元素、判断栈是否为空等操作。