1 继承结构图
LinkedList是List的另一种实现。继承自AbstractSequentialList
2 数据结构
LinkedList与ArrayList不同的是LinkedList底层使用双向链表进行存储,其主要数据结构如下
// 记录List长度 transient int size = 0; // 指向LinkedList第一个节点 transient Node<E> first; // 指向LinkedList最后一个节点 transient Node<E> last; // Node 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; } }
LinkedList的一个节点是一个Node对象,可以看到node.item记录值,并且分别有指向前一个节点和后一个节点的指针prev和next
3 构造方法
public LinkedList() {} public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
LinkedList也支持两种构造方式,无参构造和传入一个集合构造LinkedList,addAll的具体实现如下
public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } 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; } if (succ == null) { last = pred; } else { pred.next = succ; succ.prev = pred; } size += numNew; modCount++; return true; }
初始化是size=0,可见就是利用Collection的toArray方法把c转为对象数组,然后遍历新建Node,并逐个连起来,基本的链表操作。
4 一些方法介绍
void linkBefore(E e, Node<E> succ) { // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
linkBefore方法是在succ节点之前插入一个新的节点,其执行过程大致如下图
其他方法类似也都可以通过画图的形式了解大致执行步骤,涉及链表操作,画图能更好的理解执行过程,在此不再赘述。
5 与ArrayList的异同
ArrayList和LinkedList是List的两种实现,不同的ArrayList是基于动态数组的数据结构,而LinkedList是基于双向链表的数据结构。
他们的优缺点也正是由于他们所依赖的数据结构决定的
- 对于随机存取,因为ArrayList是基于数组实现的,所以随机存取的时间复杂度为O(1),直接根据数据下标即可get或set,而LinkedList由于是使用双向链表实现,随机存取需要移动指针,时间复杂度为O(n);
- 但是对于元素的删除和增加,如果不是在List尾部操作,ArrayList中元素的删除会涉及数组元素的移动,所以复杂度O(n)会比只单纯操作几个指针的复杂度O(1)要高。
所以在日常使用中,需要根据应用场景灵活选择,对于不需要随机存取而是只进行平凡的增加和删除的场景,使用LinkedList是较好的选择。
本文来自我的个人博客:http://blog.duchangchun.com/2018/12/29/jdk_linkedlist/