双端链表LinkedList

基本概念

LinkedList实现了List接口，底层的链表结构使它支持高效的插入和删除操作。
实现了Deque接口，具有队列的特性。
LinkedList不是线程安全的，如果想使LinkedList变成线程安全（在拥有共享数据的多条线程并行执行的程序中，线程安全的代码会通过同步机制保证各个线程都可以正常且正确的执行，不会出现数据污染等意外情况），可以调用静态类Collections类中的synchronizedList方法：

List list=Collections.synchronizedList(new LinkedList(...));
1

结构组成

LinkedList由多个下图所示的单结点和双向箭头组成双向链表。
单结点代码：

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;
	}
}
1
2
3
4
5
6
7
8
9
10

基本方法

add(E e) 方法：将元素添加到链表尾部。
add(int index,E e)：在指定位置添加元素。
addAll(Collection c )：将集合插入到链表尾部。
addAll(int index, Collection c)： 将集合从指定位置开始插入。
addFirst(E e)： 将元素添加到链表头部。
addLast(E e)： 将元素添加到链表尾部，与 add(E e) 方法一样。
get(int index)： 根据指定索引返回数据。
getFirst(),element(),peek(),peekFirst()： 获取头节点（index=0）数据。getFirst() 和element() 方法将会在链表为空时，抛出异常NoSuchElementException，element()方法的内部就是使用getFirst()实现的。
获取尾节点（index=-1）数据方法: getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。
根据对象得到索引的方法：int indexOf(Object o)： 从头遍历找，int lastIndexOf(Object o)： 从尾遍历找。
检查链表是否包含某对象：contains(Object o)： 检查对象o是否存在于链表中。
删除：remove() ,removeFirst(),pop(): 删除头节点，removeLast(),pollLast(): 删除尾节点，removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。remove(int index)：删除指定位置的元素。