LinkedList类是双向列表,列表中的每个节点都包含了对前一个和后一个元素的引用，是线程不安全的，是允许元素为null的双向链表
IDEA 类图
源码分析
1.变量
/** * 集合元素数量 **/ transient int size = 0; /** * 指向第一个节点的指针 * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node<E> first; /** * 指向最后一个节点的指针 * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node<E> last;
2.构造方法
/** * 无参构造方法 */ public LinkedList() { } /** * 将集合c所有元素插入链表中 */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
3.节点
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; } }
这个类代表双端链表的节点Node，有三个变量，前驱节点，当前节点，后继结点
4.添加元素方法-
add(E e) 尾部添加元素
public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; // 前驱为前last，值为e，后继为null final Node<E> newNode = new Node<>(l, e, null); last = newNode; //最后一个节点为空，说明列表中无元素 if (l == null) //first同样指向此节点 first = newNode; else //否则，前last的后继指向当前节点 l.next = newNode; size++; modCount++; }
add(int index, E element)方法，指定索引处添加元素
public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }
addAll(int index, Collection c)： 将集合从指定位置开始插入
public boolean addAll(int index, Collection<? extends E> c) { //1:检查index范围是否在size之内 checkPositionIndex(index); //2:toArray()方法把集合的数据存到对象数组中 Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //3：得到插入位置的前驱节点和后继节点 Node<E> pred, succ; //如果插入位置为尾部，前驱节点为last，后继节点为null if (index == size) { succ = null; pred = last; } //否则，调用node()方法得到后继节点，再得到前驱节点 else { succ = node(index); pred = succ.prev; } // 4：遍历数据将数据插入 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //创建新节点 Node<E> newNode = new Node<>(pred, e, null); //如果插入位置在链表头部 if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; } //如果插入位置在尾部，重置last节点 if (succ == null) { last = pred; } //否则，将插入的链表与先前链表连接起来 else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
可以看出addAll方法通常包括下面四个步骤：
1.检查index范围是否在size之内
toArray()方法把集合的数据存到对象数组中
得到插入位置的前驱和后继节点
遍历数据，将数据插入到指定位置
方法linkBefore，在succ节点前增加元素e(succ不能为空)
/** * 在succ节点前增加元素e(succ不能为空) */ void linkBefore(E e, Node<E> succ) { // assert succ != null; // 拿到succ的前驱 final Node<E> pred = succ.prev; // 新new节点：前驱为pred，值为e，后继为succ final Node<E> newNode = new Node<>(pred, e, succ); // 将succ的前驱指向当前节点 succ.prev = newNode; // pred为空，说明此时succ为首节点 if (pred == null) // 指向当前节点 first = newNode; else // 否则，将succ之前的前驱的后继指向当前节点 pred.next = newNode; size++; modCount++; }
5.获取元素方法
get(int index) ，获取指定索引下的元素
public E get(int index) { checkElementIndex(index); return node(index).item; } // 检测index合法性 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 根据index 获取元素 Node<E> node(int index) { // assert isElementIndex(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; } }
6.根据Object对象删除元素。
remove(Object o)
小结
LinkedList是一个实现了List接口和Deque接口的双端链表。 LinkedList底层的链表结构使它支持高效的插入和删除操作，另外它实现了Deque接口，使得LinkedList类也具有队列的特性; LinkedList不是线程安全的，如果想使LinkedList变成线程安全的，可以调用静态类Collections类中的synchronizedList方法：
LinkedList和ArrayList的区别
LinkedList
优点：
不需要扩容和预留空间,空间效率高
增删效率高
缺点：
随机访问时间效率低
改查效率低
ArrayList
优点：
底层是数组，查找和修改效率高
缺点：
增删效率低
