队列在Java类库中的实现——LinkedList一文中已经提到LinkedList是一个双向链表，它用一个整数来存储链表的长度：
transient int size = 0;用一个静态内部类来表示链表的节点： 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;}}它有指向链表第一个元素和最后一个元素的指针：transient Node<E> first;transient Node<E> last;接下来讲讲线性表的常见操作在LinkedList中的实现。
（1）查询线性表中是否包含某一个元素
public boolean contains(Object o) {return indexOf(o) != -1;}contains(Object o)调用indexOf(Object o)来查询线性表中是否包含某一个元素，indexOf(Object o)的实现如下： public int indexOf(Object o) {int index = 0;// 分o == null和o != null两种情况if (o == null) {/*** first节点是遍历链表的第一个元素；* x.next == null说明x是链表的最后一个节点，这是遍历介绍*/for (Node<E> x = first; x != null; x = x.next) {if (x.item == null)return index;index++;}} else {for (Node<E> x = first; x != null; x = x.next) {if (o.equals(x.item))return index;index++;}}// 返回-1说明链表中没有包含指定的元素return -1;}可见，查找的时间复杂度为O(n).（2）向线性表中插入元素，在队列在Java类库中的实现——LinkedList一文中说了LinkedList中如何把元素添加到链表的结尾，这里讲把元素添加到链表的指定位置： public void add(int index, E element) {// 验证index是否大于0并且小于size,如果不满足就抛出异常checkPositionIndex(index);/*** index == size就等于把元素添加到链表的最后；* 否则把元素添加到现在链表中索引为index的节点的前面，也就是把它放在*/if (index == size)linkLast(element);elselinkBefore(element, node(index));}node(int index)返回指定位置的节点；linkBefore(E e, Node<E> succ)用于把e添加到指定节点的前面，linkBefore(E e, Node<E> succ)实现如下： /*** 用e构造一个节点，放在succ的前面*/void linkBefore(E e, Node<E> succ) {// assert succ != null;// 获得succ的前驱final Node<E> pred = succ.prev;// 用e构造一个节点，该节点的前驱是succ的前驱，后继是succfinal Node<E> newNode = new Node<>(pred, e, succ);// 把新节点的前驱设置为新节点succ.prev = newNode;/*** pred为空，说明succ为链表第一个节点；* pred不为空，就把succ之前的前驱的后继设置为新节点*/if (pred == null)first = newNode;elsepred.next = newNode;// 链表长度加1size++;modCount++;}node(int index)实现如下： Node<E> node(int index) {// assert isElementIndex(index);/*** index小于size的一半，就是说，要查找的元素在链表的前半部分，就从头节点开始搜索；* index大于size的一半，就是说，要查找的元素在链表的后半部分，就从尾节点开始搜索；*/if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;// x是第index-1个节点的后继return x;} else {Node<E> x = last;for (int i = size – 1; i > index; i–)x = x.prev;// x是第index+1个节点的前驱return x;}}找到指定位置的元素节点的时间复杂度为O(n)，也就是说，插入的时间复杂度为O(n)。（3）从线性表删除元素
队列在Java类库中的实现——LinkedList一文中已经讲了从线性表的开头和结尾删除节点，这里讲从线性表的指定位置删除节点：
public E remove(int index) {// 验证index是否大于0并且小于size,如果不满足就抛出异常checkElementIndex(index);// node(index)返回index处的节点，删除这个节点return unlink(node(index));}unlink(Node<E> x)用来删除某个节点，实现如下：E unlink(Node<E> x) {// assert x != null;final E element = x.item;final Node<E> next = x.next;final Node<E> prev = x.prev;/*** 如果x是链表唯一的一个元素，那么接下来的两个if语句会让first和* last都指向null；* 如果x既不是头节点也不是尾节点，，那么只是将x的前驱的指向后继元素的* 指针指向x的后继元素，将x的后继元素的指向前驱的指针指向x的前驱；* 如果x是首节点但不是尾节点，那么first指向next，prev等于null，* x的后继元素的指向前驱的指针指向null；* 如果x是尾节点但不是首节点，那么next等于null，x的前驱指向后继* 元素的指针指向null，last指向prev*//*** 这一部分让x的前驱节点的指向后继元素的指针指向x的后继；* prev == null说明x是链表的第一个节点，x没有前驱，于是就把* first指向next;* 否则就让x的前驱的指向后继元素的指针指向x的后继，并回收x的指向前驱* 的指针*/if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}/*** 这一步让x的后继节点的指向前驱元素的指针指向x的前驱；* next == null说明x是链表的最后一个元素，x没有后继节点，* 就让last指向prev；* 否则就让x的后继的指向前驱的指针指向x的前驱，并回收x的指向* 后继元素的指针*/if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}// 回收x.itemx.item = null;// 链表长度减1size–;modCount++;return element;}和向线性表中插入元素一样，删除元素需要首先找到一个元素，找到这个元素的时间决定了删除元素的时间，也就是说，删除一个元素的时间复杂度为O(n)。
肯承认错误则错已改了一半
