List

LinkedList

为什么用static class ？

private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

在 stackoverflow上面回答是

A nested class is a member of its enclosing class. Non-static nested classes (inner classes) have access to other members of the enclosing class, even if they are declared private. Static nested classes do not have access to other members of the enclosing class. 嵌套类是其外围类的成员。非静态内部类（内部类）可以访问封装类的其他成员，即使它们被声明为private。静态嵌套类不具有访问封闭类的其他成员。 There is no need for LinkedList.Entry to be top-level class as it is only used by LinkedList (there are some other interfaces that also have static nested classes named Entry, such as Map.Entry - same concept). And since it does not need access to LinkedList’s members, it makes sense for it to be static - it’s a much cleaner approach. 没有必要为LinkedList.Node是顶层类，因为它仅由LinkedList的（也有一些其他接口也有一个名为Node静态嵌套类，如Map.Entry的 - 同一概念）。而且因为它并不需要访问LinkedList的成员，它是有道理的它是静态的 - 这是一个更清洁的方式。

底层实现

LinkedList 与 ArrayList 一样实现 List 接口 ArrayList 是 List 接口大小可变数组的实现 LinkedList是 List 接口链表的实现。 基于链表实现的方式使得 LinkedList 在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 逊色些 可见以下源码发现实现需要进行迭代返回 数组实现的话 不需要进行迭代返回点击查看数组在内存的位置

/** * Returns the element at the specified position in this list. * 返回列表中指定位置的元素 * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) { checkElementIndex(index); return node(index).item; } /** * Returns the (non-null) Node at the specified element index. */ 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; } }

Deque 接口

一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

此接口定义在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。插入操作的后一种形式是专为使用有容量限制的 Deque 实现设计的；在大多数实现中，插入操作不能失败。

次借口扩展可queue接口

Queue 方法等效 Deque 方法作用add(e)addLast(e)在不违反容量限制的情况下， 将指定元素插入此双端队列的末尾offer(e)offerLast(e)在不违反容量限制的情况下，将指定的元素插入此双端队列的末尾。remove()removeFirst()获取并移除此双端队列第一个元素。poll()pollFirst()获取并移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。element()getFirst()获取，但不移除此双端队列的第一个元素。peek()peekFirst()获取，但不移除此双端队列的第一个元素；如果此双端队列为空，则返回 null。 /** * Returns the first element in this list. * * @return the first element in this list * @throws NoSuchElementException if this list is empty */ public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } /** * Returns the last element in this list. * * @return the last element in this list * @throws NoSuchElementException if this list is empty */ public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } /** * Removes and returns the first element from this list. * * @return the first element from this list * @throws NoSuchElementException if this list is empty */ public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * Removes and returns the last element from this list. * * @return the last element from this list * @throws NoSuchElementException if this list is empty */ public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); } /** * Inserts the specified element at the beginning of this list. * * @param e the element to add */ public void addFirst(E e) { linkFirst(e); } /** * Appends the specified element to the end of this list. * * <p>This method is equivalent to {@link #add}. * * @param e the element to add */ public void addLast(E e) { linkLast(e); }

Aarraylist 和 Linkedlist

ArrayList 是实现了基于动态数组的数据结构，LinkedList 基于链表的数据结构。对于随机访问 get 和 set，ArrayList 绝对优于 LinkedList，因为 LinkedList 要迭代获取。对于新增和删除操作 add 和 remove，LinedList 比较占优势，因为 ArrayList 要移动数据。 这一点要看实际情况的。若只对单条数据插入或删除，ArrayList 的速度反而优于 LinkedList。但若是批量随机的插入删除数据，LinkedList 的速度大大优于 ArrayList. 因为 ArrayList 每插入一条数据，要移动插入点及之后的所有数据。

千万级的只有插入

public static void main(String[] args) { List arrayList = new ArrayList(); List linkedList= new LinkedList(); long begin1 = System.currentTimeMillis(); for(int i = 0 ; i < 10000000 ; i++ ){ arrayList.add(1); } long end1 = System.currentTimeMillis(); System.out.println("ArrayList: "+(end1 - begin1)+" ms" ); long begin2 = System.currentTimeMillis(); for(int i = 0 ; i < 10000000 ; i++ ){ linkedList.add(1); } long end2 = System.currentTimeMillis(); System.out.println("LinkedList: "+(end2 -begin2) +" ms" ); } //ArrayList: 313 ms //LinkedList: 14510 ms

千万级的随机插入与删除

public static void main(String[] args) { Random random = new Random(); List arrayList = new ArrayList(); List linkedList= new LinkedList(); long begin1 = System.currentTimeMillis(); for(int i = 0 ; i < 10000000 ; i++ ){ if(random.nextBoolean() == true) { arrayList.add(1); }else{ if(arrayList.size()>1) { arrayList.remove(1); }else{ arrayList.add(1); } } } long end1 = System.currentTimeMillis(); System.out.println("ArrayList: "+(end1 - begin1)+" ms" ); long begin2 = System.currentTimeMillis(); for(int i = 0 ; i < 10000000 ; i++ ){ if(random.nextBoolean() == true) { linkedList.add(1); }else{ if(linkedList.size() > 1) { linkedList.remove(1); }else{ linkedList.add(1); } } } long end2 = System.currentTimeMillis(); System.out.println("LinkedList: "+(end2 -begin2) +" ms" ); } //ArrayList: 6356 ms //LinkedList: 412 ms

千万级的随机set与get

public static void main(String[] args) { Random random = new Random(); List arrayList = new ArrayList(); List linkedList = new LinkedList(); for (int i = 0; i < 10000000; i++) { arrayList.add(1); } for (int i = 0; i < 10000000; i++) { linkedList.add(1); } System.out.println("初始化ArrayList与LinkList成功"); long begin1 = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { if(random.nextBoolean()) { arrayList.set(random.nextInt(10000000), 10); }else { arrayList.get(random.nextInt(10000000)); } } long end1 = System.currentTimeMillis(); System.out.println("ArrayList: " + (end1 - begin1) + " ms"); long begin2 = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { if(random.nextBoolean()) { linkedList.set(random.nextInt(10000000), 10); }else { linkedList.get(random.nextInt(10000000)); } } long end2 = System.currentTimeMillis(); System.out.println("LinkedList: " + (end2 - begin2) + " ms"); } //ArrayList: 702 ms //LinkList :???ms太大了没跑出来 最坏复杂度为O(n^2) n = 10000000