LinkedList特性

LinkedList没什么好说的，在存放大量数据时尤其有用，其插入花费的操作次数仅仅为1，而对比arraylist的插入，花费的操作次数通过aggregate method算出为2，快两倍。

Java中的LinkedList

双向链表，因为内部维护的Node就是双向，而开头写的tail加head更是直接提醒

缺陷在哪

双向链表的一个重要性质就是如果传入的是链表中element的指针，那么删除的复杂度则为O(1)，但可惜的是java的remove(object)是通过遍历，然后判断equals进行删除，所以复杂度为O(n)，翻看完oracle文档里的说明，并没发现合适的方法可以达到O(1)，全部都是遍历，并没有Node指针的接口。最典型的remove:

 public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

其实现过程也是相当简单，当然，这里的unlink符合O(1)的要求，但也仅仅只是用来删除节点而已。而外部暴露的接口并没有O(1)复杂度的接口

需不需要自己实现一个O(1)

不需要，linkedhashmap就是弥补这个的