privatevoidwriteObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out element count, and any hidden stuff int expectedModCount = modCount; s.defaultWriteObject();
// Write out size as capacity for behavioral compatibility with clone() s.writeInt(size);
// Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); }
if (modCount != expectedModCount) { thrownew ConcurrentModificationException(); } }
privatevoidreadObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic 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()); }
voidlinkLast(E e){ final LinkedList.Node<E> l = last; final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
注意 for 循环中的 linkLast() 方法,它可以把链表重新链接起来,这样就恢复了链表序列化之前的顺序。很妙,对吧?
publicbooleanadd(E e){ linkLast(e); returntrue; } voidlinkLast(E e){ final LinkedList.Node<E> l = last; final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
先将队尾的节点 last 存放到临时变量 l 中(不是说不建议使用 I 作为变量名吗?Java 的作者们明知故犯啊),然后生成新的 Node 节点,并赋给 last,如果 l 为 null,说明是第一次添加,所以 first 为新的节点;否则将新的节点赋给之前 last 的 next。
插入到指定位置的源码:
publicvoidadd(int index, E element){ checkPositionIndex(index);
if (index < (size >> 1)) { LinkedList.Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { LinkedList.Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } voidlinkBefore(E e, LinkedList.Node<E> succ){ // assert succ != null; final LinkedList.Node<E> pred = succ.prev; final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
找到指定位置上的元素(succ)之后,就开始执行 linkBefore() 方法了,先将 succ 的前一个节点(prev)存放到临时变量 pred 中,然后生成新的 Node 节点(newNode),并将 succ 的前一个节点变更为 newNode,如果 pred 为 null,说明插入的是队头,所以 first 为新节点;否则将 pred 的后一个节点变更为 newNode。
/** * @author 微信搜「沉默王二」,回复关键字 PDF */ publicclassLinkedListTest{ publicstaticvoidaddFromHeaderTest(int num){ LinkedList<String> list = new LinkedList<String>(); int i = 0; long timeStart = System.currentTimeMillis(); while (i < num) { list.addFirst(i + '沉默王二'); i++; } long timeEnd = System.currentTimeMillis();
publicclassArrayListTest{ publicstaticvoidaddFromMidTest(int num){ ArrayList<String> list = new ArrayList<String>(num); int i = 0;
long timeStart = System.currentTimeMillis(); while (i < num) { int temp = list.size(); list.add(temp / 2 + '沉默王二'); i++; } long timeEnd = System.currentTimeMillis();
publicclassLinkedListTest{ publicstaticvoidaddFromMidTest(int num){ LinkedList<String> list = new LinkedList<String>(); int i = 0; long timeStart = System.currentTimeMillis(); while (i < num) { int temp = list.size(); list.add(temp / 2, i + '沉默王二'); i++; } long timeEnd = System.currentTimeMillis();
publicclassLinkedListTest{ publicstaticvoidaddFromTailTest(int num){ LinkedList<String> list = new LinkedList<String>(); int i = 0; long timeStart = System.currentTimeMillis(); while (i < num) { list.add(i + '沉默王二'); i++; } long timeEnd = System.currentTimeMillis();
publicbooleanremove(Object o){ final Object[] es = elementData; finalint size = this.size; int i = 0; found: { if (o == null) { for (; i < size; i++) if (es[i] == null) break found; } else { for (; i < size; i++) if (o.equals(es[i])) break found; } returnfalse; } fastRemove(es, i); returntrue; } public E remove(int index){ Objects.checkIndex(index, size); final Object[] es = elementData;
@SuppressWarnings('unchecked') E oldValue = (E) es[index]; fastRemove(es, index);
publicbooleanremove(Object o){ if (o == null) { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); returntrue; } } } else { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
也是先前后半段遍历,找到要删除的元素后调用 unlink(Node)。
removeFirst(),删除第一个节点
public E removeFirst(){ final LinkedList.Node<E> f = first; if (f == null) thrownew NoSuchElementException(); return unlinkFirst(f); } private E unlinkFirst(LinkedList.Node<E> f){ // assert f == first && f != null; final E element = f.item; final LinkedList.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; }
intindexOfRange(Object o, int start, int end){ Object[] es = elementData; if (o == null) { for (int i = start; i < end; i++) { if (es[i] == null) { return i; } } } else { for (int i = start; i < end; i++) { if (o.equals(es[i])) { return i; } } } return -1; }
根据元素找索引的话,就需要遍历整个数组了,从头到尾依次找。
2)LinkedList
遍历 LinkedList 找到某个元素的话,通常也有两种形式:
get(int),找指定位置上的元素
public E get(int index){ checkElementIndex(index); return node(index).item; }
既然需要调用 node(int) 方法,就意味着需要前后半段遍历了。
indexOf(Object),找元素所在的位置
publicintindexOf(Object o){ int index = 0; if (o == null) { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (LinkedList.Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
需要遍历整个链表,和 ArrayList 的 indexOf() 类似。
那在我们对集合遍历的时候,通常有两种做法,一种是使用 for 循环,一种是使用迭代器(Iterator)。
如果使用的是 for 循环,可想而知 LinkedList 在 get 的时候性能会非常差,因为每一次外层的 for 循环,都要执行一次 node(int) 方法进行前后半段的遍历。
if (index < (size >> 1)) { LinkedList.Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { LinkedList.Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
那如果使用的是迭代器呢?
LinkedList<String> list = new LinkedList<String>(); for (Iterator<String> it = list.iterator(); it.hasNext();) { it.next(); }