LinkedList浅析

傷城~ 2022-05-14 20:38 383阅读 0赞

--------------------

##### LinkedList是Collection下的一个list实现，就像ArrayList一样。 #####

*和ArrayList不同的是它是链表结构，而ArrayList是顺序结构。我们平常使用的list是一样的，理论上来说一种list就可以完成我们所有的需求。但是它们在运行过程中有区别的，完成需求所需要的资源也不相同，至于什么情况下使用哪种list就看需求和当前情况了。*

--------------------

视频：

LinkedList 是一个继承于AbstractSequentialList的**双向链表**。  
LinkedList 可以被当作**堆栈、队列或双端队列**进行操作。  
LinkedList 实现 List 接口，所以能对它进行**队列操作**。  
LinkedList 实现 Deque 接口，能将LinkedList当作**双端队列**使用。  
LinkedList 实现了Cloneable接口，即覆盖了函数**clone()**，能克隆。  
LinkedList 实现java.io.Serializable接口，所以LinkedList**支持序列化**，能通过序列化去传输。  
LinkedList 是非同步的。

![java集合][java]

**构造函数**

// 默认构造函数
    LinkedList()
    
    // 创建一个LinkedList，保护Collection中的全部元素。
    LinkedList(Collection<? extends E> collection)

**LinkedList的本质是双向链表**

1.  LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
2.  LinkedList包含两个重要的成员：header 和 size。  
    　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。  
    　　size是双向链表中节点的个数。

\#\#双向链表结构

*  链表：链表是一种重要的数据结构，有单链表和双链表之分

单链表：

> 单链表（单向链表）：由两部分组成 数据域（Data）和结点域(Node),单链表就像是一条打了很多结的绳子，每一个绳结相当于一个结点，每个节结点间都有绳子连接，这样原理的实现是通过Node结点区的头指针head实现的，每个结点都有一个指针，每个节点指针的指向都是指向自身结点的下一个结点，最后一个结点的head指向为null,这样一来就连成了上述所说绳子一样的链，对单链表的操作只能从一端开始，如果需要查找链表中的某一个结点，则需要从头开始进行遍历。

双向链表结构

> 双链表（双向链表）：双链表和单链表相比，多了一个指向尾指针（tail），双链表的每个结点都有一个头指针head和尾指针tail,双链表相比单链表更容易操作，双链表结点的首结点的head指向为null，tail指向下一个节点的tail;尾结点的head指向前一个结点的head，tail 指向为null，是双向的关系；  
> 在单链表中若需要查找某一个元素时，都必须从第一个元素开始进行查找，而双向链表除开头节点和最后一个节点外每个节点中储存有两个指针，这连个指针分别指向前一个节点的地址和后一个节点的地址，这样无论通过那个节点都能够寻找到其他的节点。

*  插入删除不需要移动元素外，可以原地插入删除
 *  可以在结构的前后插入数据
 *  可以双向遍历

\#\#\#[链表][Link 1]

--------------------

## AbstractSequentialList ##

Linklist是AbstractSequentialList的子类

> AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数。这些接口都是随机访问List的，LinkedList是双向链表；既然它继承于AbstractSequentialList，就相当于已经实现了“get(int index)这些接口”。  
> 此外，我们若需要通过AbstractSequentialList自己实现一个列表，只需要扩展此类，并提供 listIterator() 和 size() 方法的实现即可。若要实现不可修改的列表，则需要实现列表迭代器的 hasNext、next、hasPrevious、previous 和 index 方法即可。

LinkedList的继承关系：

java.lang.Object
       ↳ java.util.AbstractCollection<E>
             ↳ java.util.AbstractList<E>
                   ↳ java.util.AbstractSequentialList<E>
                         ↳  java.util.LinkedList<E>
    
        public class LinkedList<E>
             extends AbstractSequentialList<E>
                implements List<E>, Deque<E>, Cloneable, java.io.Serializable { …… }

**LinkedList与Collection关系**

*Collection:*

> Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

![o_linkedlist.jpg][]

--------------------

**LinkedList的本质是双链表，实现 List 和 Deque接口:**

![o_QQ_e6_88_aa_e5_9b_be20180828105623.png][]

在LinkedList中，每个节点都用内部类Node表示：

