欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java之LinkedList源码分析(第三篇:添加元素-List接口)

程序员文章站 2022-05-23 12:02:05
LinkedList的添加方法太多了……,先从List系列开始0、一个参数,接受一个参数类型E的参数 public boolean add(E e) { linkLast(e); return true; }传入的元素对象e,直接被传入到linkLast方法中(见1号知识点),不过最后的返回值一定是true哦……添加元素没失败的......

(注意:本文源码基于JDK1.8) 

Java之LinkedList源码分析(第三篇:添加元素-List接口)

LinkedList添加元素的方法太多了……,本篇从List接口中定义的添加元素方法做一个分析

 

传入一个参数类型E的add()方法分析

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

add(E)方法是LinekdList中最常用的添加元素的方法

1、将传入的元素对象e,再传入到实际进行添加元素的方法中

实际调用linkLast()方法,将元素插入,元素会插入到双向链表的尾部

2、返回值为true,表示LinkedList添加一个元素成功

 

linkLast()方法分析

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

实际向双向链表尾部添加一个元素的方法,无返回值,传入的参数e表示要添加的元素对象

1、保存当前双向链表的最后一个元素到局部变量中

首先将LinkedList对象持有的实例变量last,赋值给局部变量l保存,last指向的是双向链表的最后一个结点对象(结点对象中持有的元素)

2、创建一个Node对象,用于持有传入的元素对象e,并赋值给一个局部变量保存

通过new创建一个Node对象,Node的构造方法需传入3个参数,局部变量l表示的尾节点、元素对象e、以及一个null值,新创建的Node对象会赋值给一个局部变量newNode负责保存

PS:局部变量l与局部变量newNode都用final修饰,这是为何?

3、更新双向链表的尾节点为新创建的Node对象

将实例变量last指向新创建的结点对象newNode,此时新创建的结点对象成为双向链表的最后一个结点

4、处理第一次添加元素的情况

如果LinkedList是第一次添加元素,将新创建的结点对象newNode赋值给LinkedList对象持有的first,实例变量first永远指向双向链表的第一个结点对象

如果LinkedList不是第一次添加元素,则将临时保存的旧的尾结点对象l持有的实例变量next指向新添加的结点对象newNode,完成双向链表之间连接

5、更新LinkedList持有的元素总数

添加完新的结点对象,再将LinkedList持有的元素总数size值,增加1

6、fail-fast机制更新值,防止多线程下使用LinkedList

再把fail-fast机制用的modCount值增加1

 

Node构造方法分析

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

Node类定义在LinkedList的内部,为静态内部类,它产生的每个对象表示作为双向链表的节点对象,Node的构造方法需传入3个参数

第一个参数prev表示当前Node对象连接的上一个Node对象,第二个参数element表示当前Node持有的元素对象,第三个参数next表示当前Node对象连接(指向)的下一个Node对象

1、首先为Node对象持有的item赋值

Node对象持有的item负责保存传入的元素对象element

2、为Node对象持有的next赋值

Node对象持有的next,表示连接(指向)的下一个Node对象,这里直接将传入的next赋值给实例变量next

3、为Node对象持有的prev赋值

Node对象持有的prev表示连接(指向)的上一个Node对象,同样直接将传入的prev赋值给实例变量prev

 

 

传入两个参数的add()方法分析

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

用于在指定位置插入元素的方法(注意:第一个位置的下标是0)

第一个参数index表示下标,第二个参数element表示插入的元素对象

1、检查下标值是否合法

首先检查下标值是否超出范围,将传入的下标index传入到checkPositionIndex()方法中,只有符合下标要求的元素才能插入到LinkedList中

2、判断是否在双向链表尾部插入元素

符合范围的下标值,会检查元素是否为插入到双向链表的尾部,这里将下标index与元素总数size作比较,如果index与size相等则说明是要插入到双向链表的尾部,所以此时会调用linkLast()方法完成在尾部插入元素

3、在双向链表的中间部分插入元素

如果元素不是插入到尾部,那一定是插入到中间的元素,此时先将下标index传入到node()方法中,node()方法会返回一个指定下标index的前面或者后面的一个已经存在的Node对象,最后再将即将要插入的元素对象element与node()方法返回的Node对象,作为参数一并传入到linkBefore()方法中,由linkBefore方法完成最终的插入

 

checkPositionIndex()方法分析

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

用于检查下标index是否在有效范围内的方法

1、将传入的下标index传入到isPositionIndex()方法中

2、不符合要求抛出异常告知用户

