精华内容
下载资源
问答
  • 比如现在给数字3要求删除,再删除6,然后给3要求按顺序插入,不要给按顺序直接删除的答案,而是查找到后再删除 import java.util.*; class s{ public int i; s(int s){i=s; } } public class display { ...
  • LinkedList,是基于链表实现,由双向链条next、prev,把数据节点穿插起来,所以在插入数据时,是不需要ArrayList那样扩容数组。 二、源码分析 1.初始化 与ArrayList不同,LinkedList初始化不需要创

    分别是:10万、100万、1000万的数据在两种集合下面不同位置的插入效果!

    1. ArrayList 中间插入快。
    2. LinkedList 头插、尾插快。

    一、数据结构

    Linked + List = 链表 + 列表 = LinkedList = 链表列表

    LinkedList,是基于链表实现,由双向链条next、prev,把数据节点穿插起来,所以在插入数据时,是不需要ArrayList那样扩容数组。

    二、源码分析

    1.初始化

    与ArrayList不同,LinkedList初始化不需要创建数组,因为它是一个链表结构,而且没有传给构造函数初始化多少个空间的入参,如下:

    但是,构造函数一样提供了和ArrayList一些相同的方法,来初始化入参,入下:

    @Test
    public void test_init() {
        LinkedList<String> list01 = new LinkedList<String>();
        list01.add("a");
        list01.add("b");
        list01.add("c");
        System.out.println(list01);
    
        LinkedList<String> list02 = new LinkedList<String>(Arrays.asList("a", "b", "c"));
        System.out.println(list02);
    
        LinkedList<String> list03 = new LinkedList<String>(){
            {add("a");add("b");add("c");}
        };
        System.out.println(list03);
    
        LinkedList<Integer> list04 = new LinkedList<Integer>(Collections.nCopies(10, 0));
        System.out.println(list04);
    }

     

    [a, b, c] 
    [a, b, c] 
    [a, b, c] 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]  
    Process finished with exit code 0

    2.插入

    LinkedList的插入方法比较多,List中接口中默认提供的是add,也可以指定位置插入。

    但在LinkedList中还提供了头插addFirst和尾插addLast

    2.1头插

    ArrayList的插入和LinkedList插入对比,如下:

    1.ArrayList头插时,需要把数组元素通过Arrays.copyOf的方式把数组元素移位,如果容量不足需要扩容。
    2.LinkedList头插时,不需要考虑移位、以及扩容的问题,直接把元素定位到首位,接点链条就可以了。

    2.1.1 源码

    对照LinkedList源码

    1. first,首节点会一直被记录,这样就非常方便头插。
    2. 插入时候会创建新的节点元素,new Node<>(null, e,f),紧接着把新的头元素赋值给first。
    3. 之后判断f节点是否存在,不存在则把头节点作为最后一个节点,存在则用f节点的上一个链条prev链接。
    4. 最后记录size大小、和元素数量modCount。modCount用在便利时做校验,modCount!=expectedModCount.
    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++;
    }

    2.1.2验证

    ArrayList、LinkeList,头插源码验证

    @Test
    public void test_ArrayList_addFirst() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.add(0, i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }
    @Test
    public void test_LinkedList_addFirst() {
        LinkedList<Integer> list = new LinkedList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.addFirst(i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    比对结果:

    10万、100万、1000万的数据量,在头插时的消耗情况。
    1.ArrayList需要做大量的位移和复制操作,而LinkedList的优势就体现出来了,耗时只是实例化的一个对象。

    2.2尾插

    ArrayList的插入与LinkedList插入对比

    1.ArrayList尾插时,是不需要数据位移,比较耗时的是数据扩容时候,需要数据拷贝迁移。
    2.LinkedList尾插时,与头插相比耗时点会在对象的实例化上面

    2.2.1源码

    对照一下LinkedList的尾插源码,如下:

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

    1.头插代码相比几乎没有什么区别,只是first换成last
    2.耗时点知识在创建节点上,Node<E>

    2.2.2验证

    ArrayList、LinkedList,尾插源码验证

    @Test
    public void test_ArrayList_addLast() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.add(i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }
    @Test
    public void test_LinkedList_addLast() {
        LinkedList<Integer> list = new LinkedList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.addLast(i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    比对结果:

    10万、100万、1000万的数据量,在尾插时的一个耗时情况。
    1.ArrayList不需要做位移拷贝也就不会特别耗时,而LinedList则需要创建大量的对象,所以这边ArrayList尾插效果更好

    2.3中间插入

    结构比对图,ArrayList和LinkedList 插入做下对比,如下:

    1.ArrayList中间插入,首先我们知道它的定位时间复杂度是O(1),比较耗时的点在于数据迁移和容量不足的时候扩容。
    2.LinkedList中间插入,链表的数据实际插入时候并不会怎么耗时,但是它定位的元素的时间复杂度但是O(n),所以这部分比较耗时

    2.3.1源码

    看LinkedList指定位置的插入源码

    使用add(位置、元素)方法插入

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

    位置定位node(index):

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

    size >> 1,这部分代码判断元素位置在左半区间,还是右半区间,在进行循环查找

    执行插入:

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

    1.找到指定位置插入的过程就比较简单了,与头插、尾插,相插不大。
    2.整个过程可以看到,插入中比较耗时的点会在便利寻找插入的位置上。

    2.3.2验证

    ArrayList、LinkeList,中间插入源码验证

    @Test
    public void test_ArrayList_addCenter() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 10000000; i++) {
            list.add(list.size() >> 1, i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }
    @Test
    public void test_LinkedList_addCenter() {
        LinkedList<Integer> list = new LinkedList<Integer>();
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            list.add(list.size() >> 1, i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    比对结果:

    10万、100万、1000万的数据量,在中间插入的一个耗时情况。
    1.LinkedList在中间插入时,遍历寻找位置还是非常耗时,所以不同的情况下,需要选择不同的List集合做不同的业务

    3.删除

    与ArrayList不同,删除不需要拷贝元素,LinkedList是找到元素位置。

    1.确定出要删除的元素X,把前后的链接进行替换。
    2.如果是删除首尾元素,操作起来会更加容易,这也就是为什么说插入和删除块,但中间位置删除,需要遍历找到对应的位置

    3.1删除操作方法

    序列方法描述
    1list.remove()与removeFirst()一致
    2list.remove(1)删除Idx=1的位置元素节点,需要遍历定位
    3list.remove('a')删除元素=‘a'的节点,需要遍历定位
    4list.removeFirst();删除首位节点
    5list.removeLast();删除结尾节点
    6list.removeAll(Arrays.asList('a','b'))按照集合批量删除,底层是Iterator

    源码:

    @Test
    public void test_remove() {
        LinkedList<String> list = new LinkedList<String>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.remove();
        list.remove(1);
        list.remove("a");
        list.removeFirst();
        list.removeLast();
        list.removeAll(Arrays.asList("a", "b"));
    }
    

    3.2源码

    分为删除首尾节点与其他节点的时候,对节点的解链操作。

    list.remove('a');

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    1.这一部分是元素定位,和unlink(x)解链.循环查找对应的元素。

    unlink(x)解链

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

    1.获取待删除节点的信息;元素item、元素下一个节点next、元素上一个节点prev。
    2.如果上一个节点为空,则把待删除元素的下一个节点赋值给首节点,否则把待删除节点的下一个节点,赋值给删除节点的上一个节点的子节点。
    3.同样待删除节点的下一个节点next,也执行2步骤同样操作。
    4.最后是把删除节点设置为null,并扣减size和modeCount数量

    4.遍历

    ArrayList与LinkedList的遍历都是通用的,基本包括5种方式。

    int xx = 0;
    @Before
    public void init() {
        for (int i = 0; i < 10000000; i++) {
            list.add(i);
        }
    }

    4.1普通for循环

    @Test
    public void test_LinkedList_for0() {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < list.size(); i++) {
            xx += list.get(i);
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    4.2增强for循环

    @Test
    public void test_LinkedList_for1() {
        long startTime = System.currentTimeMillis();
        for (Integer itr : list) {
            xx += itr;
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    4.3Iterator遍历

    @Test
    public void test_LinkedList_Iterator() {
        long startTime = System.currentTimeMillis();
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            xx += next;
        }
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime))
    }

    4.4forEach循环

    @Test
    public void test_LinkedList_forEach() {
        long startTime = System.currentTimeMillis();
        list.forEach(integer -> {
            xx += integer;
        });
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    4.5stream(流)

    @Test
    public void test_LinkedList_stream() {
        long startTime = System.currentTimeMillis();
        list.stream().forEach(integer -> {
            xx += integer;
        });
        System.out.println("耗时:" + (System.currentTimeMillis() - startTime));
    }

    1.ArrayList与LinkedList都有自己的使用场景,如果在集合首位有大量的插入、删除以及获取操作那么可以使用LinkedList,因为它有相应的方法:addFirst、addLast、removeFirst、removeLast、getFirst、getLast、这些操作的时间复杂度都是O(1),很高效。
    2.LinkedList的链表结构不一定比ArrayList节约空间,首先它占的内存不是连续的,其次它需要大量的实例化对象创造节点,虽然不一定节省空间,但是链表结构也是很好的数据结构,它能在你程序设计中起到很优秀的作用,列入可视化链路追踪图,就是需要链表结构,并需要每一个节点自旋一次,用于串联业务

    展开全文
  • 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]
    	

     

    展开全文
  • 网上有很多比较ArrayList和LinkedList的文章,基本上都认为ArrayList是用数组实现,而LinkedList用链表实现,所以ArrayList查询效率高,LinkedList插入效率高,但是事实真的是这样吗? 比较他们的使用效率之前,先看...

    网上有很多比较ArrayList和LinkedList的文章,基本上都认为ArrayList是用数组实现,而LinkedList用链表实现,所以ArrayList查询效率高,LinkedList插入效率高,但是事实真的是这样吗?

    比较他们的使用效率之前,先看看ArrayList与LinkeLlist的底层数据结构。

    1. /** 
    2.       * The array buffer into which the elements of the ArrayList are stored. 
    3.       * The capacity of the ArrayList is the length of this array buffer. 
    4.       */  
    5.      private transient Object[] elementData;  
    6.    
    7.      /** 
    8.       * The size of the ArrayList (the number of elements it contains). 
    9.       * 
    10.       * @serial 
    11.       */  
    12.      private int size; 

    ArrayList内部用数组来保存元素,size记录当前数组的大小。但是数组的大小是确定的,那么他是怎么实现ArrayList这种大小可变的集合的呢?

    1. public boolean add(E e) {  
    2.     ensureCapacity(size + 1);  // Increments modCount!!  
    3.     elementData[size++] = e;  
    4.     return true;  
    5. }
    1. /** 
    2.       * Increases the capacity of this <tt>ArrayList</tt> instance, if 
    3.       * necessary, to ensure that it can hold at least the number of elements 
    4.       * specified by the minimum capacity argument. 
    5.       * 
    6.       * @param   minCapacity   the desired minimum capacity 
    7.       */  
    8.      public void ensureCapacity(int minCapacity) {  
    9.      modCount++;  
    10.      int oldCapacity = elementData.length;  
    11.      if (minCapacity > oldCapacity) {  
    12.          Object oldData[] = elementData;  
    13.          int newCapacity = (oldCapacity * 3)/2 + 1;  
    14.              if (newCapacity < minCapacity)  
    15.          newCapacity = minCapacity;  
    16.              // minCapacity is usually close to size, so this is a win:  
    17.              elementData = Arrays.copyOf(elementData, newCapacity);  
    18.      }  
    19. 每次ArrayList在添加元素的时候都会调用ensureCapacity方法,这个方法会检查数组容量是否够大,如果不够则新创建一个容量为1.5倍的数组,
    20. 并把数据复制到这个新数组上。
    21. 所以不能简答的说ArrayList底层数据结构是一个数组,其实它是一个动态表。
       接下来看看LinkedList的实现,它是一个双向循环链表。
    1. //链表大小,transient代表不可序列化  
    2. transient int size = 0;  
    3.   
    4. /** 
    5.  * 指向头节点的指针 
    6.  */  
    7. transient Node<E> first;  
    8.   
    9. /** 
    10.  * 指向尾节点的指针 
    11.  */  
    12. transient Node<E> last;  

    1. private static class Node<E> {  
    2.     E item;  
    3.     Node<E> next; // 指向后一个结点  
    4.     Node<E> prev; // 指向前一个结点  
    5.   
    6.     Node(Node<E> prev, E element, Node<E> next) {  
    7.         this.item = element;  
    8.         this.next = next;  
    9.         this.prev = prev;  
    10.     }  
    11. }
    12. 值得注意的是,这里的链表节点是linkedlist的私有内部类,也就是说其他类是不可能拿到节点的引用的。所以在链表中间插入的时候,通过修改几个指针就能插入一个节点这样的操作是不可能的。
        
        了解底层实现之后,我们开始比较ArrayList与linkedlist的插入效率。
        1.尾部插入
        
    1. public boolean add(E e) {  
    2.     ensureCapacity(size + 1);  // Increments modCount!!  
    3.     elementData[size++] = e;  
    4.     return true;  
    5. }
      ArrayList最常用的add方法就是尾部插入,在不需要扩容的情况下,只需要将size递增即可,时间复杂度O(1)
    6. 需要扩容的情况下,时间复杂度也不会受到影响。理由如下:
    7. 假设它每次扩容两倍,那么从开始的16个元素扩容到n,共需要复制16+32+。。。+n/4+n/2+n<2n个元素
    8. 所以平均到每一次添加操作,扩容只需要复制常数个元素 

    1. /** 
    2. *默认的添加动作,可以看到这个方法是把新元素添加 到表尾 
    3. */  
    4. public boolean add(E e) {  
    5.     addBefore(e, header); //加到头结点之前 ,即表尾  
    6.         return true;  
    7. }
    1. /**  
    2. *将元素e添加到entry结点之前  
    3. */  
    4. private Entry<E> addBefore(E e, Entry<E> entry) {  
    5.     Entry<E> newEntry = new Entry<E>(e, entry, entry.previous);  
    6.     newEntry.previous.next = newEntry; //将新结点与前后结点相连接   
    7.     newEntry.next.previous = newEntry;  
    8.     size++;  
    9.     modCount++;  
    10.     return newEntry;  
    11. }
    12. 可以看出linkedlist的最常用的add方法也是插入尾部,只需要改变几个指针,时间复杂度O(1)
       综上,在两个集合最常用的尾部插入时间复杂度都是O(1),不存在ArrayList插入比linkedlist慢的说法

       2.中间插入
    1. public void add(int index, E element) {  
    2.      if (index > size || index < 0)  
    3.          throw new IndexOutOfBoundsException(  
    4.          "Index: "+index+", Size: "+size);  
    5.    
    6.      ensureCapacity(size+1);  // Increments modCount!!  
    7.      System.arraycopy(elementData, index, elementData, index + 1,  
    8.               size - index);  
    9.      elementData[index] = element;  
    10.      size++;  
    11. }
    12. ArrayList的中间插入效率比较低,因为需要将index之后的元素往后移动,时间复杂度O(n),但是不代表ArrayList就比linkedlist慢
    1. public void add(int index, E element) {
              checkPositionIndex(index);


              if (index == size)
                  linkLast(element);
              else
                  linkBefore(element, node(index));
       }
    2.     /**
           * Returns the (non-null) Node at the specified element index.
           */
          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;
              }
          }
    3. linkedlist虽然插入的时间复杂度为O(1),但是在每次插入前需要找到插入的位置。前面已经说过linkedlist的node节点是私有内部类,外部不可能拿到node的引用,所以linkedlist只能进行顺序寻址找到插入的位置,总时间复杂度也是O(n)
         综上,ArrayList与linkedlist在中间插入的时间复杂度也是一样
       
       3.迭代器插入
       linkedlist和ArrayList内部都内置了一个迭代器用来遍历他们里面的元素,在遍历的时候也可以插入元素。ArrayList的迭代器插入用的是中间插入的方法,所以时间复杂度还是一样。但是linkedlist在迭代过程中不需要定位插入的位置,插入的时间复杂度变成O(1)。所以在需要迭代器插入O(n)个元素的时候,ArrayList时间复杂度为O(n^2),而linkedlist的时间复杂度为O(n),这时候才体现了链表插入的优势。但是如果只需要插入常数个元素的时候,迭代器遍历的开销大于插入的开销,此时两个集合的时间复杂度还是一样。

       所以,不能简单的说ArrayList插入速度比linkedlist慢,附上别人做的性能测试,仅供参考
    http://blog.csdn.net/dlutbrucezhang/article/details/9931025











    展开全文
  • linkedList是通过一个双向链表来实现的,它允许插入所有元素,包括null,它是线程不安全的 1、双向链表是什么样子 如下图:双向立案别有一个first指针和next指针,分别指向头结点和尾结点。另外还有一个前指针和后...

    前言:

    linkedList是通过一个双向链表来实现的,它允许插入所有元素,包括null,它是线程不安全的

    1、双向链表是什么样子

    如下图:双向链表有一个first指针和next指针,分别指向头结点和尾结点。另外还有一个前指针和后指针,指向前驱结点和后继结点
    在这里插入图片描述
    上篇博客我们着重的讲解了ArrayList的扩容机制和add 方法,其中ArrayList如果在指定位置插入相关元素是非常耗时的,时间复杂度为O(n),那么这个双向链表到底是如何实现插入数据的呢,请看下图:

    2、源码分析

    2.1 属性
    
    	// 链表的结点个数
    	 transient int size = 0;
    
       // 指向头结点的指针
        transient Node<E> first;
    
      //指向尾结点的指针
        transient Node<E> last;
    
    

    2.2Node类

    注意这是一个静态内部类:

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

    2.3 从链表尾部添加数据

    当向表尾插入一个节点时,很显然当前节点的后继一定为 null,而前驱结点是 last 指针指向的节点,然后还要修改 last 指针指向新的尾节点。此外,还要修改原来尾 节点的后继指针,使它指向新的尾节点
    在这里插入图片描述
    源码的实现如下:

        void linkLast(E e) {
            // l就是链表最后一个节点
            final Node<E> l = last;
            //当前节点的前驱指向尾节点,后继指向 null 
            final Node<E> newNode = new Node<>(l, e, null);
             //尾指针指向新的尾节点 
            last = newNode;
            //如果原来有尾节点,则更新原来节点的后继指针,否则更新头指针 
            //当最开始添加数据,链表是空的,添加第一个数据,头指针和尾指针指的是同一个结点
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    

    从链表首部添加数据和上边的逻辑类似,后面就不陈述了。

    2.4从链表中间插入数据

    在这里插入图片描述
    源码:这个与下图匹配一块看

       //succ表示的是当前结点,就是所要插入的位置的前一个结点
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
             //指定节点的前驱 
            final Node<E> pred = succ.prev;
            //当前节点的前驱为指定节点的前驱,后继为指定的节点 如下图的 1,2
            final Node<E> newNode = new Node<>(pred, e, succ);
              //更新指定节点的前驱为当前节点,如下图的3
            succ.prev = newNode;  
            //更新前驱节点的后继,如下图的4
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    

    在这里插入图片描述

    3、总结

    (1) LinkedList 的底层结构是一个带头、尾指针的双向链表,可以快速的对头/尾节点 进行操作。
    (2)相比ArrayList,链表的特点就是在指定位置插入和删除元素的效率较高,但是查找的效率不如ArrayList。

    展开全文
  • 容器-LinkedList指定位置添加元素的源码分析(九) LinkedList指定索引位置添加元素 public static void main(String[] args) { List<String> list= new LinkedList<>(); //添加元素 list.add("a...
  • Java学习笔记——LinkedList插入和删除速度真的比ArrayList快吗 问:LinkedList 和 ArrayList 有什么区别? 答: LinkedList 实现了 List 和 Deque 接口,一般称为双向链表; ArrayList 实现了List 接口,称为...
  • 10万、100万、1000万,数据在两种集合下不同位置的插入效果,所以:,不能说LinkedList插入就快,ArrayList插入就慢,还需要看具体的操作情况。 接下来我们带着数据结构和源码,具体分析下。 三、数据结构 Linked + ...
  • 在数据尾部插入数据 测试代码 package com.lly.springtest1.collection; import lombok.extern.slf4j.Slf4j; import java.util.ArrayList; import java.util.LinkedList; /** * @ClassName ICollecti...
  • 1、线性表不仅可以存储重复的元素,而且允许用户指定它们存储的位置,可以用下标来访问元素。 2、List接口增加了面向位置的操作,并且增加了一个能够双向遍历线性表的新列表迭代器。 ListIterator接口扩展了...
  • Java中LinkedList删除元素

    万次阅读 2018-05-24 00:47:21
    今天敲代码看到一个例子,在迭代器遍历的时候插入元素报错,有提到原因,但没有提到删除元素的方法,就自己试了一下。import java.util.*; public class IteratorTest { public static void main(String[] args) {...
  • LinkedList删除,插入快。 ArrayList查询,修改快,可以理解,因为定位快。 但是删除和插入真的LinkedList就比ArrayList快吗,我做了一些测试,以下是个人的一些看法,欢迎讨论。 一、连续插入: 1.随机位置连续...
  • Java 向List指定位置插入元素 list.add(index, object) index:插入位置索引 object: 插入对象 ArrayList, LinkedList 同理
  • ArrayList和linkedList插入、查找、删除

    千次阅读 热门讨论 2017-07-08 18:06:31
    ArrayList:AL LinkedList:LL ...有频繁的插入、删除使用AL不合适,因涉及到其他元素左右移动问题; LL不易于查找;有频繁的插入、删除操作使用LL比较合适,因只涉及修改前后连接; 还是 AL比LL的各方面都要好。
  • LinkedList

    2021-09-21 09:16:18
    public void addFirst(E e):在该列表开头插入指定元素 public void addLast(E e):将指定的元素追加到此列表的末尾 public E getFirst():返回此列表中的第一个元素 public E getLast():返回此列表中的最好一个元素 ...
  • 2.get,set方法,方法参数有指定位置数值的,ArrayList要优于LinkedList,因为,ArrayList有下标,LinkedList要移动指针。 3.新增和删除操作add和remove,LinkedList比较占优势,因为ArrayList需要移动数据 ...
  • 实现比较器(Comparator)接口 实现比较器例子: ...2、如果我们经常在List的开始处增加元素,或者在List中进行插入和删除操作,我们应该使用LinkedList,否则的话,使用ArrayList将更加快速。
  • ArrayList和LinkedList插入和访问的时间复杂度?** ArrayList插入源码: 如果ArrayList没有扩张,那么插入的复杂度为O(1); 如果ArrayList扩张了,那么插入的复杂度主要集中在System.arraycopy()这个方法的复杂度...
  • //在指定位置插入元素: cout 输入插入链表元素的位置:"; int site; cin >> site; cout 输入插入链表的元素:"; int e; cin >> e; insert(list, site, e); outputList(list); //在指定位置删除元素: cout 输入...
  • 它的添加和删除元素的相关方法比较多,容易混淆,这里简单总结下。 add,remove,addFirst,addLast,removeFirst,removeLast,pollFirst,pollLast,offerFirst,offerLast等方法看名字就知道添加和删除的顺序,就不举例了...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,050
精华内容 19,620
关键字:

linkedlist插入指定元素