// 遍历数组a, 将数据插入 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; // 创建新节点 Node<E> newNode = new Node<>(pred, e, null); // 如果pred是null, 插入到头部位置 if (pred == null) first = newNode; else pred.next = newNode; pred = newNode; }
// 修改succ和pred的指向 if (succ == null) { // 如果 succ 为 null , 说明插入队尾, 则直接修改 last 指向最后一个 pred last = pred; } else { // 如果 succ 非 null, 说明插入到 succ 的前面 pred.next = succ; succ.prev = pred; }
public E removeFirst(){ final Node<E> f = first; // 如果链表为空, 抛出异常 if (f == null) thrownewN oSuchElementException(); // 移除链表首个元素 return unlinkFirst(f); }
private E unlinkFirst(Node<E> f){ // assert f == first && f != null; final E element = f.item; // 获得f的下一个节点 final Node<E> next = f.next; // 设置f的item为null, 帮助GC f.item = null; // 设置f的next为null, 帮助GC f.next = null; // help GC // 修改first指向next first = next; // 修改next节点的prev指向null if (next == null) // 如果链表只有一个元素, 说明被移除后, 队列就是空的, 则last设置为null last = null; else next.prev = null; // 链表大小减一 size--; // 增加数组修改次数 modCount++; return element; }
另外还有实现Queue接口的几个方法
1 2 3 4 5 6 7 8 9 10 11 12 13
public E poll(){ final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
public E pop(){ return removeFirst(); }
public E pollFirst(){ final Node<E> f = first; return (f == null) ? null : unlinkFirst(f); }
public E removeLast(){ final Node<E> l = last; // 如果链表为空, 则抛出异常 if (l == null) thrownew NoSuchElementException(); // 移除链表的最后一个元素 return unlinkLast(l); }
private E unlinkLast(Node<E> l){ // assert l == last && l != null; final E element = l.item; // 获得f的上一个节点 final Node<E> prev = l.prev; // 设置l的item为null, 帮助GC l.item = null; // 设置l的prev为null, 帮助GC l.prev = null; // help GC // 修改last指向prev last = prev; // 修改prev节点的next指向null if (prev == null) // 如果链表只有一个元素, 说明被移除后, 队列就是空的, 则first设置为null first = null; else prev.next = null; // 链表大小减一 size--; // 数组修改次数加一 modCount++; return element; }
publicvoidclear(){ // 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 // 顺序遍历链表, 设置每个节点前后指向为null // 通过这样的方式, 帮助GC for (Node<E> x = first; x != null; ) { // 获取下一个节点 Node<E> next = x.next; // 设置x的item,next,prev为null x.item = null; x.next = null; x.prev = null; // 设置下一个节点为x x = next; } // 清空first和last的指向 first = last = null; // 设置链表大小为0 size = 0; // 增加数组修改次数 modCount++; }
publicintindexOf(Object o){ int index = 0; if (o == null) { // 如果o为null // 顺序遍历, 如果item为null, 进行返回 for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { // 如果o非null // 顺序遍历, 如果item为o的节点, 进行返回 for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } // 未找到 return -1; }
publicintlastIndexOf(Object o){ int index = size; if (o == null) { // o为null // 倒序遍历, 如果item为null, 返回 for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { // o非null // 倒序遍历, 如果item为o的节点, 返回 for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } // 找不到 return -1; }
7.3.获得指定位置的元素
由于 LinkedList 不支持随机访问，所以该方法时间复杂度为 O(n)
1 2 3 4 5
public E get(int index){ checkElementIndex(index); // 基于node()方法实现, 时间复杂度为O(n) return node(index).item; }
@java.io.Serial privatevoidwriteObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic // 写入非静态属性、非transient属性 s.defaultWriteObject();
// Write out size // 写入链表大小 s.writeInt(size);
// Write out all elements in the proper order. // 顺序遍历, 逐个序列化 for (Node<E> x = first; x != null; x = x.next) s.writeObject(x.item); }
8.2.反序列化
方法 #readObject(java.io.ObjectInputStream s) ，反序列化
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
@SuppressWarnings("unchecked") @java.io.Serial privatevoidreadObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic // 读取非静态属性、非transient属性 s.defaultReadObject();
// Read in size // 读取size int size = s.readInt();
// Read in all elements in the proper order. // 顺序遍历, 逐个反序列化 for (int i = 0; i < size; i++) linkLast((E)s.readObject()); // 添加到链表尾部 }
99.其他常用方法
99.1.转换为数组
方法 #toArray() ，将 LinkedList 转换为 Object 数组
1 2 3 4 5 6 7 8 9
public Object[] toArray() { // 创建Object数组 Object[] result = new Object[size]; // 顺序遍历节点, 设置到Object数组中 int i = 0; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item; return result; }
如果需要指定类型，可以用 toArray(T[] a) 方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
@SuppressWarnings("unchecked") public <T> T[] toArray(T[] a) { // 如果传入的数组小于size大小, 则直接复制一个新数组 if (a.length < size) a = (T[])java.lang.reflect.Array.newInstance( a.getClass().getComponentType(), size); // 顺序遍历链表, 复制到a中 int i = 0; Object[] result = a; for (Node<E> x = first; x != null; x = x.next) result[i++] = x.item;
// 如果传入的数组大于size大小, 则将size赋值为null if (a.length > size) a[size] = null;
// 返回a return a; }
99.2.求哈希值
类 java.util.AbstractList<E> 的 #hashCode() 方法
1 2 3 4 5 6 7
publicinthashCode(){ int hashCode = 1; // 遍历, 求哈希 for (E e : this) hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); return hashCode; }
