容器学习八：LinkedList源码分析
?一.概述
- LinkedList继承Deque，所以LinkedList的插入删除操作遵循先进性出FIFO。LinkedList继承Deque，所以Linkedist实现了Deque的操作，比喻offer peek pollfirst/last等操作。其实这些操作也就是建立在getFirst getLast addFirst addLast removeFirst removeLast这几个操作上的。
?
二.成员变量
//头节点private transient Entry<E> header = new Entry<E>(null, null, null);private transient int size = 0;
?
三.节点Entry对象
//节点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;}}??四.构造函数
//初始化public LinkedList() {header.next = header.previous = header;}?五.存数据
//默认插入到最后public boolean add(E e) {addBefore(e, header);return true;}//把元素e插入最前public void addFirst(E e) {//等价于把元素e插入到原第一个节点header.next的前面addBefore(e, header.next);}//把元素e插入最后public void addLast(E e) {//等价于把元素e插入到header的前面，因为是双链表addBefore(e, header);}//在指定位置插入元素e，原index处和以后的元素往后移public void add(int index, E element) {//index == size,把元素e插入到header的前面//其他情况把元素e插入entry(index)的前面addBefore(element, (index == size ? header : entry(index)));}//把元素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 E get(int index) {return entry(index).element;}private Entry<E> entry(int index) {if (index < 0 || index >= size)throw new IndexOutOfBoundsException("Index: " + index + ", Size: "+ size);Entry<E> e = header;//在链表中取值时，需要遍历整个链表，//即使优化成遍历半个链表，相对于ArrayList的随机访问，还是慢的if (index < (size >> 1)) {for (int i = 0; i <= index; i++)e = e.next;} else {for (int i = size; i > index; i--)e = e.previous;}return e;}//取第一个节点处的元素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;}//和ArrayList一样的算法，只是ArrayList遍历数组，LinkedList遍历链表public int indexOf(Object o) {int index = 0;if (o == null) {//遍历链表for (Entry e = header.next; e != header; e = e.next) {if (e.element == null)return index;index++;}} else {for (Entry e = header.next; e != header; e = e.next) {if (o.equals(e.element))return index;index++;}}return -1;}??六.删数据
//remove默认删除第一个位置的元素public E remove() {return removeFirst();}public E removeFirst() {return remove(header.next);}public E removeLast() {return remove(header.previous);}//和ArrayList一样的算法，只是ArrayList遍历数组，LinkedList遍历链表public boolean remove(Object o) {if (o == null) {for (Entry<E> e = header.next; e != header; e = e.next) {if (e.element == null) { //转换成remove(Entry)remove(e);return true;}}} else {for (Entry<E> e = header.next; e != header; e = e.next) {if (o.equals(e.element)) {//转换成remove(Entry)remove(e);return true;}}}return false;}//转换成remove(Entry)public E remove(int index) {return remove(entry(index));}//删除指定节点:删除操作都将落到这个方法上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;}?七.遍历
private class ListItr implements ListIterator<E> {private Entry<E> lastReturned = header;private Entry<E> next;private int nextIndex;private int expectedModCount = modCount; //初始化的时候next = header.next;ListItr(int index) {if (index < 0 || index > size)throw new IndexOutOfBoundsException("Index: " + index+ ", Size: " + size);if (index < (size >> 1)) {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;} //遍历的时候next = next.next，按照从头往后遍历，也就是FIFO的顺序public E next() {checkForComodification();if (nextIndex == size)throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.element;}}??
?