精华内容
下载资源
问答
  • 比如现在给数字3要求删除,再删除6,然后给3要求按顺序插入,不要给按顺序直接删除的答案,而是查找到后再删除 import java.util.*; class s{ public int i; s(int s){i=s; } } public class display { ...
  • 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&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

    2020-02-20 15:52:25
    LinkedList无需提前指定容量,因为基于链表操作,集合的容量随着元素的加入自动增加 LinkedList的所有方法没有进行同步,因此它也不是线程安全的,应该避免在多线程环境下使用 //结点内部类 privat....
     LinkedList是基于双向链表实现的,因此插入删除快而查找修改慢。 与ArrayList不同的是LinkedList没有指定初始大小的构造器。
    • LinkedList无需提前指定容量,因为基于链表操作,集合的容量随着元素的加入自动增加
    • LinkedList的所有方法没有进行同步,因此它也不是线程安全的,应该避免在多线程环境下使用
      //结点内部类
      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;
         }
      //增(添加)
      public boolean add(E e) {
         //在链表尾部添加
         linkLast(e);
         return true;
      }
      
      //增(插入)
      public void add(int index, E element) {
         checkPositionIndex(index);
         if (index == size) {
             //在链表尾部添加
             linkLast(element);
         } else {
             //在链表中部插入
             linkBefore(element, node(index));
         }
      }
      
      //删(给定下标)
      public E remove(int index) {
         //检查下标是否合法
         checkElementIndex(index);
         return unlink(node(index));
      }
      
      //删(给定元素)
      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;
      }
      
      //改
      public E set(int index, E element) {
         //检查下标是否合法
         checkElementIndex(index);
         //获取指定下标的结点引用
         Node<E> x = node(index);
         //获取指定下标结点的值
         E oldVal = x.item;
         //将结点元素设置为新的值
         x.item = element;
         //返回之前的值
         return oldVal;
      }
      
      //查
      public E get(int index) {
         //检查下标是否合法
         checkElementIndex(index);
         //返回指定下标的结点的值
         return node(index).item;
      }

       

      /链接到指定结点之前
      void linkBefore(E e, Node<E> succ) {
         //获取给定结点的上一个结点引用
         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 unlink(Node<E> x) {
         //获取给定结点的元素
         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;
      }

       通过下标定位时先判断是在链表的上半部分还是下半部分,如果是在上半部分就从头开始找起,如果是下半部分就从尾开始找起,因此通过下标的查找和修改操作的时间复杂度是O(n/2)。

      /根据指定位置获取结点
      Node<E> node(int 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;
         }
      }

       

    展开全文
  • Debug LinkedList

    2020-07-26 18:24:00
    目录Debug LinkedList源码2.1 Debug 分析第一个元素是如何进入链表的2.2 Debug 分析如何通过下标插入指定位置add(index,e)2.3 Debug 分析如何通过下标获取指定元素2.4 Debug 分析如何通过下标删除元素2.5 Debug ...

    Debug LinkedList源码

    前置知识

    • LinkedList基于链表,LinkedList的Node节点定义

    image-20200719145701402

    • 成员变量

      //链表中元素的数量
          transient int size = 0;
      
          /**
           * 链表的头节点:用于遍历
           */
          transient Node<E> first;
      
          /**
      	* 链表的尾节点:用于添加元素
           */
          transient Node<E> last;

    2.1 Debug 分析第一个元素是如何进入链表的

    编写测试代码,打上断点:

    image-20200726161013956

    进入方法内部:

    • add方法默认添加到链表的尾部
    • 该方法等同于addLast(区别就是add方法需要返回一个true,而addLast没有任何返回值)

    image-20200726161221902

    image-20200726161546055

    进入linkLast方法内部:

    /**
         * 当前方法执行完后,若添加的节点为第一个节点,链表的last和first都指向新节点
         */
        void linkLast(E e) {
            //获取到链表的最后一个元素
            final Node<E> l = last;
            //创建一个节点,前一个节点为当前链表的last,后一个节点为空
            final Node<E> newNode = new Node<>(l, e, null);
            //修改last为新添加的节点
            last = newNode;
            //若链表为空,first节点为新添加的节点,否则添加前最后一个节点的next指向新节点
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
                
                //链表长度加一
            size++;
            	//链表修改次数加1
            modCount++;
        }
        
    //=================================================================
        
        Node带三个参数的构造函数:
        Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }

    2.2 Debug 分析如何通过下标插入指定位置add(index,e)

    编写测试用例:

    image-20200726163053756

    进入方法内部:

    public void add(int index, E element) {
    		//检查下标是否合法:大于等于0小于等于size【return index >= 0 && index <= size;】
            checkPositionIndex(index);
    
    		//若等于size,相当于在链表尾部添加节点
            if (index == size)
                linkLast(element);
            else
            //linkBefore中的Before指的是传入索引元素前
                linkBefore(element, node(index));
        }

    进入node(index)方法:返回索引为index的元素

    Node<E> node(int index) {
            // assert isElementIndex(index);
    
    	   //查找元素的思路是遍历一半,先折半分区,然后若在小于折半的区域就从first开始往后遍历,反之从last往前遍历
    	   //右移一位相当于除以2
            if (index < (size >> 1)) {
            //获取到first节点
                Node<E> x = first;
                //从first遍历到index的位置
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
            
            //获取到next的节点
                Node<E> x = last;
                //从last往前遍历到index的位置
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }

    回到linkBefore方法:

    void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            //获取index节点的上一个节点
            final Node<E> pred = succ.prev;
            //创建新节点,下一个节点指向index节点,上一个节点指向index节点的上一个节点
            final Node<E> newNode = new Node<>(pred, e, succ);
            //index节点的上一个节点指向变为指向新节点
            succ.prev = newNode;
            //**若index节点的头节点为空,相当于从头部插入节点,直接将新节点赋给first节点
            if (pred == null)
                first = newNode;
            else
            //index的上一个节点的下一个节点指向改为新节点
                pred.next = newNode;
                
                //节点长度+1
            size++;
                //链表修改次数+1
            modCount++;
        }

    2.3 Debug 分析如何通过下标获取指定元素

    编写测试代码,打上断点:

    image-20200726174022431

    进入get方法内部:

    public E get(int index) {
    		//检查下标范围
            checkElementIndex(index);
            //遍历一半,返回节点的值
            return node(index).item;
        }

    LinkedList支持的查询除了通过下标获取外,还支持getLast和getFirst

    image-20200726174631658

    get(0)和getFirst时间复杂度有区别吗?

    理论上来说,getFirst和getLast都是直接获取到节点,时间复杂度为O(1),而通过get(index)方法查询节点,都会折半后遍历一半的元素,时间复杂度为O(n)。但实际情况下,for循环遍历的第一个元素就100%是头节点或尾节点,不会进入之后的循环,实际运行的也是O(1)。

    2.4 Debug 分析如何通过下标删除元素

    打上断点:

    image-20200726175453328

    进入方法内部:

    public E remove(int index) {
    		//检查下标范围
            checkElementIndex(index);
            //node(index)获取需要删除的节点,折半遍历
            return unlink(node(index));
        }

    进入unlink方法内部:

    删除中间元素的过程图:

    image-20200726181403239

    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节点
                first = next;
            } else {
            //若删除的节点为中间节点,将当前节点的上一个节点的下一个节点指向变为当前节点的下一个节点(step1)
                prev.next = next;
                //当前节点的上一个节点指向置为null(step2)
                x.prev = null;
            }
    
            if (next == null) {
            //若删除的节点为尾节点,将当前节点的上一个节点赋给last
                last = prev;
            } else {
            //若删除的节点为中间节点,将当前节点的下一个节点的上一个节点指向变为当前节点的上一个节点(step3)
                next.prev = prev;
                //当前节点的下一个节点指向置为null(step4)
                x.next = null;
            }
    
    		//节点元素内容置为空
            x.item = null;
            //链表长度-1
            size--;
            //链表修改次数+1
            modCount++;
            //返回删除节点内容		
            return element;
        }

    2.5 Debug 分析如何通过对象删除节点(内容)

    image-20200726181609167

    public boolean remove(Object o) {
    		//若节点为null,从first往下遍历(说明LinkedList是允许为空值的,并且允许多个)
            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;
        }
    展开全文
  • LinkedList集合

    2019-11-26 21:32:27
    LinkedList集合 ​ 底层是链表结构实现,查询慢...在该列表开头插入指定元素 public void addLast(E e) 将指定的元素追加到此列表的末尾 public E getFirst() 返回此列表中的第一个元素 public ...
  • void add(int index, E element) 在此列表中指定的位置插入指定的元素。 void addFirst(E e) 将指定元素插入此列表的开头。 void addLast(E e) 将指定元素添加到此列表的结尾。 boolean offer(E e) 在尾部添加元素
  • LinkedList理解

    2020-05-06 10:44:45
    Deque接口 支持两端元素插入和移除的线性集合。 public interface Deque<E> extends Queue<E> { //插入此双端队列的前面 ... //在此deque的前面插入指定元素 boolean offerFirst(E e); ...
  • LinkedList源码分析

    2020-08-11 19:47:15
    LinkeList是List接口的另一种实现,它的底层是基于双向链表...LinkedList重载了两个构造函数:一个是无参构造函数,一个是传入外部集合的构造器,与ArrayList不同的是:LinkedList没有指定初始大小的构造器 添加元素
  • ArrayList与LinkedList

    2019-05-27 15:16:53
    2)当执行插入或删除操作时,采用LinkedList比较好 3)执行搜索操作时,采用AttayList比较好 ArrayList 增加元素到链表中 boolean add(Element e) 增加指定元素到链表尾部. void add(int index, Element e) ...
  • LinkedList源码解析 一封不动的源代码 +注释 ...offerFirst( E e)插入指定元素到队列头部 offerLast( E e)插入指定元素到队列尾部 peekFirst()返回队列的头元素 peekLast()返回队列的尾元素 pollFirst()删除并...
  • LinkedList PK ArrayList

    2020-08-26 11:19:01
    指定index插入元素:1、ArrayList 最坏情况性能O(n),最好情况是(容量不够时,需要扩容)O(1) ArrayList扩容机制 2.LinkedList 在都是O(1) 删除操作 1、ArrayList 删除操作最坏情况下性能是O(n),最好O(1),删除最后...
  • LinkedList的使用

    2018-11-22 22:59:59
    import java.util.LinkedList; /** LinkedList集合:有序,有索引,可重复,基于链表的实现,查询慢,增删快。(双链表) 链表结构的首尾可以直接定位,所以... -----addFirst(E e):将指定元素插入此列表的开头。...
  • Java 基础 LinkedList

    2020-03-19 21:48:47
    package demo1; /* * java.util.LinkedList集合 implement List集合 * LinkedList集合的特点: * 1....* 2....* 注意:使用LinkedList集合特有的方法,不能使用...* public void add First(E e):将指定元素插入此列表的开...
  • 48、LinkedList集合

    2020-12-24 08:53:57
    LinkedList集合 LinkedList集合是List接口的实现类。...public void addFirst(E e):将指定元素插入此列表的开头。//等效于push()方法 public void addLast(E e):将指定元素添加到此列表的结尾。 public E getF
  • //在列表开头插入指定元素 boolean allLast(Object o);//在列表结尾插入指定元素 //2. 获取方法 Object getFirst();//返回列表中的第一个元素,但不删除元素 Object getLast();//返回列表中的最后一个元素,但不...
  • LinkedList 实现原理

    2020-07-01 20:00:20
    2、相比数组,链表的特点就是在指定位置插入和删除元素的效率较高,但是查找的效率就不如数组那么高了 常用的方法 双向链表,头节点均指first,尾节点均指last 添加元素: add(E e):将元素添加到表尾,返回布尔类型...
  • python实现linkedList

    2021-01-19 13:14:23
    python 仿照 list api实现的 linkedList from ds.util.Data import Data class LinkedList: """ 模拟python列表实现的 链表 打印字符串 会导致遍历 remove 会导致遍历 ... 支持 指定位置插入 支持 f
  • 异: 数据结构上:ArrayList底层数据结构是数组,而LinkedList采用的是双向链表。...LinkedList虽然是双向链表,但他的删除元素remove(Element e)和删除指定位置元素remove(int index),插入指...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 273
精华内容 109
热门标签
关键字:

linkedlist插入指定元素