9.3LinkedList设计思想

目录介绍

01.LinkedList简介
02.内部结构分析
03.常用方法测试
04.LinkedList类声明
05.几个常用的方法
06.list效率比较

00.一些常见问题思考

LinkedList集合有何特点？LinkedList相比ArrayList效率如何？用什么进行论证？

01.LinkedList简介

LinkedList具有的特点
- LinkedList 同时实现了 List 接口和 Deque 接口，所以既可以将 LinkedList 当做一个有序容器，也可以将之看作一个队列（Queue），同时又可以看作一个栈（Stack）。
- 虽然 LinkedList 和 ArrayList 一样都实现了 List 接口，但其底层是通过双向链表来实现的，所以 LinkedList 插入和删除元素的效率都要比 ArrayList 高，因此随机访问的效率也要比 ArrayList 低。
简单总结一下
- 实现了List接口和Deque接口，是双端链表
- 支持高效的插入和删除操作
- 不是线程安全的
如果想使LinkedList变成线程安全的
- 可以调用静态类
```
List list =Collections.synchronizedList(new LinkedList(...));
```

02.内部结构分析

如下图所示：
- LinkedList内部结构

看完了图之后，我们再看LinkedList类中的一个就很好理解了：

private static class Node<E> {
    E item;//节点值
    Node<E> next;//后继节点
    Node<E> prev;//前驱节点

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

这个类就代表双端链表的节点Node。这个类有三个属性，分别是前驱节点，本节点的值，后继结点。

03.常用方法测试

package list;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] srgs) {
        //创建存放int类型的linkedList
        LinkedList<Integer> linkedList = new LinkedList<>();
        /************************** linkedList的基本操作 ************************/
        linkedList.addFirst(0); // 添加元素到列表开头
        linkedList.add(1); // 在列表结尾添加元素
        linkedList.add(2, 2); // 在指定位置添加元素
        linkedList.addLast(3); // 添加元素到列表结尾
        
        System.out.println("LinkedList（直接输出的）: " + linkedList);

        System.out.println("getFirst()获得第一个元素: " + linkedList.getFirst()); // 返回此列表的第一个元素
        System.out.println("getLast()获得第最后一个元素: " + linkedList.getLast()); // 返回此列表的最后一个元素
        System.out.println("removeFirst()删除第一个元素并返回: " + linkedList.removeFirst()); // 移除并返回此列表的第一个元素
        System.out.println("removeLast()删除最后一个元素并返回: " + linkedList.removeLast()); // 移除并返回此列表的最后一个元素
        System.out.println("After remove:" + linkedList);
        System.out.println("contains()方法判断列表是否包含1这个元素:" + linkedList.contains(1)); // 判断此列表包含指定元素，如果是，则返回true
        System.out.println("该linkedList的大小 : " + linkedList.size()); // 返回此列表的元素个数

        /************************** 位置访问操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.set(1, 3); // 将此列表中指定位置的元素替换为指定的元素
        System.out.println("After set(1, 3):" + linkedList);
        System.out.println("get(1)获得指定位置（这里为1）的元素: " + linkedList.get(1)); // 返回此列表中指定位置处的元素

        /************************** Search操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.add(3);
        System.out.println("indexOf(3): " + linkedList.indexOf(3)); // 返回此列表中首次出现的指定元素的索引
        System.out.println("lastIndexOf(3): " + linkedList.lastIndexOf(3));// 返回此列表中最后出现的指定元素的索引

        /************************** Queue操作 ************************/
        System.out.println("-----------------------------------------");
        System.out.println("peek(): " + linkedList.peek()); // 获取但不移除此列表的头
        System.out.println("element(): " + linkedList.element()); // 获取但不移除此列表的头
        linkedList.poll(); // 获取并移除此列表的头
        System.out.println("After poll():" + linkedList);
        linkedList.remove();
        System.out.println("After remove():" + linkedList); // 获取并移除此列表的头
        linkedList.offer(4);
        System.out.println("After offer(4):" + linkedList); // 将指定元素添加到此列表的末尾

        /************************** Deque操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.offerFirst(2); // 在此列表的开头插入指定的元素
        System.out.println("After offerFirst(2):" + linkedList);
        linkedList.offerLast(5); // 在此列表末尾插入指定的元素
        System.out.println("After offerLast(5):" + linkedList);
        System.out.println("peekFirst(): " + linkedList.peekFirst()); // 获取但不移除此列表的第一个元素
        System.out.println("peekLast(): " + linkedList.peekLast()); // 获取但不移除此列表的第一个元素
        linkedList.pollFirst(); // 获取并移除此列表的第一个元素
        System.out.println("After pollFirst():" + linkedList);
        linkedList.pollLast(); // 获取并移除此列表的最后一个元素
        System.out.println("After pollLast():" + linkedList);
        linkedList.push(2); // 将元素推入此列表所表示的堆栈（插入到列表的头）
        System.out.println("After push(2):" + linkedList);
        linkedList.pop(); // 从此列表所表示的堆栈处弹出一个元素（获取并移除列表第一个元素）
        System.out.println("After pop():" + linkedList);
        linkedList.add(3);
        linkedList.removeFirstOccurrence(3); // 从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表）
        System.out.println("After removeFirstOccurrence(3):" + linkedList);
        linkedList.removeLastOccurrence(3); // 从此列表中移除最后一次出现的指定元素（从头部到尾部遍历列表）
        System.out.println("After removeFirstOccurrence(3):" + linkedList);

        /************************** 遍历操作 ************************/
        System.out.println("-----------------------------------------");
        linkedList.clear();
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }
        // 迭代器遍历
        long start = System.currentTimeMillis();
        Iterator<Integer> iterator = linkedList.iterator();
        while (iterator.hasNext()) {
            iterator.next();
        }
        long end = System.currentTimeMillis();
        System.out.println("Iterator：" + (end - start) + " ms");

        // 顺序遍历(随机遍历)
        start = System.currentTimeMillis();
        for (int i = 0; i < linkedList.size(); i++) {
            linkedList.get(i);
        }
        end = System.currentTimeMillis();
        System.out.println("for：" + (end - start) + " ms");

        // 另一种for循环遍历
        start = System.currentTimeMillis();
        for (Integer i : linkedList)
            ;
        end = System.currentTimeMillis();
        System.out.println("for2：" + (end - start) + " ms");

        // 通过pollFirst()或pollLast()来遍历LinkedList
        LinkedList<Integer> temp1 = new LinkedList<>();
        temp1.addAll(linkedList);
        start = System.currentTimeMillis();
        while (temp1.size() != 0) {
            temp1.pollFirst();
        }
        end = System.currentTimeMillis();
        System.out.println("pollFirst()或pollLast()：" + (end - start) + " ms");

        // 通过removeFirst()或removeLast()来遍历LinkedList
        LinkedList<Integer> temp2 = new LinkedList<>();
        temp2.addAll(linkedList);
        start = System.currentTimeMillis();
        while (temp2.size() != 0) {
            temp2.removeFirst();
        }
        end = System.currentTimeMillis();
        System.out.println("removeFirst()或removeLast()：" + (end - start) + " ms");
    }
}

