容器学习八：LinkedList源码分析

 一.概述

1. LinkedList继承Deque，所以LinkedList的插入删除操作遵循先进性出FIFO。
2. 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;
		}

		
	}