LinkedList源码

布满荆棘的人生 2022-02-28 03:33 329阅读 0赞

LinkedList底层是基于双向链表，链表在内存中不是连续的，而是通过引用来关联所有的元素，所以链表的优点在于添加和删除元素比较快，因为只是移动指针，并且不需要判断是否需要扩容，缺点是查询和遍历效率比较低。

LinkedList是列表，双端队列，堆栈，  
列表的那些方法，都是当成单向链表使用，队尾添加，队首删除  
初始状态，空链表，first=last=null  
添加一个元素后，first=last=Node1  
2个元素后，first=Node1，last=Node2

## 类结构 ##

**
     *LinkedList底层是双链表。
     *实现了List接口可以有队列操作
     *实现了Deque接口可以有双端队列操作
     *实现了所有可选的List操作并且允许存储任何元素，包括Null
     
     *所有的操作都提现了双链表的结构.
     *索引进入List的操作将从开始或者结尾遍历List，无论任何一个指定的索引
     *
     *注意：这些实现(linkedList)不是同步的，意味着线程不安全
     *如果有多个线程同时访问双链表，至少有一个线程在结构上修改list，那么就必须在外部加上同步操作(synchronized)(所谓的结构化修改
     *操作是指增加或者修改一个或者多个元素，重新设置元素的值不是结构化修改)，通常通过自然地同步一些对象来封装List来完成
     *
     *如果没有这样的对象存在，那么应该使用Collections.synchronizedList来封装链表。
     *最好是在创建是完成，以访问意外的对链表进行非同步的访问。
     *如：List list = Collections.synchronizedList(new LinkedList(...));
     *
     *此类的迭代器和迭代方法返回的迭代器是快速失败的：如果链表在迭代器被创建后的任何时间被结构化修改，除非是通过remove或者add方法操作的，
     *否则将会抛出ConcurrentModificationException异常，因此，面对高并发的修改，迭代器以后快速而干净的失败以防承担
     *冒着未确定的任意，非确定性行为的风险
     *
     *注意：迭代器快速失败的行为不能保证，一般来说，在存在并发修改的情况下不能确保任何的承诺，失败快速的迭代器
     *尽最大努力抛出ConcurrentModificationException异常，因此，编写一个依赖于此的程序是错误的。
     *正确性异常：迭代器的快速失败行为应该只用于检测错误
     *
     * @author cb
     *
     * @param <E>
     */
    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;
     
    /**
     * 空构造器
     */
    public LinkedList() {
    }
     
    /**
     *传入集合参数的构造器
     */
    public LinkedList(Collection<? extends E> c) {
        this();//调用当前类的构造函数
        addAll(c);
    }

## 常用方法 ##

/**
     *在链表的尾端追加指定集合的所有元素，按指定的迭代器的集合顺序返回，在这个操作执行总是如果指定的集合被修改了
     *，那么该行为操作将提示未定义
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    public boolean addAll(int index, Collection<? extends E> c) {
    	/**
    	 * 检查index是否越界，index=size+1
    	 */
        checkPositionIndex(index);
        /**
         * 将集合参数转化为数组
         */
        Object[] a = c.toArray();
        int numNew = a.length;//要插入的集合长度
        if (numNew == 0)
            return false;
        /**
         * 定义pred和succ两个Node对象，用于标识要插入元素的前置节点和后置节点
         */
        Node<E> pred, succ;
        /**
         * 这里为什么要写if..else？
         * 因为该方法不一定是从上层方法addAll(size, c)过来的，还有可能是直接调用了addAll(int index, Collection<? extends E> c)
         * 方法，从上层addAll(size, c)跳转过来的，size=index也就从尾部插入，但是直接调用的该方法，则从传进来的参数index这个位置（肯能是任何位置）插入
         */
        if (index == size) {//表明是从尾部插入
            succ = null;//从尾部插入，后置节点为null
            pred = last;//从尾部插入，前置节点为当前LinkedList中的最后一个节点
        } else {//表明不是从尾部插入
            succ = node(index);//查到当前LinkedList中位置为index的节点并把它赋给要插入元素的后置节点
            pred = succ.prev;//把上一步得到的节点的前置节点赋值给要插入元素的后置节点
        }
     
        for (Object o : a) {//变量集合参数
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)//说明插入之前当前链表是空链表
                first = newNode;//新节点是第一个节点
            else
                pred.next = newNode;//设置插入元素的的前置节点的后置节点为新节点
            pred = newNode;//更改指向后将新节点对象赋给pred作为下次循环中新插入节点的前一个对象节点，依次循环
        }
      //此时pred代表集合元素的插入完后的最后一个节点对象
        if (succ == null) {//结尾添加的话在添加完集合元素后将最后一个集合的节点对象pred作为last
            last = pred;
        } else {
            pred.next = succ;//将集合元素的最后一个节点对象的next指针指向原index位置上的Node对象
            succ.prev = pred;//将原index位置上的pred指针对象指向集合的最后一个对象
        }
     
        size += numNew;
        modCount++;
        return true;
    }
    /**
     * Returns the (non-null) Node at the specified element index.
     * 返回index位置的非空节点
     * 折半查询 
     */
    Node<E> node(int index) {
        /**
         * 如果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;
        }
    }

node（int index）:这个方法的主要功能是找到index位置的Node节点，源码上利用折半查询进行优化，即使这样，遍历和查询效率还是比较差。

add方法

public boolean add(E e) {
        linkLast(e);
        return true;
    }
    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++;
    }

remove方法  
移除方法主要有两个：

根据元素移除

/**
     *从第一个节点循环指针查找
     */
    public boolean remove(Object o) {
        //如果移除的数据为Null
        if (o == null) {
            //遍历找到第一个为null的节点，然后移除掉
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
        //遍历找到第一条不为null与参数相等的数据，然后移除掉
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
     
    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;
        
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }
     
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
     
        x.item = null;
        size--;
        modCount++;
        return element;
    }

根据索引移除

public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

get方法  
get系方法有三个：分别是get(index),getFirst(),getLast(),

public E get(int index) {
        checkElementIndex(index);//检查是否越界
        return node(index).item;//折半查询节点，然后获取该节点的值
    }
    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;
    }

set方法

public E set(int index, E element) {
        checkElementIndex(index);//检查是否越界
        Node<E> x = node(index);//折半查询索引为index的节点
        E oldVal = x.item;//查询index节点原来的数据值
        x.item = element;//将新值插入
        return oldVal;//返回旧值
    }

clear方法

public void clear() {
        //遍历所以的数据，置为null,方便垃圾回收
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

toArray方法

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;
    }