5. LinkedList

底层数据结构是链表，查询慢，增删快；线程不安全，效率高

由于LinkedList：每一个元素在内存中的地址不连续，需要让上一个元素记住下一个元素。

所以每个元素中保存的有下一个元素的位置。虽然也有角标，但是查找的时候，需要从头往下找，显然是没有数组查找快的。

但是，链表在插入新元素的时候，只需要让前一个元素记住新元素，让新元素记住下一个元素就可以了，所以插入很快。

由于链表实现， 增加时只要让前一个元素记住自己就可以， 删除时让前一个元素记住后一个元素， 后一个元素记住前一个元素。

这样的增删效率较高，但查询时需要一个一个的遍历， 所以效率较低。

我们用一个图来解释：

每一个方框都有他自己的内存地址，同时还记录着它下一个数据的内存地址，这样就可以从第一个元素一直找到任何链表上的元素。

LinkedList类特有功能

public void addFirst(E e)及addLast(E e)

public E getFirst()及getLast()

public E removeFirst()及public E removeLast()

这些方法是跟Queue（队列）有关的，具体内容可移步：