我们都站在巨人的肩膀上
1.LinkedList 源码：
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ // transient修饰的字段将不进行序列化，该变量内容在序列化后无法获得访问 transient int size = 0; transient Node<E> first; transient Node<E> last; public LinkedList() { } // 指定集合创建LinkedList public LinkedList(Collection<? extends E> c) { this(); addAll(c); } // 设置头节点 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 = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } // 在非空节点前插入元素 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++; } //首元素设置为null，GC回收 private E unlinkFirst(Node<E> f) { // assert f == first && f != null; final E element = f.item; final Node<E> next = f.next; // item、next 同时为null，GC才能回收 f.item = null; f.next = null; // help GC first = next; if (next == null) last = null; else next.prev = null; size--; modCount++; return element; } //末位设置为null，GC回收 private E unlinkLast(Node<E> l) { // assert l == last && l != null; final E element = l.item; final Node<E> prev = l.prev; // item、next 同时为null，GC才能回收 l.item = null; l.prev = null; // help GC last = prev; if (prev == null) first = null; else prev.next = null; size--; modCount++; return element; } // 指定元素设置为null 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; } // 获取头结点 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; } // 删除首节点 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); } // 添加首节点、实际上调用的是linkFirst，对linkFirst进行封装 public void addFirst(E e) { linkFirst(e); } // 添加尾节点、实际上调用的是linkLast，对linkLast进行封装 public void addLast(E e) { linkLast(e); } // 是否包含此元素 public boolean contains(Object o) { return indexOf(o) != -1; } public int size() { return size; } // 默认在尾节点添加元素，成功返回true public boolean add(E e) { linkLast(e); return true; } // 删除节点 public boolean remove(Object o) { if (o == null) { // 遍历树 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { // 将该元素设置为null,GC回收 unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { // 将该元素设置为null,GC回收 unlink(x); return true; } } } return false; } // 添加尾节点处添加集合 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; } // 清空 public void clear() { // 整个集合设置为null 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++; } // 根据下标获取元素 public E get(int index) { // 检查下标 checkElementIndex(index); return node(index).item; } // 根据下标设置元素 public E set(int index, E element) { checkElementIndex(index); Node<E> x = node(index); E oldVal = x.item; x.item = element; return oldVal; } /** * Inserts the specified element at the specified position in this list. * Shifts the element currently at that position (if any) and any * subsequent elements to the right (adds one to their indices). * * @param index index at which the specified element is to be inserted * @param element element to be inserted * @throws IndexOutOfBoundsException {@inheritDoc} */ public void add(int index, E element) { checkPositionIndex(index); if (index == size) linkLast(element); else linkBefore(element, node(index)); } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); } private boolean isElementIndex(int index) { return index >= 0 && index < size; } private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } // 越界信息 private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; } private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } // 返回节点信息 Node<E> node(int index) { // assert isElementIndex(index); // 获取节点，size >>1 更高效 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; } } // 检查该元素释放存在，存在返回下标，不存在返回-1 public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; } // 从后往前遍历获取元素，返回下标 public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; } public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } public E element() { return getFirst(); } public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } public E remove() { return removeFirst(); } public boolean offer(E e) { return add(e); } public boolean offerFirst(E e) { addFirst(e); return true; } public boolean offerLast(E e) { addLast(e); return true; } public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); } public boolean removeFirstOccurrence(Object o) { return remove(o); } public boolean removeLastOccurrence(Object o) { if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } // 迭代器 public ListIterator<E> listIterator(int index) { checkPositionIndex(index); return new ListItr(index); } // 重写 迭代器 private class ListItr implements ListIterator<E> { private Node<E> lastReturned = null; private Node<E> next; private int nextIndex; private int expectedModCount = modCount; ListItr(int index) { // assert isPositionIndex(index); next = (index == size) ? null : node(index); nextIndex = index; } public boolean hasNext() { return nextIndex < size; } public E next() { checkForComodification(); if (!hasNext()) throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } public boolean hasprevious() { return nextIndex > 0; } public E previous() { checkForComodification(); if (!hasPrevious()) throw new NoSuchElementException(); lastReturned = next = (next == null) ? last : next.prev; nextIndex--; return lastReturned.item; } public int nextIndex() { return nextIndex; } public int previousIndex() { return nextIndex - 1; } public void remove() { checkForComodification(); if (lastReturned == null) throw new IllegalStateException(); Node<E> lastNext = lastReturned.next; unlink(lastReturned); if (next == lastReturned) next = lastNext; else nextIndex--; lastReturned = null; // 迭代器执行次数 expectedModCount++; } public void set(E e) { if (lastReturned == null) throw new IllegalStateException(); checkForComodification(); lastReturned.item = e; } public void add(E e) { checkForComodification(); lastReturned = null; if (next == null) linkLast(e); else linkBefore(e, next); nextIndex++; expectedModCount++; } // 检查linkedList操作次数与迭代器操作次数释放相同 final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } } 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; } } /** * @since 1.6 */ public Iterator<E> descendingIterator() { return new DescendingIterator(); } // 返回一个迭代器在此双端队列以逆向顺序的元素 private class DescendingIterator implements Iterator<E> { private final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } } // 克隆后返回LinkedList集合 @SuppressWarnings("unchecked") private LinkedList<E> superClone() { try { return (LinkedList<E>) super.clone(); } catch (CloneNotSupportedException e) { throw new InternalError(); } } // 克隆 public Object clone() { LinkedList<E> clone = superClone(); // 克隆放为初始状态 clone.first = clone.last = null; clone.size = 0; clone.modCount = 0; // Initialize clone with our elements for (Node<E> x = first; x != null; x = x.next) clone.add(x.item); return clone; } //对象转为LinkedList public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } // 指定集合转为LinkedList @SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; if (a.length > size) a[size] = null; return a; } // 序列化 private static final long serialVersionUID = 876323262645176354L; // 写入流 private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { //写入所有信息和隐藏信息 s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); } // 读出流 @SuppressWarnings("unchecked") private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // 读所有信息和隐藏信息 s.defaultReadObject(); // Read in size int size = s.readInt(); // Read in all elements in the proper order. for (int i = 0; i < size; i++) linkLast((E)s.readObject()); }}新闻热点
疑难解答