![o_QQ_e6_88_aa_e5_9b_be20180828105310.png][]

具体的过程可以看下面这张图：  
[点我][Link 2]

每个node都是节点，里面有三个属性，分别指向上一个节点、下一个节点、实际储存元素开辟的内存空间

而对linkedlist里元素的操作方法都是对这些节点进行操作：

**add()操作:**

/**
         * Appends the specified element to the end of this list.
         *
         * <p>This method is equivalent to {@link #addLast}.
         *
         * @param e element to be appended to this list
         * @return {@code true} (as specified by {@link Collection#add})
         */
        public boolean add(E e) {
            linkLast(e);
            return true;
        }
    
      /**
         * Links e as last element.
         */
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }

**remove()操作**

/**
         * Removes the element at the specified position in this list.  Shifts any
         * subsequent elements to the left (subtracts one from their indices).
         * Returns the element that was removed from the list.
         *
         * @param index the index of the element to be removed
         * @return the element previously at the specified position
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
    
    	//查找对应索引
        private void checkElementIndex(int index) {
            if (!isElementIndex(index))
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
    
        /**
         * Unlinks non-null node x.
         */
        E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
        }

可以看到都是对node节点进行操作，真实的实例内存并没有任何改变，等着jvm回收。

--------------------

**List使用场景**

> ArrayList在随机访问方面比较擅长，LinkedList在随机增删方面比较擅长  
> 对于需要快速插入，删除元素，使用LinkedList。因为ArrayList要想在数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。  
> 对于需要快速随机访问元素（get()），应该使用ArrayList，因为LinkedList要移动指针、遍历节点来定位，所以速度慢。  
> 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。  
> 对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。

对于插入数据使用时间的对比：

public static void addTest(){
    
            //批量插入，每次都向首位插入数据；
    
            LinkedList linkedList = new LinkedList();
    
            long time1 = new Date().getTime();
    
            for(int m=0;m<300000;m++){
                linkedList.add(0,null);
            }
    
            long time2 = new Date().getTime();
    
            System.out.print("linkedList批量插入时间:"+(time2 - time1)+"ms\n");
    
    
    
    
            ArrayList arraylist = new ArrayList();
    
            long time3 = new Date().getTime();
    
            for(int n=0;n<300000;n++){
                arraylist.add(0, null);
            }
    
            long time4 = new Date().getTime();
            System.out.print("arrayList批量插入时间:"+(time4 - time3)+"ms\n");
    
        }

结果：  
  
linkedList批量插入时间:9ms  
arrayList批量插入时间:3696ms

--------------------

那么问题就来了：

**Q：什么时候使用Arraylist，什么时候使用LinkedList？**  
A：当你需要频繁查询数组的时候使用ArrayList比较快，当你需要频繁操作数组进行增删插入操作的时候使用LinkList比较合适。当然直接在末尾添加数据ArrayList用时也不是特别多，因为在末尾操作后面没有数据。

**Q：那什么时候适合用list呢**  
A：涉及到“栈”、“队列”、“链表”等操作，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍

*  对于需要快速插入，删除元素，应该使用LinkedList。
 *  对于需要快速随机访问元素，应该使用ArrayList。
 *  对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
 *  对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。

**Q：线程安全的数组，什么是线程安全？**  
A：线程安全就是当前资源只能被单独一个线程访问，也就是加同步锁的线程。默认的线程安全的list是Vector；

--------------------

**以上，如果有哪里不对或者不清楚的地方欢迎勾搭，多谢指正**

[java]: /images/20220515/0136ac108fc046dc9ce6937ea7337a73.png
[Link 1]: https://www.processon.com/view/link/5b83c4dbe4b0fe81b618a9ef
[o_linkedlist.jpg]: /images/20220515/337d4d1d328f4ba4a420dd20e0eb64dd.png
[o_QQ_e6_88_aa_e5_9b_be20180828105623.png]: /images/20220515/00b515e2e3544ab2a400efb5336e5a11.png
[o_QQ_e6_88_aa_e5_9b_be20180828105310.png]: /images/20220515/34699a5df6bb4d70a96de3a9f726c907.png
[Link 2]: https://www.processon.com/view/link/5b83f844e4b06fc64ad76fd9