精华内容
下载资源
问答
  • 双向链表为何时间复杂度为O(1)?

    千次阅读 2019-09-25 05:59:57
    双向链表相比于单向链表,所谓的O(1)是指删除、插入操作。 单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(通过待删除节点序号或按值查找)。若仅仅知道待删除节点,是不能知道前驱节点的,故...

            双向链表相比于单向链表,所谓的O(1)是指删除、插入操作。

           单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(通过待删除节点序号或按值查找)。若仅仅知道待删除节点,是不能知道前驱节点的,故单链表的增删操作复杂度为O(n)。 双链表(双向链表)知道要删除某一节点p时,获取其前驱节点q的方式为 q = p->prior,不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号,则依然要按序查找,时间复杂度仍为O(n)。

           单、双链表的插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(n)。至于查找,二者的时间复杂度均为O(n)。 对于最基本的CRUD操作,双链表优势在于删除给定节点。但其劣势在于浪费存储空间(若从工程角度考量,则其维护性和可读性都更低)。

           双链表本身的结构优势在于,可以O(1)地找到前驱节点,若算法需要对待操作节点的前驱节点做处理,则双链表相比单链表有更加便捷的优势。

     

    转载于:https://www.cnblogs.com/RambleIvy/p/11414116.html

    展开全文
  • 注意看带头结点的双向链表,他的时间效率,不管哪种操作,都是O(1),实际上是利用了空间提高时间

     

    注意看带头结点的双向链表,他的时间效率,不管哪种操作,都是O(1),实际上是利用了空间提高时间

    展开全文
  • 链表插入操作的时间复杂度真的是O(1)吗?

    千次阅读 多人点赞 2019-01-24 22:29:34
    提起链表,很多人可能都会知道它的优势就是能够快速插入、删除数据。但是往链表插入数据的时间复杂度真的是O(1)吗?相信看完这篇文章,读者会有自己的答案了。为什么用一节来讲解链表代码实现 ...

    提起链表,很多人可能都会知道它的优势就是能够快速插入、删除数据。但是往链表中插入数据的时间复杂度真的是O(1)吗?相信看完这篇文章,读者会有自己的答案了。

    为什么用一节来讲解链表代码实现 ?

    1. 链表的代码量虽然不多,但是其中充满了大量的指针操作,所以很考验面试者对指针引用操作的熟练程度。

    2. 链表的操作往往需要考虑到对边界问题的考虑,比如在链表是空链表的情况下,代码是否还能正确执行。

    这同时考察了一个程序员的编程基本功,也能体现一个程序员在逻辑上是否是足够严谨的,思维是否缜密。所以很面试官在面试的时候都特别青睐询问链表相关的题目。

    需要掌握到何种程度

    上一节发布之后,很多人私信跟我说: 我已经了解了什么是链表,以及它的特点。难道这就已经足够了吗??代码方面还是写不出来没有关系吗??

    链表并不像 红树、图算法那样,复杂到几乎不可能在短短的1、2个小时内写出完整并正确的实现代码。相反,链表的创建、插入和删除结点等操作都只需要20行左右的代码就能实现,所以面试官一般都是直接让应聘者手写链表代码的。

    基于这个原因,对于链表的基本操作代码,应聘者必须熟练到如同写 Hello World 的程度。不要仅仅满足于能够实现功能即可,还需要保证代码的准确性以及高运行效

    正式进入代码阶段

    链表的基本操作

    链表的基本操作,基本可以按照下图中从上到下的流程依次来掌握。

    基本可以概括为增、删、查找。其中,添加和删除头结点、尾节点的时间复杂度为O(1),查找操作以及向链表中间位置插入节点的时间复杂度则为O(n)。

    工欲善其事必先利其器

    正所谓巧妇难为无米之炊在开始实现以上几个操作之前,我们必须先实现一个链表的节点Node。有了节点之后,才能展开后续的一些列操作。

    实现代码:

    class LinkedList 
    { 
        Node head;  // 链表中的头节点
        Node tail;  // 链表中的尾节点
    
        /* 
         * 节点类,包含数据域data
         * 和指向下一个节点的指针next
         */
        class Node { 
            int data; 
            Node next; 
    
            Node(int d) {
                data = d;
                next = null;
            } 
        } 
    }

    为了操作方便,我们一般会在一个链表中保存一个head引用和一个tail引用,分别用来保存链表的头节点尾节点。这种机制通常被叫做哨兵机制。当初始化链表LinkList时,头节点和尾节点都为null,也就是一个空链表

    有了节点之后,就可以来看一下链表基本操作的具体实现了。

    先从查找节点开始

       searchNode、nodeAtPosition

    因为后续的插入和删除操作会用到这里的代码,所以将查找操作放到前面来讲。查找操作分为两种:searchNodenodeAtPosition,见名知意一个是根据value查找,另一个是根据下标index查找。

    searchNode:  查找指定value的节点

    比如要在下列链表中,查找是否含有value等于9的节点,如果找到就返回,否则返回null。

    我们只要从head节点3开始,依次判断所遍历到的节点value是否等于9,如果不是就继续遍历节点next所指向的下一个节点。

    也就是说,查找操作需要遍历链表中的每一个节点进行判断,直到找到相应节点或者遍历到尾结点tail为止。因此时间复杂度为O(n)。

    实现代码如下:

    /*
     * 查找指定元素,找到了返回节点Node,找不到返回null
     */
    public Node searchNode(int value){
          Node current = head;  // 从头结点head开始遍历
    
          while(current != null){  // 只有尾节点tail的next指向null
              if(value == current.data){
                  return current;  // 找到节点并返回
              }else{
                  current = current.next;  // 继续遍历下一个节点
              }
          }
    
          return null;  // 遍历整个链表也没有找到,返回null
    }
    

    nodeAtPosition: 查找指定位置index的节点

    根据下标查找相对简单一些,只要定义一个循环次数就是index的 while语句 即可,直接贴出代码

    1  private Node nodeAtPosition(int index) {
    2    verify (index >= 0);  // 伪代码,检验输入index是否有效
    3
    4    Node result = head;   // 从头节点head开始,取index次next引用的节点
    5
    6    while (index > 0) {
    7      result = result.next;
    8      index--;
    9    }
    10
    11    return result;
    12  }

    接下来插入节点

    addLastaddHeadaddNode

    addLast

    我们调用  addLast(int value) 方法,向链表尾部插入一个元素5。向链表中插入元素时,我们需要判断链表是否为空链表。

    1. 如果此时的链表是一个空链表,只需要将被插入元素同时赋值给head和tail节点即可。此时被插入的元素即是头结点,也是尾结点。

    2. 如果链表不为空,这种情况头节点head不需要做任何修改,所有的操作都发生在链表的尾部:

    2.1 先将尾节点5的next指针指向被插入元素
    

    2.2 然后重新将被插入元素赋值给尾结点tail即可。
        此时的尾节点变为被插入节点
    
    同样的操作,依次插入9、13之后的链表如下: 

    将元素9、13插入到链表中

    具体实现代码如下:

    void addLast(int value) {
      Node newNode = new Node(value);
    
      if (head == null) { // 空链表
          head = tail = newNode;
      } else {  // 非空链表  
          // 将当前尾节点的next指针指向被插入元素
          tail.next = newNode;  
      }
      
      tail = newNode;  // 重新将被插入元素赋值给tail节点
      size++;
    }
    
    

    addHead

    我们调用  addHead(int value) 方法,向链表头部插入一个元素。这个操作甚至比  addLast 更加简单,为什么这么说呢,先看下代码:

    1void addHead(String value) {
    2    Node newNode = new Node(value);
    3
    4    newNode.next = head;  // 将head赋值给新插入节点的next指针
    5    head = newNode;       // 重新将被插入节点赋值给head引用
    6    size++;
    7}
    
    

    可以看出,在addHead方法中,甚至都不需要判断链表是否为空链表。因为即使head是null,第4行代码无非就是将被插入节点newNode的next指针指向一个空值null罢了,然后在第5行代码中会重新给head赋值。因此addHead方法不需要判断操作,因为代码很简单,并且同addLast类似,这里就不再贴图占用篇幅了。

    addNode(int index, int value)

    这是一个比较重量级的操作,意思是向链表中index位置上,插入指定vaule的节点。比如

    输入:

     原始链表 3->5->8->10, index = 2, value = 9
    

    则输出

     修改后链表 3->5->9->8->10
    

    基本可以按照以下思路去实现这一操作:

    1. 从0下标开始遍历链表到 position - 1 的位置

    2. 当遍历到 position - 1 的节点(可叫做currentNode)时,根据传入的value创建节点newNode

    3. 将被插入节点newNode的next指针指向当前currentNode的next指针指向的节点

    4. 重新将当前currentNode的next指针指向newNode

     1  /*
     2   * linked list
     3   */
     4  public void addNode(int index, int value) {
     5    if ((index < 0) || (index > size)) {
     6      String badIndex =
     7        new String ("index " + index + " must be between 0 and " + size);
     8      throw new IndexOutOfBoundsException(badIndex);
     9    }
    10    if (index == 0) {
    11      addHead (value);
    12    } else {
    13      addAfter (nodeAtPosition (index - 1), value);
    14    }
    15    size++;
    16  }
    

    注意:新手可能经常会将步骤3和步骤4的执行顺序给颠倒!导致的后果就是指针丢失

    【插图--正常执行顺序和错误执行顺序】

    最后删除节点

    removeLast、removeHead、removeNode

    链表的删除操作同添加操作基本大同小异,遵循的规律也是一样的。所以直接po出代码,就不配图了。

    removeNode: 删除指定下标的节点

    1/**
    2 * 删除指定位置的节点,时间复杂度O(n)
    3 */
    4public void removeNode(int index){
    5    if(index < 0 || index > size){
    6        throw new IllegleStateException();
    7    }
    8    //删除链表中的第一个元素
    9    if(index == 0){
    10        removeHead();
    11    }
    12
    13    int i=1;
    14    Node preNode = head;
    15    Node curNode = preNode.next;
    16
    17    while(curNode != null){
    18        if(i == index){
    19            preNode.next = curNode.next;
    20        }
    21        preNode = curNode;
    22        curNode = curNode.next;
    23        i++;
    24    }
    25}

    removeHead: 删除头节点

    1void removeHead() {
    2    if (head == null) {
    3        String exceptionMsg = new String ("LinkList is empty");
    4        throw new IndexOutOfBoundsException(badIndex);
    5    }
    6    Node temp = head;
    7    head = head.next;
    8    tmp.next = null;
    9    size--;
    10}

    removeLast: 删除尾节点

    因为我们已经实现了删除指定下标的节点,而尾节点的下标就是size - 1,所以直接调用 removeNode(size - 1) 即可

    /*
     * 直接调用removeNode,所以时间复杂度也为O(n)
     */
     void removeFirst() {
         removeNode(size - 1);
    }

    链表

    内容小结

    链表的操作无非就是添加、删除、查找操作

    01

    添加节点

    addLast 添加尾节点,时间复杂度O(1)

    addHead 添加头节点,时间复杂度O(1)

    addNode 添加节点到链表指定位置,时间复杂度O(n)

    02

    删除结点

    removeLast 删除尾节点,时间复杂度O(1)

    removeHead 删除头节点,时间复杂度O(1)

    removeNode 删除指定位置的节点,时间复杂度O(n)

    03

    查找节点

    searchNode    搜索指定value的节点,时间复杂度O(n)

    nodeAtPosition    搜索指定位置的节点,时间复杂度O(n)

    链表操作极容易发生指针丢失

    应聘者在面试时,如果遇到稍微复杂的链表操作,比如一个经典的链表题--单链表反转(我司必考题),可以尝试列举一个具体的例子,并通过画图来李理清思路,看图写代码就简单多了。

    链表的操作需要考虑边界情况

    针对这种情况,给应聘者的建议就是对你写出的实现代码提出以下几个问题,如果对于每个问题的回答都是肯定的,那就说明你给出的代码基本考虑到了边界情况。

    1. 如果链表为空时,代码是否能正常工作?

    2. 如果链表只包含一个结点时,代码是否能正常工作?

    3. 如果链表只包含两个结点时,代码是否能正常工作

    链表的中级操作

    此文主要是列举了链表的几个基本操作,但是在面试中经常会碰到一些更加复杂的链表操作,这里列举几个比较典型的操作,后续会在APP端给出实现思路以及具体实现代码。

    1. 单链表反转

    2. 链表的倒序打印

    3. 找到倒数第k个元素

    4. 检测链表是否有环

    5. 两个有序链表的合并

    扫描二维码, 下载App了解更多

    展开全文
  • 单链表和双链表的删除和插入时间复杂度分析 单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(开发中大致分为两种删除方式:1.通过待删除节点序号2.按值查找)。若仅仅知道待删除节点,是不能...
    • 单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(开发中大致分为两种删除方式:1.通过待删除节点序号2.按值查找)。若仅仅知道待删除节点,是不能知道前驱节点的,故单链表的增删操作复杂度为O(n)。

    • 双链表(双向链表)知道要删除某一节点p时,获取其前驱节点q的方式为 q = p->prior,不必再进行遍历。故时间复杂度为O(1)。而若只知道待删除节点的序号,则依然要按序查找,时间复杂度仍为O(n)。

    • 单、双链表的插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(n)。

    • 至于查找,二者的时间复杂度均为O(n)。 对于最基本的CRUD操作,双链表优势在于删除给定节点。但其劣势在于浪费存储空间(若从工程角度考量,则其维护性和可读性都更低)。

    双链表本身的结构优势在于,可以O(1)地找到前驱节点,若算法需要对待操作节点的前驱节点做处理,则双链表相比单链表有更加便捷的优势。

    展开全文
  • 优点:构建简单,能在O(1)的时间里根据数组下标来查询某个元素。 缺点:构建时需要分配一段连续的空间,查询某个元素时需要遍历整个数组,耗费O(n)的时间。删除和添加元素同样需要耗费O(n)的时间。 ...
  • 下面简单的分析一下数组和链表分别在有序和无须情况下的时间复杂度。 数组 1、有序数组的删除:数组的存储地址是连续的,我们删除数组中的某个值,首先我们要找到要删除的值,删除此值后,若此值后面还有其他值,每...
  • 单向链表时间复杂度 在单向链表原理和实现中已经和动态数组相比对比并分析了单向链表时间复杂度: 情况分类 添加 删除 最好 头节点 O(1) O(1) 最差 尾节点 O(n) O(n) 平均 O(n) O(n) 双向链表的...
  • 时间复杂度 查询 O(1) 插入(空间充足) O(1) 插入(空间不足) O(n)+O(1)=O(n) 删除(末尾元素) O(1) 删除(非末尾元素且元素个数>1) O(1)+O(n)=O(n) 分析 1.查询:通过index直接定....
  • 单向链表要删除某一节点时,必须要先通过遍历的方式找到前驱节点(通过待删除节点序号或按值查找)...单、双链表插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(..
  • 最近抽空在看数据结构和时间复杂度的文章,今天想谈一下数组和链表相关的问题。 目录 1. 数组 1.1 什么是数组 1.2数据结构 1.2.1一维数组 1.3 为什么数组下标是从0开始 1.4时间复杂度 1.4.1新增 1.4.2...
  • 单链表插入时间复杂度分析

    千次阅读 2021-05-24 22:28:08
    链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个...
  • 链表实现插入排序 # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next ##################################用来练习插入排序...
  • 数组、链表、跳表的时间复杂度和空间复杂度分析一、数组二、链表三、跳表 一、数组 1.1头插入、尾插入、中间某个位置插入 1.2 头删除、尾删除、中间某个位置删除 1.3查找 二、链表 2.1头插入、尾插入、中间某个位置...
  • 顺序表和单链表的插入删除操作时间复杂度的区别 最近在学习数据结构,看到如果需要用到大量的插入和删除操作,单链表的效率会高于顺序表。看到这里时内有有个疑惑,这两种数据结构的插入和删除操作的时间复杂度不都...
  • 单链表插入删除元素时间复杂度探究

    万次阅读 多人点赞 2015-03-26 00:50:07
    单链表相比数组的优势在于插入删除元素快,不需要移动大量的元素,只需要改变指针的指向,那么插入删除操作的时间复杂度应该是O(1),但是这是不对的,应该分情况讨论。 单链表结构体声明: typedefstruct LNode { ...
  • 下面就我自己的感受说说我对内存空间换取降低操作数据时的时间复杂度的一点浅见。 首先单向链表的结构可以简单的表示为: 头结点是节点1的引用,而节点1的next属性又是节点2的应用,以此类推,最后一个节点的next...
  • 转载于:https://www.cnblogs.com/wmxl/p/11309352.html
  • 顺序表与链表时间复杂度比较

    千次阅读 2020-02-15 20:03:25
    顺序表与链表时间复杂度比较 名称 访问 查找 插入 删除 数组 O(1) O(n) O(n) O(n) 有序数组 O(1) O(logN) O(n) O(n) 链表 O(n) O(n) O(1) O(1) 有序链表 O(n) O(n) O(n) O(n) 1、向一个有序数组中...
  • 链表排序,时间复杂度O(nlogn)

    千次阅读 2018-07-04 13:37:30
    题目描述对链表进行排序,要求时间复杂度O(nlogn)解题思路因题目要求复杂第O(nlogn),故可以考虑归并排序(1)将待排序数组(链表)取中点并一分为二;(2)递归地对左半部分进行归并排序(3)递归地对右半部分进行...
  • 总体完成一次操作,大家都是o(n)的复杂度,为什么教材和网路上都说,要频繁删除插入操作时,选链表? 答案: 因为这个O(n)内涵不同,分别是写O(n)和读O(n)。数组擅长读取,链表擅长写入。写入要先读取定位,再写入。...
  • 链表中删除数据的时间复杂度真的是O(1)吗?

    千次阅读 多人点赞 2019-10-09 08:30:00
    本文经授权转载自微信公众号:小争哥(xiaozhengge0822),作者:小争哥数组和链表作为最基础的数据结构,在面试的时候,经常会被问到。最常被问到的一个问题,那就是...
  • 1、内存中开辟空间:  C语言中:全局、域、堆空间(malloc/new) 组织形式:  a、连续内存空间:申请... 时间复杂度:耗费时间 与数据量关系  空间复杂度:额外占有内存与数据量关系  for(i=0;i&lt;1...
  • 折半查找对链表而言根本不能达到O(logN)的效率。只有当访问集合中任何一个元素...是常量O(1)时间时,折半查找才能达到O(logN),而链表访问其中元素的平均时间是O(N)即 线性时间。对用数组构造的集合才能使用折半查找。
  •     如题,这是我在看数据结构中链表的时候产生的疑惑。     其实,这源于对链表认识不够深刻。...所以链表插入,并不会像顺序线性表一样,指定一个下标,然后插入,而是
  • 单链表插入删除操作的时间复杂度

    千次阅读 2019-11-10 10:31:23
    单链表相比数组的优势在于插入删除元素快,不需要移动大量的元素,只需要改变指针的指向,那么插入删除操作的时间复杂度应该是O(1),但是这是不对的,应该分情况讨论。 单链表结构体声明: typedefstruct LNode { ...
  • 我们都知道: 数组是开辟一块连续的空间用来保存数据的。 链表是通过节点一个连一个来保存数据,更具...插入、删除元素 数组需要移动数据,链表只需要改变指针指向。 写的是自己的看法,可能不对,后续需要完善。 ...
  • 在实现队列的链表结构中,时间复杂度最优的是: 仅设置头指针的单循环链表 仅设置尾指针的单循环链表 仅设置头指针的双向链表 仅设置尾指针的双向链表 答案 2 前提:队列中的结点从队尾插入,从队头删除;队列中的结点...
  • 文章目录算法时间复杂度时间复杂度“大O记法”时间复杂度的基本计算规则常见时间复杂度之间的关系时间复杂度例子空间复杂度常见的空间复杂度空间复杂度举例时间复杂度与空间复杂度取舍数据结构之数组 算法 算法是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 87,405
精华内容 34,962
关键字:

链表插入的时间复杂度