04.LinkedList类声明

先看一下代码

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable

从其实现的几个接口可以看出来
- LinkedList 是支持快速访问，可克隆，可序列化的，而且可以将之看成一个支持有序访问的队列/栈
- 上面说过，LinkedList内部是通过双向链表的数据结构来实现的，对于链表中的结点来说，除了首尾两个结点外，其余每个结点除了存储本结点的数据元素外，还分别有两个指针用于指向其上下两个相邻结点，这个结点类就是 LinkedList 中的静态类 Node。
```
//结点类
private static class Node<E> {

    //当前结点包含的实际元素
    E item;

    //指向下一个结点
    Node<E> next;

    //指向上一个结点
    Node<E> prev;

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

05.几个常用的方法

如下所示

//判断是否包含元素 o
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

//获取元素个数
public int size() {
    return size;
}

//清空链表元素
//这里将各个结点之间的引用都切断了，这并不是必须的，但这样有助于GC回收
public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

//返回第一个元素值为 o 的结点所在的索引值
//如果查找不到，则返回 -1
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

//返回最后一个元素值为 o 的结点所在的索引值
//如果查找不到，则返回 -1
public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

06.list效率比较

LinkedList 相比 ArrayList 添加和移除元素的效率会高些，但随机访问元素的效率要比 ArrayList 低，这里我也来做个测试，看下两者之间的差距

分别向 ArrayList 和 LinkedList 存入同等数据量的数据，然后各自移除 100 个元素以及遍历 10000 个元素，观察两者所用的时间。

public static void main(String[] args) {

        List<String> stringArrayList = new ArrayList<>();
        for (int i = 0; i < 300000; i++) {
            stringArrayList.add("leavesC " + i);
        }
        //开始时间
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            stringArrayList.remove(100 + i);
        }
        //结束时间
        long endTime = System.currentTimeMillis();
        System.out.println("移除 ArrayList 中的100个元素，所用时间：" + (endTime - startTime) + "毫秒");

        //开始时间
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            stringArrayList.get(i);
        }
        //结束时间
        endTime = System.currentTimeMillis();
        System.out.println("遍历 ArrayList 中的10000个元素，所用时间：" + (endTime - startTime) + "毫秒");


        List<String> stringLinkedList = new LinkedList<>();
        for (int i = 0; i < 300000; i++) {
            stringLinkedList.add("leavesC " + i);
        }
        //开始时间
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 100; i++) {
            stringLinkedList.remove(100 + i);
        }
        //结束时间
        endTime = System.currentTimeMillis();
        System.out.println("移除 LinkedList 中的100个元素，所用时间：" + (endTime - startTime) + "毫秒");
        //开始时间
        startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000; i++) {
            stringLinkedList.get(i);
        }
        //结束时间
        endTime = System.currentTimeMillis();
        System.out.println("遍历 LinkedList 中的10000个元素，所用时间：" + (endTime - startTime) + "毫秒");
    }

可以看出来，两者之间的差距还是非常大的，因此，在使用集合时需要根据实际情况来判断到底哪一种数据结构才更加适合。