数组和结点这两种数据结构之间的差异,决定了LinkedList相比ArrayList拥有更高的插入和删除效率,而随机访问效率不如ArrayList。
transient只能用来修饰成员变量(field),被transient修饰的成员变量不参与序列化过程。
序列化: JVM中的Java对象转化为字节序列。
反序列化: 字节序列转化为JVM中的Java对象。
静态成员变量即使不加transient关键字也无法被序列化。
自定义序列化,无视transient关键字
public class Person implements Externalizable { private String nickName; private transient String realName; @Override public void writeExternal(ObjectOutput out) throws IOException { out.writeUTF(realName); out.writeUTF(childName); } @Override public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException { realName = in.readUTF(); childName = in.readUTF(); } public static void main(String[] args){ //序列化 os = new ObjectOutputStream(new FileOutputStream(filePath)); os.writeObject(x); //反序列化 is = new ObjectInputStream(new FileInputStream(filePath)); Person readObject = (Person)is.readObject(); }}
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; }}
因为存在数据结构基础,不全记录,只记录觉得写的妙的源码和比较经典的源码。
看了一段就知道,LinkedList的核心问题在注意头指针和尾指针的同时,怎么严密的修改前指针和后指针的问题,看前问自己几个问题,怎么添加(删除)头(尾)结点?怎么插入(删除)中间结点(给你个结点你怎么确定它是中间结点还是头尾结点?)?。
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{ transient int size = 0; transient Node<E> first; transient Node<E> last; //因为类中只记录了first结点和last结点,通过一次二分可以找到目标结点和first结点比较接近还是last结点比较接近 Node<E> node(int index) { if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } } //如果原头结点为空,则让尾指针指向新结点(头尾重合);如果原头结点不为空,那么就让原头结点的前指针指向新的头结点 private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; } //将原尾节点的后指针指向新的尾节点 void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //插入到succ结点之前 void linkBefore(E e, Node<E> succ) { //记录succ的前指针 final Node<E> pred = succ.prev; //pred<-newNode->succ final Node<E> newNode = new Node<>(pred, e, succ); //将prev<-succ修改为newNode<-succ succ.prev = newNode; if (pred == null) //前指针为空,说明succ为头指针,而现在newNode为头指针 first = newNode; else //将pred->succ 修改为 pred->newNode pred.next = newNode; size++; modCount++; } //这也有栈顶?peek出的first头节点。 public E peek() { final Node<E> f = first; return (f == null) ? null : f.item; } //很粗暴的转换数组 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; } }
原文出处:LinkedList源码刨析