LinkedList源码刨析

AI助手支持GPT4.0

数组和结点这两种数据结构之间的差异，决定了LinkedList相比ArrayList拥有更高的插入和删除效率，而随机访问效率不如ArrayList。

目录

• transient
• Externalizable
• LinkedList源码刨析
  • Node
  • LinkedList

transient

transient只能用来修饰成员变量（field），被transient修饰的成员变量不参与序列化过程。

序列化: JVM中的Java对象转化为字节序列。

反序列化: 字节序列转化为JVM中的Java对象。

静态成员变量即使不加transient关键字也无法被序列化。

Externalizable

自定义序列化，无视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();    }}

LinkedList源码刨析

Node

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

因为存在数据结构基础，不全记录，只记录觉得写的妙的源码和比较经典的源码。

看了一段就知道，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;    }        }