集合源码-LinkedList

1、简介

LinkedList是一个以双向链表实现的List，它除了作为List使用，还可以作为队列或者栈来使用。 LinkedList 也支持空值和重复值。LinkedList 是非线程安全的集合类。

2、继承体系

LinkedList不仅实现了List接口，还实现了Queue和Deque接口，所以它既能作为List使用，也能作为双端队列使用，当然也可以作为栈使用。

3、源码分析

3.1 主要属性

// 长度 transient int size = 0; // 首节点 transient Node<E> first; // 尾结点 transient Node<E> last;

3.2 构造方法

public LinkedList() { } // 无界 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

3.3 添加元素

LinkedList 除了实现了 List 接口相关方法，还实现了 Deque 接口的很多方法，所以我们有很多种方式插入元素。作为一个双端队列，添加元素主要有两种，一种是在队列尾部添加元素，一种是在队列首部添加元素。

两端插入 // 默认为尾插入 public boolean add(E e) { linkLast(e); return true; } // 头部插入 private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } // 尾部插入 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); // last指向未结点 last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); } public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; } 中间添加元素 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++; } public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); }

3.3 删除元素

在队列首尾删除元素很高效，时间复杂度为O(1)。 在中间删除元素比较低效，首先要找到删除位置的节点， 再修改前后指针，时间复杂度为O(n)。

public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } public boolean remove(Object o) { if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } 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; } x.item = null; size--; 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--; 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; } 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); } public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }

4、总结

LinkedList双链表实现的List；

LinkedList可以作为队列、双端队列、栈；

LinkedList在队列首尾添加、删除元素非常高效

LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；