LinkedList

LinkedList

LinkedList源码解析转载自：https://www.cnblogs.com/CherishFX/p/4734490.html

线性表介绍转载自：https://www.jianshu.com/p/02f8696bf4cf

总结：LinkedList是基于双向链表实现的。其中的元素不存在下标索引，因此不适合于查找，但适合于添加(add)和删除(remove)。LinkedList进行插入和删除时，只需修改相邻元素的next和previous的引用即可，即重新指向next和previous的引用。

数据结构：prev | data | next 。（LinkedList内部类Node中指定了这三个属性）
集合中每个元素处存储了当前元素值，当前元素前一个元素的指针，当前元素后一个元素的指针。

Question1：LinkList如果需要根据下标(index)进行查询，底层是如何进行的?
Question2：LinkedList具体是如何实现随机访问的？即，具体是如何定义index这个参数的？
注：以下的两个问题均为一个意思，只是进行不同的论述。
在源码中，Node<E> node(int index)方法是得到索引index所指向的Node节点的。具体实现为：

 //返回指定索引位置的节点
    Node<E> node(int index) {
        // assert isElementIndex(index);
        //折半思想，当index < size/2时，从列表首节点向后查找
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {  //当index >= size/2时，从列表尾节点向前查找
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

        该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。 源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果 index>size/2，就只从位置size往前遍历到位置index处。因此，LinkedList不适合根据指定索引值进行查找。

ArrayList和LinkedList的区别:
1：ArrayList是实现了基于动态数组的数据结构，LinkedList基于双向链表的数据结构。 
2：对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针去遍历查找。 
3：对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据，调用System.arrayCopy( )，比较消耗资源。

java如何实现双端队列或者说如何区别双端队列和单端队列?
双端队列：队列的一端能分别当头部和尾部使用。
单端队列：队列的一端只能当头部或尾部使用。
java在实现单端队列的时候，只提供add元素的时，只能add到元素的尾部，取出元素的时，只能从元素的头部取出。实现双端队列的时候，多提供几个方法，addFirst是加到队列的头部，addLast是加到队列的尾部。removeFirst是删除队首，removeLast是删除队尾。这种实现就区分了双端队列和单端队列。