LinkedList
LinkendList是一个双向链表 , 并且实现了Deque接口 , 可以作为一个队列来使用 , 虽然LinkendList是线性结构 , 但是数据的存储并不是按照线性的接口来存储的 , 而是在每一个节点里存数据及下一个节点的地址, 同时实现了Cloneable接口 , 支持拷贝 , 并且实现了java.io.Serializable支持序列化和反序列化
Cloneable , Serializable接口直通车 : java框架集合List子接口之ArrayList源码剖析
数据结构直通车 : 数据结构之顺序存储结构和链式存储结构分析 , 图文并茂 , 又涨姿势了
队列直通车 : 线性数据结构之队列(Queue)
Deque
Deque是double ended queue的简称，支持两端的元素插入和移除 ,习惯上称之为双端队列。大多数Deque 实现对它们可能包含的元素的数量没有固定的限制，但是该接口支持容量限制的deques以及没有固定大小限制的deque
Deque同时扩展了Queue接口，当Deque作为队列的时候，会产生FIFO(先进先出)行为。元素添加在双端队列的末尾并从头开始删除。
双端队列的功能就是既可以从队首添加 , 也可以从队尾添加 , 既可以从队尾获取 , 也可以从队首获取
Deque和Queue方法对比
Deque
Queue
添加元素到队尾 add(E e) / offer(E e)
addLast(E e)
offerLast(E e)
取队首元素并删除
E remove()
E poll()
E removeFirst()
E pollFirst()
取队首元素但不删除
E element()
E peek()
E getFirst()
E peekFirst()
添加元素到队首 无
addFirst(E e)
offerFirst(E e)
取队尾元素并删除 无
E removeLast()
E pollLast()
取队尾元素但不删除 无
E getLast()
E peekLast()
可以看出LinkendList又是一个集合 , 又是一个队列 , 又是一个栈 , 功能还是比较强大的 , 但是我们在使用的时候，总是用特定的接口来引用它，这是因为持有接口说明代码的抽象层次更高，而且接口本身定义的方法代表了特定的用途。
// 不推荐的写法: LinkedList<String> d1 = new LinkedList<>(); d1.offerLast("z"); // 推荐的写法： Deque<String> d2 = new LinkedList<>(); d2.offerLast("z");
可见面向抽象编程的一个原则就是：尽量持有接口，而不是具体的实现类。
LinkendList构造方法
构造函数 描述
LinkedList() 此构造函数构建一个空链表。
LinkedList(Collection c) 此构造函数构建一个链表，它使用集合c的元素进行初始化。
// 当前列表的节点个数 transient int size = 0; // 第一个节点 transient Node<E> first; // 最后一个节点 transient Node<E> last; /** * Constructs an empty list. */ public LinkedList() { } /** * Constructs a list containing the elements of the specified * collection, in the order they are returned by the collection's * iterator. * * @param c the collection whose elements are to be placed into this list * @throws NullPointerException if the specified collection is null */ public LinkedList(Collection<? extends E> c) { this(); addAll(c); }
LinkendList常用方法
方法 描述
void add(int index,Object element) 将指定元素插入此列表中的指定位置索引。如果指定的索引超出范围(index<0 或 index> size())，则抛出IndexOutOfBoundsException异常。
boolean add(Object o)` 将指定的元素追加到此列表的末尾。
boolean addAll(Collection c) 将指定集合中的所有元素按指定集合的迭代器返回的顺序附加到此列表的末尾。如果指定的集合为null，则抛出NullPointerException异常。
boolean addAll(int index, Collection c) 从指定位置开始，将指定集合中的所有元素插入此列表。如果指定的集合为null，则抛出NullPointerException异常。
void addFirst(Object o) 在此列表的开头插入给定元素。
void addLast(Object o) 将给定元素追加到此列表的末尾。
void clear() 从此列表中删除所有元素。
Object clone() 返回此LinkedList的浅表副本。
boolean contains(Object o) 如果此列表包含指定的元素，则返回true。当且仅当此列表包含至少一个元素e时才返回true，即，(o == null？e == null：o.equals(e))。
Object get(int index) 返回此列表中指定位置的元素。如果指定的索引超出范围(index < 0 或 index> = size())，则抛出IndexOutOfBoundsException异常。
Object getFirst() 返回此列表中的第一个元素。如果此列表为空，则抛出NoSuchElementException异常。
Object getLast() 返回此列表中的最后一个元素。如果此列表为空，则抛出NoSuchElementException异常。
int indexOf(Object o) 返回指定元素第一次出现的列表中的索引，如果列表不包含此元素，则返回-1。
int lastIndexOf(Object o) 返回指定元素最后一次出现的列表中的索引，如果列表不包含此元素，则返回-1。
public ListIterator<E> listIterator(int index) 从列表中的指定位置开始，返回此列表中元素的列表迭代器(按正确顺序)。如果指定的索引超出范围(index < 0 或 index> = size())，则抛出IndexOutOfBoundsException异常。
Object remove(int index) 删除此列表中指定位置的元素。如果此列表为空，则抛出NoSuchElementException异常。
boolean remove(Object o) 删除此列表中第一次出现的指定元素。如果此列表为空，则抛出NoSuchElementException异常。如果指定的索引超出范围(index < 0 或 index >= size())，则抛出IndexOutOfBoundsException异常。
Object removeFirst() 从此列表中删除并返回第一个元素。如果此列表为空，则抛出NoSuchElementException异常。
Object removeLast() 从此列表中删除并返回最后一个元素。如果此列表为空，则抛出NoSuchElementException异常。
Object set(int index, Object element) 用指定的元素替换此列表中指定位置的元素。如果指定的索引超出范围(index < 0 或 index >= size())，则抛出IndexOutOfBoundsException异常。
int size() 返回此列表中的元素数量。
Object[] toArray() 以正确的顺序返回包含此列表中所有元素的数组。如果指定的数组为null，则抛出NullPointerException异常。
Object[] toArray(Object[] a) 以正确的顺序返回包含此列表中所有元素的数组; 返回数组的运行时类型是指定数组的运行时类型。
addAll()
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 { // 找到index所在的节点 succ = node(index); // index所在位置的前一个节点 pred = succ.prev; } // 遍历需要添加的集合，逐个插入 for (Object o : a) { // 创建一个新的节点，以 pred 为前一个节点，值为 e，null 为后一个节点 @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, null); // 如果 pred 为空，说明是在头部插入 if (pred == null) // 也就是说新建的节点是第一个节点 first = newNode; else // pred 不为空，说明是在中间或者尾部插入 // pred 的下一个节点连接上新创建的节点 pred.next = newNode; // 依次插入 pred = newNode; } // 如果 succ 为空，说明是在尾部插入 if (succ == null) { // 所以最后插入的元素就是最后一个元素 last = pred; } else { // succ 不为空，说明是在中间插入 // 最后插入的元素连接上后面的一段 pred.next = succ; // 后面的一段第一个元素连接上前面的一段 succ.prev = pred; } // 数量合并 size += numNew; // 修改次数+1 modCount++; return true; }
检查数组下标越界方法
private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private boolean isPositionIndex(int index) { return index >= 0 && index <= size;
看到了很熟悉的异常 IndexOutOfBoundsException，就是根据链表大小检查一下
时间复杂度
addAll()属于一种浅拷贝的方式 , 通过for循环来把一个集合的元素遍历添加到另一个几集合 , 所以时间复杂度是O(N)
add() public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { // 检查 index 是否越界，上面分析过了 checkPositionIndex(index); // 插入位置与当前数量相同，说明是尾部插入 if (index == size) linkLast(element); else linkBefore(element, node(index)); } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); }
可以看到 , 主要调用了linkBefore() linkFirst() linkLast() 这几个方法 , 所以我们接下来分析这几个方法
// 在某个节点前插入一个元素 void linkBefore(E e, Node<E> succ) { // assert succ != null; // 获取到 succ 的上一个节点 final Node<E> pred = succ.prev; // 创建一个新的节点，连接到 succ 上一个节点后面 final Node<E> newNode = new Node<>(pred, e, succ); // 将 succ 连接到 newNode 后面 succ.prev = newNode; // 如果 succ 的上一个节点为空，说明 succ 为头部节点 if (pred == null) // 直接将 newNode 设为头部节点 first = newNode; else // 如果 succ 的上一个节点不为空，说明 succ 为中间或者尾部节点 // 将 succ 的上一个节点关联到 newNode 上 pred.next = newNode; size++; modCount++; }
linkFirst()和linkLast()逻辑相似 , 所以就分析linkFirst
// 插入一个元素到头节点 private void linkFirst(E e) { final Node<E> f = first; // 当前第一个节点 // 创建了一个新节点，以 null 为前一个节点、e 为值、当前第一个节点为下一个节点 final Node<E> newNode = new Node<>(null, e, f); first = newNode; // 设置新建的节点为第一个节点 if (f == null) // 当前第一个节点为空，说明列表为空 last = newNode; // 所以最后一个节点为当前插入的节点 else // 当前第一个节点不为空，说明列表不为空 f.prev = newNode; // 当前列表头部连接上插入的节点 size++; modCount++; }
时间复杂度
add()方法有三种增加方式 , 头插 , 尾插 , 中间插入 , 头插和尾插时间复杂度为O(1) , 因为不需要通过遍历找到上一个节点 , 但是中间插入时间复杂度为O(N) , 因为需要调用node(int index)找到下标对应的元素 , 然后在这个元素后面插入
get() public E get(int index) { // 检查 index 是否越界，上面分析过了 checkElementIndex(index); return node(index).item; } Node<E> node(int index) { // 如果 index 小于 size 的一半，从开头开始查找 if (index < (size >> 1)) { Node<E> x = first; // 从头开始查找,直到 i == index for (int i = 0; i < index; i++) x = x.next; return x; } else { // 如果 index 大于 size 的一半，从尾部开始查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
getFirst()和getLast()
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; }
时间复杂度
get()方法的时间复杂度也要分开说明 , 因为LinkendList的实现中保存了头尾元素 , 所以可以直接获取 , 时间复杂度为O(1) , 但是如果是根据下标获取 , 那么就要通过遍历来获取下标对应的元素 , 时间复杂度为O(N)
remove()
public E remove(int index) { // 检查 index 是否越界 checkElementIndex(index); return unlink(node(index)); } public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return unlinkLast(l); }
可以看到 , remove()方法和add()方法类似 , 也是分别调用了unlink() unlinkFirst() unlinkLast() , 分别表示删除某个节点 , 删除头节点 , 删除尾结点
E unlink(Node<E> x) { // assert x != null; // 获取到当前节点的元素 final E element = x.item; // 获取到下一个节点 final Node<E> next = x.next; // 获取到前一个节点 final Node<E> prev = x.prev; // 如果当前节点前一个节点为空，说明为头部节点 if (prev == null) { // 直接设置下一个节点为首节点即可 first = next; } else { // 不为空，说明是中间节点或者尾节点 // 将前一个节点连接到下一个节点 prev.next = next; x.prev = null; }
if (next == null) { // 如果当前节点下一个节点为空，说明是尾部节点 // 尾部节点移除了，所以将前一个节点设为尾部节点 last = prev; } else { // 不为空，说明是中间节点 // 将前一个节点连接到下一个节点 next.prev = prev; // 当前节点断开与下一个节点的连接 x.next = null; } // 当前节点元素设置为空，方便 GC x.item = null; size--; // 修改次数+1 modCount++; return element; }
private E unlinkFirst(Node<E> f) { // assert f == first && f != null; // 获取到当前节点的元素 final E element = f.item; // 获取到当前节点的下一个元素 final Node<E> next = f.next; f.item = null; f.next = null; // help GC // 将当前节点的下一个节点设置为头部节点 first = next; // 如果下一个节点为空，说明链表只有一个节点 if (next == null) // 清空尾部节点 last = null; else // 否则，说明还有其他节点 // 下一个节点已经设置为头部节点了 // 所以清空一下与前一个节点的 关联 next.prev = null; size--; // 数量 -1 modCount++; return element; }
private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; }
时间复杂度
删除的时间复杂度为O(1) , 直接找到需要删除的前驱节点及后继节点 , 然后将被删除元素的前驱节点指针指向后继节点即可 , 因为是双向链表 , 所以可以直接操作前驱节点 , 如果是单向链表的话就不行
clear() public void clear() { // 遍历一遍全部设置为空 for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
时间复杂度
从代码的实现不难看出 , clear()方法的时间复杂度为O(N) , 因为是通过遍历然后将元素依次置空 , 所以时间复杂度为O(N)
更多方法可以查看 https://www.runoob.com/manual/jdk11api/java.base/java/util/LinkedList.html
小结
LinkendList从物理结构来说是一种线性结构 , 而从逻辑结构来说是一种链式存储结构 , 虽然是线性结构 , 但是并不会按照线性的顺序存储 , 而是分散存储在内存中 , 通过指针来建立节点与节点之间的联系, 同时实现了Deque这也说明它是一个双向链表 , 在源码中 , 没有看到它对线程安全问题的处理 , 所以它同时还是一个线程不安全的链表 , 也没有看到不允许插入null元素 , 重复元素的处理 , 所以它又是一个允许重复元素以及null元素的链表
