//x节点的值置null x.item = null; //大小-1 size--; //修改次数+ modCount++; return element; } //获取第一个节点的值 public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } //获取最后一个节点的值 public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } //移除第一个节点的值 public E removeFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); //调用unlinkFirst()方法 return unlinkFirst(f); } //移除最后一个节点值 public E removeLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); //调用unlinkLast()方法 return unlinkLast(l); } //将值放置第一个节点 public void addFirst(E e) { //调用linkFirst()方法 linkFirst(e); } //将值放置最后一个节点 public void addLast(E e) { //调用linkLast()方法 linkLast(e); } //获取元素的第一个下标 public int indexOf(Object o) { int index = 0; //如果o为null，则遍历所有节点查询(说明LinkedList是支持null值的) if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; //因为LinkedList为链表结构，没有下标，因为临时index充当下标(index是从0开始，因此应该后++) index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; //因为LinkedList为链表结构，没有下标，因为临时index充当下标(index是从0开始，因此应该后++) index++; } } //无该值 return -1; } //获取元素的最后一个下标 public int lastIndexOf(Object o) { int index = size; //如果o为null，则遍历所有节点查询(说明LinkedList是支持null值的) if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { //因为LinkedList为链表结构，没有下标，因为临时index充当下标(index是从0开始，因此应该先--) index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { //因为LinkedList为链表结构，没有下标，因为临时index充当下标(index是从0开始，因此应该先--) index--; if (o.equals(x.item)) return index; } } return -1; } //是否包含值 public boolean contains(Object o) { //indexOf()方法解析可发现此方法会遍历所有，因此应当尽可能少使用 return indexOf(o) != -1; } //返回链表大小 public int size() { return size; } //增加值 public boolean add(E e) { //默认在最后增加节点() linkLast(e); return true; } //删除值 public boolean remove(Object o) { //如果值为null，则删除第一个值为null的节点 if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { //调用unlink()方法 unlink(x); return true; } } } else { //如果值不为null，则删除第一个值为o的节点 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { //调用unlink()方法 unlink(x); return true; } } } return false; } //参数是否为现有元素的索引 private boolean isElementIndex(int index) { return index >= 0 && index < size; } //是否是迭代器或添加操作的有效位置的索引 private boolean isPositionIndex(int index) { return index >= 0 && index <= size; } //检查是否为现有元素的索引 private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //检查是否为迭代器或添加操作的有效位置的索引(最大现有元素下标+1) private void checkPositionIndex(int index) { if (!isPositionIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //根据下标获取节点 (类似二分查询法) Node<E> node(int index) { //应当保证是有值下标，但是并没有保证 // assert isElementIndex(index);
//如果index小于size的一半，则通过x.next if (index < (size >> 1)) { //从first开始next Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { //如果index大于等于size，则通过x.prev //从last开始next Node<E> x = prev; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //在index之后加入集合 public boolean addAll(int index, Collection<? extends E> c) { //检查下标是否为添加操作的有效位置的索引 checkPositionIndex(index);
//转换为数组 Object[] a = c.toArray(); //数组a的长度 int numNew = a.length; //如果数组长度为0则返回false if (numNew == 0) return false;
//遍历数组a for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; //新建一个对象(当前节点：pred，上一个节点：e，下一个节点：null) Node<E> newNode = new Node<>(pred, e, null); //如果pred为null则说明要在第一个节点前加入此节点 if (pred == null) //将新节点赋予first first = newNode; else //如果pred不为null则说明要在中间位置加入此节点 //将新节点赋予上个节点的下个节点 pred.next = newNode; //将当前节点赋予上个节点 pred = newNode; }
//size + 数组长度 size += numNew; //修改次数+1 modCount++; return true; } //在最后加入集合 public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } //清空链表 public void clear() { //清除节点之间的所有链接是“不必要的”，但如果丢弃的节点居住在一代以上，即使有一个可到达的迭代器，也肯定会释放内存，这有助于一代GC。 // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator //遍历去除强引用，使gc下次回收 for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } //去除强引用，使gc下次回收 first = last = null; //大小置 size = 0; //修改次数+1 modCount++; } //根据下标获得值 public E get(int index) { //检查下标是否为有值下标 checkElementIndex(index); //node(index)查询节点，然后返回值 return node(index).item; } //在下标处设置值 public E set(int index, E element) { //检查下标是否为有值下标 checkElementIndex(index); //根绝小标获取节点 Node<E> x = node(index); //旧值 E oldVal = x.item; //新值 x.item = element; //返回旧值 return oldVal; } //在下标处添加值 public void add(int index, E element) { //检查下标是否为添加操作的有效位置的索引 checkPositionIndex(index);
//如果下标等于链表大小，则说明加入在最后 if (index == size) //将值加入在最后 linkLast(element); else //如果下标不等于链表大小则说明要在该下标之前加入 linkBefore(element, node(index)); } //移除下标对应的节点 public E remove(int index) { //检查下标是否为有值下标 checkElementIndex(index); //移除该节点 return unlink(node(index)); } //返回第一个节点，但不删除，如果为null则返回null public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //返回第一个节点，如果为null则返回null，与peek()无区别 public E peekFirst() { final Node<E> f = first; return (f == null) ? null : f.item; } //返回最后一个节点的值 public E peekLast() { final Node<E> l = last; return (l == null) ? null : l.item; } //返回第一个节点的值(如果为空链则异常，与getFirst()无区别) public E element() { //调用getFirst() return getFirst(); } //查询第一个节点的值并删除(简而言之：出栈) public E poll() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //查询第一个节点的值并删除(简而言之：出栈，与pollFirst()无区别) public E pollFirst() { final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); } //查询最后一个节点的值并删除 public E pollLast() { final Node<E> l = last; return (l == null) ? null : unlinkLast(l); } //查询最后一个节点的值并删除 public E remove() { return removeFirst(); } //添加到最后一个节点(不知道与add(o)有什么区别) public boolean offer(E e) { return add(e); } //添加到第一个节点(与addFirst(o)无区别) public boolean offerFirst(E e) { addFirst(e); return true; } //添加到最后一个节点(与addLast(o)无区别) public boolean offerLast(E e) { addLast(e); return true; } //添加到第一个节点(简而言之：入栈) public void push(E e) { addFirst(e); } //返回值并删除第一个节点(简而言之：出栈) public E pop() { return removeFirst(); } //删除第一个值为o的节点 public boolean removeFirstOccurrence(Object o) { return remove(o); } //删除最后一个值为o的节点 public boolean removeLastOccurrence(Object o) { //判断o是否为null if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { if (x.item == null) { //删除该节点 unlink(x); return true; } } } else { //如果o不为null for (Node<E> x = last; x != null; x = x.prev) { if (o.equals(x.item)) { //删除该节点 unlink(x); return true; } } } return false; } //获取迭代器 public ListIterator<E> listIterator(int index) { //检查是否为迭代器或添加操作的有效位置的索引 checkPositionIndex(index); 返回迭代器 return new ListItr(index); } //转换为数组(与ArrayList不同，ArrayList是通过JNI调用本地方法，LinkedList是自己转换) public Object[] toArray() { //新建一个链表大小的数组 Object[] result = new Object[size]; int i = 0; //遍历并放入数组中 for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; } //将链表的值放入数组a中 public <T> T[] toArray(T[] a) { //如果a数组的大小小于链表大小 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); int i = 0; //将数组a的地址赋予result Object[] result = a; for (Node<E> x = first; x != null; x = x.next) //将链表的数据放入result中 result[i++] = x.item;