JDK源码学习系列05----LinkedList
1.LinkedList简介
LinkedList是基于双向链表实现的,它也可以被当作堆栈、队列或双端队列进行操作。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.SerializableLinkedList继承了AbstractSequentialList<E>,并实现了List<E>, Deque<E>, Cloneable, java.io.Serializable等接口。AbstractSequentialList 实现了get(int index)、set(int index, E element)、add(int index, E element) 和 remove(int index)这些函数.
2.LinkedList的成员变量
private transient Entry<E> header = new Entry<E>(null, null, null); private transient int size = 0;LinkedList有两个成员变量,表头 header 和长度size.
3.LinkedList的构造函数
public LinkedList() {//构造一个空链表 header.next = header.previous = header; } public LinkedList(Collection<? extends E> c) {//将一个数据类型相同的集合添加到LinkedList的尾部 this(); addAll(c); }
4.LinkedList的内部类。
a.Entry<E>是LinkedList的节点类,节点类包含:当前节点的值,前一节点,后一节点。该节点类是一个静态内部类:当内部类对象不需要访问外围类对象时,应该声明为静态内部类。
private static class Entry<E> { E element; Entry<E> next; Entry<E> previous; Entry(E element, Entry<E> next, Entry<E> previous) { this.element = element; this.next = next; this.previous = previous; } }b.ListItr 是 LinkedList 的迭代器类
private class ListItr implements ListIterator<E> { private Entry<E> lastReturned = header;//上一次返回的节点 private Entry<E> next;//下一节点 private int nextIndex;//下一节点的索引 private int expectedModCount = modCount;//!!!!!!期望的改变次数~ Java的 fail-fast 机制。 ListItr(int index) { if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); if (index < (size >> 1)) {//size>>1是右移一位,即size/2 ,若索引值小于 size/2则从前开始 next = header.next; for (nextIndex=0; nextIndex<index; nextIndex++) next = next.next; } else {//否则从后开始 next = header; for (nextIndex=size; nextIndex>index; nextIndex--) next = next.previous; } } public boolean hasNext() {//是否存在下一个元素 return nextIndex != size;//通过下一节点索引值是否等于size来判断是否到了最末尾 } public E next() { checkForComodification(); if (nextIndex == size)//!! throw new NoSuchElementException(); lastReturned = next; next = next.next; nextIndex++; return lastReturned.element; } public boolean hasPrevious() {//是否存在上一个 return nextIndex != 0;//通过下一节点的索引值是否等于0来判断是否在最前面即头节点,由此来判断是否有前节点 } public E previous() {//取得上一元素 if (nextIndex == 0) throw new NoSuchElementException(); lastReturned = next = next.previous; //?????? nextIndex--; checkForComodification(); return lastReturned.element; } public int nextIndex() { return nextIndex; } public int previousIndex() {//上一元素的索引 return nextIndex-1; } public void remove() {//删除当前节点!! checkForComodification(); Entry<E> lastNext = lastReturned.next; try { LinkedList.this.remove(lastReturned); } catch (NoSuchElementException e) { throw new IllegalStateException(); } if (next==lastReturned) next = lastNext; else nextIndex--; lastReturned = header; expectedModCount++; } public void set(E e) { if (lastReturned == header) throw new IllegalStateException(); checkForComodification(); lastReturned.element = e; } public void add(E e) {//讲e添加到当前节点前面 checkForComodification(); lastReturned = header; addBefore(e, next); nextIndex++; expectedModCount++; } final void checkForComodification() {//!!!!!判断 modCount是否等于 expectedModCount来实现fail-fast机制。 if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
c.
private class DescendingIterator implements Iterator { final ListItr itr = new ListItr(size()); public boolean hasNext() { return itr.hasPrevious(); } public E next() { return itr.previous(); } public void remove() { itr.remove(); } }
由于LinkedList的成员函数很多,就不单独每一个做为一部分,把一些类似的函数放在一起,经常被调用的比较复杂的函数再单独介绍。
a.
public E getFirst() {//取得第一个节点的值 if (size==0) throw new NoSuchElementException();//时刻注意特殊情况的考虑 return header.next.element; } public E getLast() { if (size==0) throw new NoSuchElementException(); return header.previous.element;//获得最后一个是 header.previous.element } public E removeFirst() {//移除第一个节点 return remove(header.next);//remove函数下面单独介绍 } public E removeLast() {//移除最后一个节点 return remove(header.previous); } public void addFirst(E e) {//在 addBefore(e, header.next); } public void addLast(E e) { addBefore(e, header); } public boolean contains(Object o) { return indexOf(o) != -1; } public int size() { return size; } public boolean add(E e) {//在最末尾添加值为e的节点,添加在header前即最末尾 addBefore(e, header); return true; }b. boolean remove(Object o) / E remove() / E remove(Entry<E> e)
public boolean remove(Object o) { if (o==null) {//即使是null也要查找到然后再移除 for (Entry<E> e = header.next; e != header; e = e.next) { if (e.element==null) { remove(e);//调用下面的方法 return true; } } } else { for (Entry<E> e = header.next; e != header; e = e.next) { if (o.equals(e.element)) { remove(e); return true; } } } return false; } private E remove(Entry<E> e) { if (e == header) throw new NoSuchElementException();//考虑头指针的特殊情况 E result = e.element; e.previous.next = e.next;//!!! e.next.previous = e.previous;//!!! e.next = e.previous = null;// ???不是特别理解 e.element = null; size--; modCount++; return result; }c.boolean addAll(Collection<? extends E> c) / boolean addAll(int index, Collection<? extends E> c)
d.
public void clear() {//清空LinkedList Entry<E> e = header.next; while (e != header) { Entry<E> next = e.next; e.next = e.previous = null; e.element = null; e = next; } header.next = header.previous = header; size = 0; modCount++; } public E get(int index) {//获得某索引对应的节点值 return entry(index).element; } public E set(int index, E element) {//设置某索引的节点值 Entry<E> e = entry(index); E oldVal = e.element; e.element = element; return oldVal; } public void add(int index, E element) { addBefore(element, (index==size ? header : entry(index))); } public E remove(int index) {//移除节点 return remove(entry(index)); }e.Entry<E> entry(int index)
此方法得到某索引对应的节点对象
private Entry<E> entry(int index) { if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: "+index+ ", Size: "+size); Entry<E> e = header; if (index < (size >> 1)) {//若小于size/2,则从头遍历 for (int i = 0; i <= index; i++) e = e.next; } else {//否则从尾遍历 for (int i = size; i > index; i--) e = e.previous; } return e; }
f.
public E peek() {//获取第一个元素的值 if (size==0) return null; return getFirst(); } public E element() {//获取第一个元素的值 return getFirst(); } public E poll() {//移除第一个元素 if (size==0) return null; return removeFirst(); } 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() { if (size==0) return null; return getFirst(); } public E peekLast() { if (size==0) return null; return getLast(); } public E pollFirst() { if (size==0) return null; return removeFirst(); } public E pollLast() { if (size==0) return null; return removeLast(); } public void push(E e) { addFirst(e); } public E pop() { return removeFirst(); }g.Entry<E> addBefore(E e, Entry<E> entry)
private Entry<E> addBefore(E e, Entry<E> entry) { Entry<E> newEntry = new Entry<E>(e, entry, entry.previous); newEntry.previous.next = newEntry; newEntry.next.previous = newEntry; size++; modCount++; return newEntry; }
public Object[] toArray() { Object[] result = new Object[size]; int i = 0; for (Entry<E> e = header.next; e != header; e = e.next) result[i++] = e.element; return result; } 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 (Entry<E> e = header.next; e != header; e = e.next) result[i++] = e.element; if (a.length > size) a[size] = null; return a; }
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out size s.writeInt(size); // Write out all elements in the proper order. for (Entry e = header.next; e != header; e = e.next) s.writeObject(e.element); } private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read in size int size = s.readInt(); // Initialize header header = new Entry<E>(null, null, null); header.next = header.previous = header; // Read in all elements in the proper order. for (int i=0; i<size; i++) addBefore((E)s.readObject(), header); }
5.方法归类
a.LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下表的方法等价:
队列方法 等效方法
add(e) addLast(e)
offer(e) offerLast(e)
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()
b.LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:
栈方法 等效方法
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()
6.总结
a.LinkedList是以双链表的形式实现的。
b.LinkedList即可以作为链表,还可以作为队列和栈。
c.LinkedList是 非 线程安全的。
JDK源码学习系列05----LinkedList,布布扣,bubuko.com
原文:http://blog.csdn.net/sheepmu/article/details/28316861