LinkedList-双向链表_linkedlist双向链表

LinkedList-双向链表

^{《Hash Map源码基于jdk_8》}

1. 类的继承关系

双向链表实现了List和Deque(双向队列)接口

2. 变量及其含义

3.构造函数

分为无参构造和有参构造，无参构造啥也不做。有参构造以Collection为参数，并初始化。

    List<String> noArgslinkedList = new LinkedList<>();
    noArgslinkedList.add("2");
    noArgslinkedList.forEach(System.out::println);

    System.out.println("=================================");

    List<String> arrayList = new ArrayList<>();
    arrayList.add("1");
    arrayList.add("2");
    arrayList.add("2");
    arrayList.add("3");
    List<String> ArgslinkedList = new LinkedList<>(arrayList);
    ArgslinkedList.forEach(System.out::println);
1
2
3
4
5
6
7
8
9
10
11
12
13

4.LinkedList的结构

5.增

LinkedList增加元素的方式有三种：链表头部插入值、尾部插入值、中间某个元素前插入值。这三种方式囊括了LinkedList添加元素的所有方式。

5.1 linkFirst

链表头部插入元素

    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11

新元素插入过程图示：

情况一：链表中本身有元素
①

②

情况二：链表为空链表

5.2 linkLast

和linkFirst差不多，不做演示了。

5.3 linkBefore

链表某元素前插入元素

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
1
2
3
4
5
6
7
8
9
10
11
12

步骤：
①创建一个item为插入元素值的Node

②newNode.prev = 上一个节点 && newNode.next = 下一个节点

③上一个节点.next = newNode && 下一个节点.prev = newNode

6.删

删除元素是添加元素的逆过程，逆向思维就好了。

7.遍历

下面列举了四种LinkedList遍历的方式，分别是：快速随机访问（for循环）、增强for循环、迭代器、stream流遍历。
通过对7w个元素进行遍历，发现快速随机访问方式最慢，迭代器方式最快。访问时间见下图：
遍历代码见最下方附录。

遍历时间分析
①快速随机访问最慢，慢就慢在get方法，链表查找元素时，会首先判断该元素是在链表的前半部分还是后半部分，之后再循环查找元素(代码见下方)。时间复杂度为O(n²)

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
1
2
3
4

    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

②增强for循环和迭代器的区别与联系
增强for循环实际上调用了迭代器，这是它和迭代器效率差不多的原因，经反编译class文件后，增强for循环的代码如下（多了一个赋值过程）：

③Stream和迭代器的区别
Stream 可以并行化操作，迭代器只能命令式地、串行化操作。也就是当使用串行方式去遍历时，每个 item 读完后再读下一个 item。而使用并行去遍历时，数据会被分成多个段，其中每一个都在不同的线程中处理，然后将结果一起输出。
当数据量不大或者没有太耗时的操作时，顺序执行（如iterator）往往比并行执行更快。当任务涉及到耗时操作（如I/O）并且任务之间不互相依赖时，那么并行化就是一个不错的选择。通常而言，将这类程序并行化之后，执行速度会提升好几个等级

附录

  public static void main(String[] args) {
        LinkedList<Integer> list = getLinkedList();
        //通过快速随机访问遍历LinkedList
        listByNormalFor(list);
        System.out.println("=======================================");
        //通过增强for循环遍历LinkedList
        listByStrengThenFor(list);
        System.out.println("=======================================");
        //通过快迭代器遍历LinkedList
        listByIterator(list);
        System.out.println("=======================================");
        //通过stream遍历LinkedList
        listByStream(list);
    }

    /**
     * 构建一个LinkedList集合,包含元素50000个
     * @return
     */
    private static LinkedList<Integer> getLinkedList() {
        LinkedList list = new LinkedList();
        for (int i = 0; i < 70000; i++){
            list.add(i);
        }
        return list;
    }

    /**
     * 通过快速随机访问遍历LinkedList
     */
    private static void listByNormalFor(LinkedList<Integer> list) {
        // 记录开始时间
        long start = System.currentTimeMillis();
        int size = list.size();
        for (int i = 0; i < size; i++) {
            System.out.print(list.get(i));
        }
        // 记录用时
        long interval = System.currentTimeMillis() - start;
        System.out.println();
        System.out.println("listByNormalFor：" + interval + " ms");
    }

    /**
     * 通过增强for循环遍历LinkedList
     * @param list
     */
    public static void listByStrengThenFor(LinkedList<Integer> list){
        // 记录开始时间
        long start = System.currentTimeMillis();
        for (Integer i : list) {
            System.out.print(i);
        }
        // 记录用时
        long interval = System.currentTimeMillis() - start;
        System.out.println();
        System.out.println("listByStrengThenFor：" + interval + " ms");
    }

    /**
     * 通过快迭代器遍历LinkedList
     */
    private static void listByIterator(LinkedList<Integer> list) {
        // 记录开始时间
        long start = System.currentTimeMillis();
        for(Iterator iter = list.iterator(); iter.hasNext();) {
            System.out.print(iter.next());
        }
        // 记录用时
        long interval = System.currentTimeMillis() - start;
        System.out.println();
        System.out.println("listByIterator：" + interval + " ms");
    }

    /**
     * 通过stream foreach遍历LinkedList
     */
    private static void listByStream(LinkedList<Integer> list) {
        // 记录开始时间
        long start = System.currentTimeMillis();
        list.stream().forEach(ele -> System.out.print(ele));
        // 记录用时
        long interval = System.currentTimeMillis() - start;
        System.out.println();
        System.out.println("listByStream：" + interval + " ms");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

LinkedList中Deque相关的一些方法

  public static void main(String[] args) {
        LinkedList<String> list = getLinkedList();
        //《offer》向List末尾添加元素
        System.out.println(list.offer("999 "));
        list.forEach(System.out::print);
        System.out.println();
        //《peek》查询队列头部的元素
        System.out.println(list.peek());
        list.forEach(System.out::print);
        System.out.println();
        //《poll》移除队列头部元素
        System.out.println(list.poll());
        list.forEach(System.out::print);
        System.out.println();
        //《pop》移除队列头部元素
        System.out.println(list.pop());
        list.forEach(System.out::print);
        System.out.println();
        //《remove》移除队列头部元素
        System.out.println(list.remove());
        list.forEach(System.out::print);
        System.out.println();

    }
    
    private static LinkedList<String> getLinkedList() {
        LinkedList list = new LinkedList();
        for (int i = 0; i < 5; i++){
            list.add(i+" ");
        }
        return list;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32