LinkedList源码分析

集合继承结构总揽

构造方法

`linkedList(Collection c)` 批量添加集合内容到linkedList的构造方法`linkedList()`无参构造方法 ](https://www.yuque.com/docs/share/86676521-3769-466c-8871-d38fc35f23f0?#%20%E3%80%8AlinkedList%E3%80%8B)继承自Iterable的方法

Iterator iterator() 获取迭代器 继承自Collection的方法

`add(E element)` 在集合尾部插入元素,几乎等价于linkLast(E element)`addAll(Collection c)` 批量添加集合元素到当前集合中`contains(Object o)` 判断集合是否包含某个元素 继承自List的方法

`set(int index, E element)` 修改元素值,同时返回原先存储的Node节点元素值`add(int index, E element)` 查找并且插入相应的元素值`addAll(int index, Collection c)` 批量添加集合元素到制定下标之后当前集合中(重载)`indexOf(Object o)` 获取某个元素在集合结构中的下标`listIterator()` 获取List类型的可迭代对象`listIterator(final int index)` 获取集合中某个下标值之后的List类型的可迭代对象`get(int index)` 获取当前集合中某个下标节点存储的值`remove(int index)` 删除当前集合中某个下标节点存储的值 继承自Queque的方法

`poll()` 获取并且删除集合的第一个元素`offer(E e)` 在集合尾部插入元素 继承自Deque的方法

`descendingIterator()` 获取一个可以逆序迭代的迭代器`addFirst(E element)` 在集合头部插入元素`addLast(E element)` 在集合尾部插入元素`pollFirst()` 获取并且删除集合的第一个元素`pollLast()` 获取并且删除集合的最后一个元素`peekFirst()` 获取集合的第一个元素`peekLast()` 获取集合的最后一个元素`offerFirst(E e)` 在集合头部插入元素`offerLast(E e)` 在集合尾部插入元素 其他私有方法(下标范围判断)

`checkPositionIndex(int index)` 确认当前传入的下标是否为可迭代的，否则抛出异常`isPositionIndex(int index)` 判断当前传入的下标是否为可迭代的`checkElementIndex(int index)` 确认当前传入的下标是否为越界，否则抛出异常`isElementIndex(int index)` 判断当前传入的下标是否为越界 其他私有方法(元素遍历)

`node(int index)` 根据下标来迭代获取响应的元素 其他私有方法(元素增删)

`linkFirst(E element)` 在集合头部插入元素`linkLast(E element)` 在集合尾部插入元素`linkBefore(E e, Node succ)` 在集合某个Node节点之前插入元素`unlinkFirst(E element)` 删除集合头结点`unlinkLast(Node l)` 删除集合尾节点`unlink(Node x)` 在集合中某个Node节点的值

兼具List的有序性和Deque的队列的特性,这个集合平常项目中使用的比较少,接着刷题的机会了解到这个数据集合,趁机来深度学习下源码知识，希望对大家可以有所帮助

public class linkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable{
    
    //集合size属性
    transient int size = 0;

    
    transient Node first;

    
    transient Node last;
    
    
    protected transient int modCount = 0;
    
    
    private static class Node {
        //Node节点中存储的元素值
        E item;
        
        //下一个Node节点
        Node next;
        //上一个Node节点
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

}

public linkedList(Collection c) {
   this();
   addAll(c);
}

//无参构造方法,初始化集合对象,此时初始化以后的是一个空的集合size=0

public linkedList() {
}

public Iterator iterator() {
    //调用List子集实现的方法
    return listIterator();
}

//默认在链表尾部插入数据

public boolean add(E element) {
    linkLast(e);
    return true;
}

public boolean addAll(Collection c) {
    //默认将元素添加到当前集合的末尾,调用addALL方法时index参数设置为当前集合的size属性
    //调用List子集实现的方法
    return addAll(size, c);
}

public boolean contains(Object o) {
    //调用List子集实现的方法
    return indexOf(o) != -1;
}

//使用无参构造方法实例化linkedList后立即调用set(int index, E element)或者操作会抛出下标越界的异常IndexOutOfBoundsException,这时通不过checkPositionIndex方法的校验,因为Node节点first和last都还未实例化

//该方法不改变集合结构,不对修改集合长度。设置前提是当前Node节点已经存在,
public E set(int index, E element) {
    //判断下标是否越界
    checkElementIndex(index);
    
    //循环遍历获取到响应的Node节点
    Node x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

//使用无参构造方法实例化linkedList后立即调用add(int index, E element)操作会抛出下标越界的异常IndexOutOfBoundsException,这时通不过checkPositionIndex方法的校验,因为Node节点first和last都还未实例化

public E add(int index, E element) {
    checkPositionIndex(index);
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

public boolean addAll(int index, Collection c) {
    checkPositionIndex(index);
    
    //Collection的子集都必须实现的方法toArray()
    Object[] a = c.toArray();
    //待添加集合的长度
    int numNew = a.length;
    //待添加集合为空,方法终止 
    if (numNew == 0)
        return false;
 
    //定义当前待插入数据的最前置Node节点pred
    //和
    Node pred, succ;
    
    //将目标集合的元素插入到当前集合尾部
    if (index == size) {
        succ = null;
        //最前置节点Node当于当前集合的last,完成两个集合的头尾衔接
        pred = last;
    } else {
        //将目标集合的元素插入到本集合中间的某个特定下标的位置
        
        //获取当前index的Node节点,并将其赋值给succ
        succ = node(index);
        //替换当前下标值对应节点以及其之后的位置(连它一起往后,再此之前开始插入值),将当前Node.prev设置为待添加集合的pred节点
        pred = succ.prev;
    }
 
    //循环赋值
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node newNode = new Node<>(pred, e, null);
        
        if (pred == null)
            //pred为空则表示原先的集合为空,直接将新建的Node设置为头节点
            first = newNode;
        else
            //再pred的尾部插入新建的节点
            pred.next = newNode;
        //把新加入的节点赋值给pred,后续的新增节点可以继续通过循环往后追加值
        pred = newNode;
    }
 
    if (succ == null) {
        //根据传入index找不到数据,直接将循环以后最后一个待插入元素赋值给当前集合的last
        last = pred;
    } else {
        //把待插入集合最后一个元素的next和原始集合下标为index的节点串起来,双向链表接通
        pred.next = succ;
        succ.prev = pred;
    }
 
    size += numNew;
    modCount++;
    return true;
} 

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        //待判断元素为null,从first开始通过链表往后顺序到第一个空元素并且返回下标
        for (Node x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        //如果待判断元素非空,从first开始通过链表往后顺序查找,挨个判断是否与其相等
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

public ListIterator listIterator() {
    return listIterator(0);
}

    public ListIterator listIterator(final int index) {
        //这部分代码实现在其父类AbstractSequentialList的父类AbstractList中有做相关的实现
        rangeCheckForAdd(index);
        return new ListItr(index);
    }

public E get(int index) {
    //判断下标是否越界
    checkElementIndex(index);
    //通过node方法遍历找到传入index对应的Node,并且获取其item值
    return node(index).item;
}

public E remove(int index) {
    //判断下标是否越界
    checkElementIndex(index);
    //通过node方法遍历找到传入index对应的Node,然后通过unlink方法删除元素值
    return unlink(node(index));
}

//实现上和pollFirst()一模一样
public E poll() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public boolean offer(E e) {
    return add(e);
}

​

_

public Iterator descendingIterator() {
    return new DescendingIterator();
}


private class DescendingIterator implements Iterator {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

public void addFirst(E e) {
    linkFirst(e);
}

public void addLast(E e) {
    linkLast(e);
}

public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}

public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}

public E peekFirst() {
    final Node f = first;
    return (f == null) ? null : f.item;
}

public E peekLast() {
    final Node l = last;
    return (l == null) ? null : l.item;
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

public boolean offerLast(E e) {
    addLast(e);
    return true;
}

private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

判断当前传入的下表是否为可迭代的, 可选范围是0<= index <= size 在链表的迭代器(Iterator)里,双向Queue(Deque)中可以正向、反向的迭代,所以index的可选范围对比数组是要大一点

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

Node node(int index) {
    //这一步判断目前都
    // assert isElementIndex(index);
    
    //size >> 1 在未超出数据类型限制的情况下,右移1尾效果等价于/2
    //因为linkedList实现的是Deque(双向队列)
    //  因此如果 index < size/2 时考虑从头fisrt开始正序遍历
    //  因此如果 index >= size/2 时考虑从头last开始反序遍历
    if (index < (size >> 1)) {
        Node x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

private void linkFirst(E e) {
    final Node f = first;
    final Node 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 l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

void linkBefore(E e, Node succ) {
    // assert succ != null;
    //待插入集合的头指向相应Node节点
    final Node pred = succ.prev;
    //创建待插入节点
    final Node newNode = new Node<>(pred, e, succ);
    //相应节点succ的双向链补全指向待插入节点
    succ.prev = newNode;
    if (pred == null)
        //如果相应节点为空,则将待插入元素设置成集合的头节点,如果原先集合有内容,这一顿操作就会造成链表断裂
        first = newNode;
    else
        //双向链表闭环,将当前节点succ的前置节点的next设置为新插入的节点
        pred.next = newNode;
    size++;
    modCount++;
}

//该方法仅有两处被调用的地方,分别是pollFirst()和poll(),都是需要拿到集合的头节点并且删除头节点的操作
private E unlinkFirst(Node f) {
    // assert f == first && f != null;
    //获取当前待删除Node存储的数据值,用于完成方法后返回
    final E element = f.item;
    //获取到当前待删除Node的下一个节点,用于替换当前节点
    final Node next = f.next;
    //清理当前Node的相关信息,等待GC回收
    f.item = null;
    f.next = null; // help GC
    //将当前待删除Node的下一个节点赋值给集合的first节点
    first = next;
    if (next == null)
        //nextNode为空标志当前集合为空,上面删除的是集合中的唯一元素
        last = null;
    else
        //集合不为空时,将集合的头节点的prev斩断,如果不执行这一步,头节点的prev还是指向待删除的但是内容已经清空的这个节点
        //个人觉得这里的代码写成first.prev=null可读性会更好
        next.prev = null;
    size--;
    modCount++;
    return element;
}

//代码逻辑和unlinkFirst类似,只是需要逆向处理
private E unlinkLast(Node l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

//简单的说就是剪短旧链 让x.pref.next=x.next  x.next.pref=x.pref
E unlink(Node x) {
    // assert x != null;
    final E element = x.item;
    final Node next = x.next;
    final Node 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;
}