Java中LinkedList容器如何使用(java,linkedlist,开发技术)

public class LinkedList<E> extends AbstractSequentialList <E> implements List<E>, Deque<E>

LinkedList具备AbstractSequentialList的特点：AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问

LinkedList具备List的特点

LinkedList具备Deque的特点：Deque是一个线性collection，支持在两端插入和移除元素

LinkedList特点

1.LinkedList是通过双链表去实现的。

2.LinkedList不存在容量不足的问题，因为是链表。

3.LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法，所以LinkedList可以作为FIFO（先进先出）的队列；LinkedList可以作为LIFO（后进先出）的栈

新增元素add()方法默认是尾部追加，核心就是将新建的Node节点追加到当前last节点的next指针上 ，伪代码：

addFirst：首部追加

首部追加的逻辑与尾部追加基本相同，伪代码：

指定位置添加元素：add(int index, E element)：

LinkedList是一个双向链表，他只记录了头部和尾部位置，如果我们要指定位置插入，他会这么做：

1.先遍历查找出要插入的元素位置，然后再插入；查找方式是根据 index < (size >> 1)判断结果，决定是从头遍历，还是从尾部遍历，这种遍历方式类似于二分查找(只在第一层循环二分)

2.新建一个Node节点，插入到查找出来的元素的前面

由此可知为何链表对随机位置读写是不合适的；他的时间复杂度=O(n/2) ，如果n很大，我们一般就认为他的时间复杂度=O(n)

这里我们看到LinkedList重写了List的remove方法，整个删除逻辑也是先查找再删除，时间复杂度O(n)，如果是删除首部元素时间复杂度=O(1)，若要删除尾部元素请使用removeLast( )

LinkedLis删除首部元素：removeFirst()

LinkedLis删除尾部元素：removeLast()

LinkedLis首部出队：pollFirst( ) ，队列的特点

LinkedLit尾部出队：pollLast( )，队列的特点

Iterator迭代器只能是从头往尾迭代，而LinkedList是双向链表，他还可以从尾往头部迭代，JAVA提供了一个新的迭代器接口：

LinkedList实现该接口：

LinkedList从前往后遍历：

LinkedList从后往前遍历：

迭代器删除元素：