linkedList深入学习

首先介绍一下java集合，集合接口Collection，子接口List，Set，Queue。



LinkedList就是子结构List的一个实现。并且它实现了其他接口，如Deque<E>-double ended queue双向队列，还有Cloneable, java.io.Serializable可克隆和可序列化结构，以及List下的子接口AbstractSequentialList顺序获取结构。

LinkedList的特点，它适用于需要频繁添加删除的集合，因为他的添加删除速度远高于ArrayList，并且顺序遍历的速度也高于ArrayList，但是它不适合随机获取数据。

LinkedList的实现原理，LinkedList顾名思义，就是一个双向列表，每一个节点为Entry，数据推送完全就是链表的操作，所以他的插入，删除的速度快，但是用index查找就费劲了


LinkedList的关键源码分析：

Java代码  收藏代码

    private transient Entry<E> header = new Entry<E>(null, null, null); 

这个成员变量是LinkedList的关键，它在链表中没有实际数据意义，是链表的标示（要是难理解，就通俗一点理解成链表第一个无意义的元素），而且transient修饰，标示着他不会被序列化。header也可以当做队列末尾的元素，因为是双向列表，所以header.next末尾元素后边的元素就成了队首元素了，知道了这些，看一下下边的添加方法


Java代码  收藏代码

    public void addFirst(E e) { 
    addBefore(e, header.next); 
       } 
     
    public void addLast(E e) { 
    addBefore(e, header); 
       } 

以上是两个添加的函数，以这两个函数，讲解一下LinkedList是如何向集合推送元素的

addFirst向队列头加元素，是将元素加到header.next-队首元素之前；

addLast向队列未加元素，是将元素加到header之前；



下面看一下addBefore(E e,Entry<E> entry)函数


Java代码  收藏代码

    private Entry<E> addBefore(E e, Entry<E> entry) { 
        Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); //初始化当前链表节点 
        newEntry.previous.next = newEntry;//改变当前节点前后的链表节点连接状态 
        newEntry.next.previous = newEntry; 
        size++; 
        modCount++; 
        return newEntry; 
        } 

Entry的数据结构是：


Java代码  收藏代码

    private static class Entry<E> { 
    E element; // 当前元素 
    Entry<E> next; // 之后的元素，靠近last 
    Entry<E> previous; // 之前的元素，靠近first 
     
    Entry(E element, Entry<E> next, Entry<E> previous) { 
        this.element = element; 
        this.next = next; 
        this.previous = previous; 
    } 
       } 

明白LinkedList的数据结构和推送方式，那么其他的操作原理也就迎刃而解，讲解也就到这里，其他的代码留给有心人，愿大家技术和综合素质都共同进步