isPositionIndex()方法的返回值若返回flase,则代表传入的下标index并不在有效的范围内,此时整个方法抛出IndexOutOfBoundsException对象,IndexOutOfBoundsException对象接受了一个outOfBoundsMsg()方法返回的字符串!

 

isPositionIndex()方法分析

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

用于检查传入的下标index是否符合范围

必须同时满足两个条件,才能作为LinkedList中有效范围内的下标

1、下标index必须大于等于0

2、下标index必须小于等于元素总数size

返回值true表示下标符合范围,false表示不符合范围……

 

node(int)方法

    Node<E> node(int index) {
        // assert isElementIndex(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;
        }
    }

用于返回指定下标index的前面或者后面的Node对象,返回的Node对象取决于下标值更接近双向链表的头部还是尾部

按照下标index距离头结点或尾结点哪个更近,所以分出了两种情况

1、传入下标index若小于元素总数size的一半,证明index距离第一个结点更近,此时从第一个结点开始查找要插入的位置的后一个结点

将LinkedList对象持有的头结点引用first赋值给局部变量x,接着开始遍历找到符合要求的结点,比如要新插入一个元素到index等于3的位置,此时x返回的是当前index为3的结点对象(它会作为新插入结点对象的下一个结点对象而存在)

2、传入下标index若大于等于元素总数size的一半,证明index距离最后一个结点更近,此时从最后一个结点开始查找要插入的位置的后一个结点

先获得LinkedList对象持有的last并赋值给局部变量x,last总是指向双向链表的最后一个结点,接着从最后一个结点开始向前进行遍历,找到符合要求的结点,返回的x也是当前位置index的结点对象(它同样也是作为新插入结点对象的下一个结点对象而存在的)

 

linkBefore()方法分析

    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

用于将一个新的结点对象插入到某一个结点对象的前面,传入的局部变量e代表插入的元素对象,传入的局部变量succ代表新插入结点对象连接(指向)的下一个结点对象

1、首先将传入的结点对象succ持有的prev赋值给局部变量pred(局部变量pred连接(指向)的结点将会成为新插入结点对象连接(指向)的上一个结点)

2、接着会创建一个新的结点对象,这是通过Node的构造方法完成的(见2号知识点),它接受三个参数,第一个是它指向的上一个结点对象、第二个是要插入的元素对象,第三个是它指向的下一个结点对象,最终新创建的对象会被赋值给局部变量newNode负责持有

3、将结点对象succ持有的prev连接(指向)新插入的结点对象newNode(succ结点是新插入结点对象连接(指向)的下一个结点)

4、如果新插入的是第一个结点,则将first连接(指向)到结点对象newNode

5、不是第一个结点对象的话,将结点对象pred的next连接(指向)到新插入的结点对象newNode

最后元素总数size加1,modCount增加1,代表结点的插入已经完成

 

outOfBoundsMsg()方法分析

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

负责返回异常字符串的方法,它会将传入的下标index与其他字符串共同组成一个新的字符串,我们看到的异常信息,就是这个方法返回的字符串

 

addAll(Collection)方法分析

    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

负责将集合中的所有元素添加到LinkedList对象持有的双向链表中,传入的Collection对象c会被传入到addAll方法中

 

addAll(int,Collection)方法分析

   public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(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;
        }

        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

1、首先检查下标的范围是否合法

将下标index传入到checkPositionIndex()方法中

2、将Collection对象转为一个数组对象,并由局部变量a负责持有

3、获取数组对象a的长度,由局部变量numNew负责持有

4、传入的数组对象长度为0时,会直接返回false

5、定义两个局部变量,一个pred、一个succ、它们都是Node类型,pred代表新插入结点对象连接(指向)的上一个结点,succ代表新插入结点对象连接(指向)的下一个结点

6、index==size时,代表元素插入到双向链表的尾部,此时succ赋值为null,pred则为last

7、不是向尾部插入时,则通过node方法()得到一个新插入结点未来连接(指向)的下一个结点对象,赋值给succ保管,接着从succ取出上一个结点,赋值给pred保存(这里只是插入多个元素,你可以把它们假装看成是一个元素)

8、接着对集合中所有元素进行遍历的连接,每个元素都会创建为一个Node对象,直到最后一个元素,此时它会成为pred

9、接着判断两种情况,一个是在尾部插入元素的情况,一个是在中间插入元素的情况,把LinkedList持有的最后一个结点更新上来

10、更新LinkedList的元素总数size

11、更新用于fail-fast机制modCount值

12、返回一个true,表示插入元素成功

 

总结

linkLast()方法中的局部变量l与局部变量newNode都用了final修饰,这是为何?

本文地址:https://blog.csdn.net/cadi2011/article/details/105084700

相关标签: Java LinkedList