LinkedList使用详解

概述

LinkedList是一个功能十分强大的集合，看它的名字可能误以为只有List顺序容器的功能，实际上它还可以作为一个双端队列，也可以作为一个栈来使用。那么我们以java8版本来对LinkedList做一个功能讲解和使用体验。

功能介绍

LinkedList底层的数据结构是双向的链表。

特点：

• 底层数据结果是双向链表，插入删除速度快，查找速度慢。
• LinkedList可以作为一个顺序容器使用
• LInkedList可以作为一个队列使用，元素先进先出
• LinkedList可以作为一个栈使用, 元素先进后出
• 允许放入null元素
• 不是线程安全，并发修改的时候会抛出ConcurrentModificationException异常

构造方法

1. LinkedList()

说明：构造一个空容器

2. LinkedList(Collection<? extends E> c)

说明：构造一个内容为入参容器c的的容器。

有序列表相关方法

1. boolean add(E e)

说明: 向集合中添加元素

2. void add(int index, E element)

说明: 向集合指定位置后面添加一个元素

3. boolean addAll(Collection<? extends E> c)

说明: 向集合中添加另外一个集合的元素

4. boolean addAll(int index, Collection<? extends E> c)

说明: 向集合指定位置后面添加另外一个集合的全部元素

5. E set(int index, E element)

说明: 设置集合中某个位置元素的值，返回修改前的内容

6. boolean remove(Object o)

说明：删除集合中碰到的第一和o一样的元素，如果集合发生变化返回true

7. E remove(int index)

说明：删除集合中某个位置的元素，返回删除的元素内容

8. boolean removeAll(Collection<?> c)

说明：根据入参的集合，删除集合里面一样的元素，如果集合发生变化，返回true

9. void clear()

说明：清空集合中的元素

10. int size()

说明：返回容器中元素的数量

11. boolean isEmpty()

说明：返回容器是否是空的，如果是空，返回true

12. boolean contains(Object o)

说明：返回容器是否包含指定对象

13. E get(int index)

说明：获取指定索引位置的元素

14. int indexOf(Object o)

说明：从头部开始找，获取查找到指定元素的第一个索引位置， 如果返回-1表示没有找到

队列相关方法

1. boolean offer(E e)

说明：队列中添加元素，往队列尾部添加元素

2. E poll()

说明：从队列中获取元素，拿到的是最先放进去的，也就是头部的元素

3. boolean offerFirst(E e)

说明：队列头部添加元素。

4. boolean offerLast(E e)

说明：队列尾部添加元素

5. E pollFirst()

说明：队列头部获取元素

6. E pollLast()

说明：队列尾部获取元素

栈相关方法

1. void push(E e)

说明：向栈中压入元素，也就是头部添加元素

2. E pop()

说明：从栈中获取元素，相当于从队列头部获取元素

3. E peek()

说明：查看栈顶元素

使用案例和总结

有序列表的使用

@Test
    public void testListFunc() {
        List<String> userNames = new LinkedList<>();
        userNames.add("alvin");
        userNames.add("cxw");
        userNames.add("hh");
        userNames.add("ss");
        String username = userNames.get(2);
        Assert.assertEquals("hh", username);
    }

小结：

ArrayList 是基于动态数组数据结构的实现，访问元素速度优于 LinkedList。LinkedList 是基于链表数据结构的实现，占用的内存空间比较大，但在批量插入或删除数据时优于 ArrayList。

对于快速访问对象的需求，使用 ArrayList 实现执行效率上会比较好。需要频繁向集合中插入和删除元素时，使用 LinkedList 类比 ArrayList 类效果高。

队列的使用

@Test
    public void testQueueFunc() {
        Deque<String> userNames = new LinkedList<>();
        userNames.offer("alvin");
        userNames.offer("cxw");
        userNames.offer("kk");
        String username = userNames.poll();
        Assert.assertEquals("alvin", username);
    }

小结： LinkedList可以支持队列的功能，底层通过队列实现，同样还有一个类ArrayDeque也支持，底层通过数组实现，通常情况下，ArrayDeque的性能和内存开销更优。

栈的使用

@Test
    public void testStackFunc() {
        Deque<String> userNames = new LinkedList<>();
        userNames.push("alvin");
        userNames.push("cxw");
        userNames.push("kk");
        String username = userNames.peek();
        Assert.assertEquals("kk", username);
        username = userNames.pop();
        Assert.assertEquals("kk", username);
    }

小结： java中有个有Stack的类支持栈的功能，它是线程安全的，性能查，不推荐使用。LinkedList可以栈的功能，底层通过队列实现，同样还有一个类ArrayDeque也支持，底层通过数组实现，通常情况下，ArrayDeque的性能和内存开销更优。

使用注意事项

1. LinkedList底层采用双向队列实现，不需要进行扩容操作，在频繁插入和删除的场景性能更佳。
2. 在 subList 场景中，高度注意对父集合元素的增加或删除，均会导致子列表的遍历、增加、删除产生 ConcurrentModificationException 异常。 说明：抽查表明，90% 的程序员对此知识点都有错误的认知。
3. 使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为0 的空数组。
4. 使用 Collection 接口任何实现类的 addAll() 方法时，要对输入的集合参数进行 NPE 判断。

说明：在 ArrayList#addAll 方法的第一行代码即 Object[] a = c.toArray()；其中 c 为输入集合参数，如果为 null，则直接抛出异常。

5. 不要在 foreach 循环里进行元素的 remove / add 操作。remove 元素请使用 iterator 方式，如果并发操作，需要对 iterator 对象加锁。
6. 使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法，它的 add/ remove / clear 方法会抛出 UnsupportedOperationException 异常。
7. Collections 类返回的对象，如：emptyList() / singletonList() 等都是 immutable list，不可

对其进行添加或者删除元素的操作。