精华内容
下载资源
问答
  • 无论是LinkedList,还是ArrayList,毕竟他们都表示线性表,所以API一致,只是具体的实现不同!今天学习一下LInkedList修改元素

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

        无论是LinkedList,还是ArrayList,都实现了List接口,List接口表示作为线性表的能力,所以LinkedList和ArrayList提供的API是一致的,只是ArrayList与LinkedList对于List接口的实现是不同的!今天我们继续学习LInkedList修改元素的源码,一个定义在LinkedList类中的set()方法,另一个是定义在迭代器类ListItr中的set()方法,它们都能完成修改元素工作!

        

     

    set()方法分析

    位于LinkedList中的set()方法,用于替换指定下标的元素,第一个参数index表示元素的索引位置,第二个参数element表示替换后的元素对象

        public E set(int index, E element) {
            checkElementIndex(index);
            Node<E> x = node(index);
            E oldVal = x.item;
            x.item = element;
            return oldVal;
        }

     set()方法本身覆盖的是LinkedList的父类AbstractSequentialList的set()方法,接下来一起分析一下

    1、检查传入下标是否合法

    由checkElementIndex()方法检查下标是否符合范围,在LinkedList中只要是使用传入下标的代码,都会做下标范围的检查,这是其中1处。举个例子:现在LinkedList一共持有5个元素,那么下标index的合法范围是0-4,如果index小于0或者大于4都不符合要求

    2、获取表示结点的对象

    我们向LinedList添加的元素对象,都是由Node对象持有的实例变量item负责保存的,此处通过node()方法获取对应下标的Node对象,目的是为了修改当前Node对象持有的item,修改item指向的对象

    3、提取保存的旧元素对象

    在第二步中已经获取到对应index的Node对象,此时取出此Node对象持有的item,也就是Node对象持有的旧元素对象,由局部变量oldVal负责保存

    4、正式添加新的元素替换掉旧的元素

    只要为Node对象x持有的item赋值为指向新的元素对象即可

    5、返回被替换的元素对象

    return语句直接返回旧的元素对象

     

    set()方法分析(ListItr)

            public void set(E e) {
                if (lastReturned == null)
                    throw new IllegalStateException();
                checkForComodification();
                lastReturned.item = e;
            }

    此set()方法定义在迭代器类ListItr中,重写的是ListIterator接口中定义的方法。此方法只接受传入一个参数,表示即将要替换成的元素对象,我们下面分步学习一下

    1、检查迭代器遍历的元素情况

    lastReturned是ListItr对象持有的一个实例变量,表示最后一次遍历过的元素,理论上lastReturned为null,则说明几个可能,第一个是创建了迭代器还没有使用过迭代器执行过遍历,lastReturned的初始值为null,第二个是使用迭代器添加了一次元素,此时lastReturned也会为null,表示上一次并没有返回元素,第三个是使用迭代器删除了一次元素,此时lastReturned也会为null,同样表示迭代器上一次没有返回元素,而是进行了删除元素的行为。如果你在lastReturned为null的情况下,执行要修改元素,作者会给你提示,一个IllegalStateException()给你……

    2、检查多线程下修改元素

    LinedList不支持多线程下操作元素,这里检查也就是说防止你在多线程下使用LinkedList

    3、通过检查后替换最后一次遍历过的元素对象

    替换最后一次访问过的元素为传入的新元素,完成替换工作

     

     

    总结

    1、node()方法、checkElementIndex()方法都是在LinkedList中多次使用的, 其他篇文章已经介绍,本篇不再提及

    2、迭代器ListItr中的set()方法只能替换最后一次通过迭代器访问过的元素

    3、LinedList中的set()方法,只要指定的元素下标符合要求,即可完成替换操作

    展开全文
  • LinkedList&lt;String&gt; ll = new LinkedList&lt;String&gt;(); ll.add("aaaa"); ll.add("bbbb"); ll.add("cccc"); // ListIterator(列表迭代器)有...
    		LinkedList<String> ll = new LinkedList<String>();
    		ll.add("aaaa");
    		ll.add("bbbb");
    		ll.add("cccc");
    
    		// ListIterator(列表迭代器)有add及previous方法
    		ListIterator<String> it = ll.listIterator();
    		/***
    		 * 在 “bbbb” 后面插入 “xxxx”
    		 */
    		while(it.hasNext()) {
    			String item = it.next();
    			if("bbbb".equals(item)) {
    				it.add("xxxx");
    			}
    		}
    		System.out.println(ll); // 输出结果: [aaaa, bbbb, xxxx, cccc]
    		
    		
    		/***
    		 * 在 “bbbb” 修改为 “BBBB”
    		 */
    		it = ll.listIterator();
    		while(it.hasNext()) {
    			String item = it.next();
    			if("bbbb".equals(item)) {
    				it.set("BBBB");
    			}
    		}
    		System.out.println(ll); // 输出结果: [aaaa, BBBB, xxxx, cccc]
    	

     

    展开全文
  • LinkedList

    2019-12-10 21:38:15
    2.支持null元素元素可以重复; 3.可以被当作堆栈、队列或双端队列进行操作。 4.实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。 5.LinkedList包含两个重要的成员:header 和 ...

    LinkedList

    特点:
    1.非同步,线程不安全;
    2.支持null元素,元素可以重复;
    3.可以被当作堆栈、队列或双端队列进行操作。
    4.实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
    5.LinkedList包含两个重要的成员:header 和 size。

    LinkedList也实现了List接口,相对于ArrayList来说,它们的最大区别在于底层数据结构不同,LinkedList的底层是一个双向链表,这也决定了它的最大优点,那就是对于数据的修改比ArrayList更加方便快捷。
    相对于ArrayList,LinkedList插入是更快的。因为LinkedList不需要改变数组的大小,也不需要在数组装满的时候要将所有的数据重新装入一个新的数组,类似于插入数据,删除数据时,LinkedList也优于ArrayList,其时间复杂度仅为O(1),而ArrayList删除数据是开销很大的,因为这需要重排数组中的所有数据(除了最后一个元素)。
    常用方法:

    方法名 说明
    addFirst(Object o) 在列表首部添加元素
    addLast(Object o) 在列表尾部添加元素
    Object getFirst() 返回列表的第一个元素
    Object getLast() 返回列表最后一个元素
    Object removeFirst() 删除并返回列表第一个元素
    Object removeLat() 删除并返回列表最后一个元素
    add(Object o) 增加元素
    remove(Object o) 按照元素删除元素
    展开全文
  • 上一篇文章我们说了LinkedList,并说了往里添加了元素。这篇文章我们来说说LinkedList元素的删除,话不多说,上代码,还是那个Person类 还是那两个属性,name,age,提供了一些简单的get与set方法。写我们的main...

    上一篇文章我们说了LinkedList,并说了往里添加了元素。这篇文章我们来说说LinkedList元素的删除,话不多说,上代码,还是那个Person类

    还是那两个属性,name,age,提供了一些简单的get与set方法。写我们的main方法

    和前文一样,new了一个LinkedList,并往里添加了四个元素,看过前文的朋友都知道现在LinkedList目前在堆内存中的样子如下图:

    现在我们来删除王五这个用户,运行一下

    看一下结果

    好奇怪,打印返回的删除状态居然是false,代码中明明删掉王五了,为什么打印的结果还是4?如果经常看本专栏文章的人,大概已经猜到了原因,这个王五是新new出来的,并不是perList里的王五,Person这个类没有重写equals方法,删除元素依赖于equals方法,到底是不是呢,我们来看一下源码:

    不出所料,又看到了熟悉的equals,真是无处不在,这段代码其实是从第一个Node节点(first节点)开始对比item的值,如果equals成功就执行unlink()方法,并返回删除成功的布尔值true。我们画一画查找王五的这个过程。

    大致就是这个样子,就大家仔细看图里的文字描述,现在我们来看看unlink()方法都做了啥

    preview

     

    注意,在本示例中,上图的黑色字体注释部分不会执行。好吧,我承认,多年前我看这段代码被绕晕了,prev.next,next.prev都是些什么鬼啊!苍天啊!大地啊!

    别怕,上面代码看似烧脑但是逻辑相当简单,就是把包含王五的这个Node从双向链表中移出来,然后把王五相邻的两个Node的next和prev重新指向一下,我们画一下图:

    简单吧,debug一下看是不是和图中画的一致,测试代码前别忘了在Person里重写equals方法

    debug看一下,已经删除了王五,size也更新成了3。

    打印结果也和期待中一样,打印删除状态也为true了。

    说到这儿,我们再来看一下ArrayList以对象方式删除元素的源码,来和LinkedList比较一下

    再看fastRemove()方法

    大体上一致,两者都在元素中循环查找,LinkedList是把Node(包含Person)从链表的移出(通过修改上下节点的引用来实现),ArrayList删除底层数组元素后又把底层数组都往前复制了一格内容(忘记了的朋友可以复习一下,传送门:ArrayList的元素删除),现在我们来比较一下这两者间的时间复杂度。

    假设要删除的元素都在这两个List中的第n位置,由于两者都循环查找了n次,省略循环查找这个步骤,说以我们直接看删除,前面的一系列文章中我们已经讲过了,由于ArrayList删除元素后,底层数组要往前复制一格,ArrayList底层数组删除元素时间复杂度为O(n)。再来看LinkedList,LinkedList底层链表删除元素只是简单的修改了一下引用地址,时间复杂度为O(1)。

    由以上推断看来,LinkedList的删除效率似乎要好很多,实际真的如此吗?答案是不一定。下一篇文章我们将写一段代码来分析一下,LinkedList和ArrayList在删除元素时的真实效率。

    以上我们说的删除用的是List的如下API

    public boolean remove(Object o);

    LinkedList还有一种删除方式,用下标方式删除,如下

    public E remove(int index);

    下一篇文章一起讲解。

    注:示例中,用对象的方式来删除元素,只是想告诉大家,这种删除方式是用equals方法来查找元素进而删除的,实际工作中很少遇到需要new一个对象去删除的情况。不建议一上来就重写equals方法,除非你有特殊的需求。如果重写了equals方法,请一并重写hashCode方法,这个问题在说说Java里的equals(中)一文中已经说过了。

    转载无限欢迎,但请注明「清浅池塘」和「https://zhuanlan.zhihu.com/p/28373321」。转载请在文中保留此段,感谢您对作者版权的尊重。如需商业转载或刊登,请联系作者获得授权。自助转载请点击:https://www.rightknights.com/materi

    展开全文
  • linkedlist

    2016-09-08 15:26:00
    一、概述 LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现。... LinkedList实现所有可选的列表操作,并允许所有的元素包括null...
  • java.util.LinkedList 本文的结构: 一、LinkedList的特点及与ArrayList的比较 二、LinkedList的内部实现 ...六、LinkedList修改元素 七、Java8中的改动 一、LinkedList的特点及与ArrayList的比较 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 58,955
精华内容 23,582
关键字:

linkedlist更改元素