精华内容
下载资源
问答
  • 浅谈单链表与双链表区别

    万次阅读 多人点赞 2018-05-06 01:23:49
    面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度...

    昨天面试官面试的时候问了我一道关于链表的问题:情境如下

    面试官:请说一下链表跟数组的区别?

    我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

    根据以上分析可得出数组和链表的优缺点如下:

     

    数组的优点

    • 随机访问性强(通过下标进行快速定位)
    • 查找速度快

    数组的缺点

    • 插入和删除效率低(插入和删除需要移动数据)
    • 可能浪费内存(因为是连续的,所以每次申请数组之前必须规定数组的大小,如果大小不合理,则可能会浪费内存)
    • 内存空间要求高,必须有足够的连续内存空间。
    • 数组大小固定,不能动态拓展

    链表的优点

    • 插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)
    • 内存利用率高,不会浪费内存(可以使用内存中细小的不连续空间(大于node节点的大小),并且在需要空间的时候才创建空间)
    • 大小没有固定,拓展很灵活。

    链表的缺点

    • 不能随机查找,必须从第一个开始遍历,查找效率低

     

    面试官:那请说一下单链表和双链表的区别?

     

    我:

    单链表只有一个指向下一结点的指针,也就是只能next
    双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点,顾名思义,单链表只能单向读取

    面试官:从你的描述来看,双链表的在查找、删除的时候可以利用二分法的思想去实现,那么这样效率就会大大提高,但是为什么目前市场应用上单链表的应用要比双链表的应用要广泛的多呢?

    我:……这个我真的不知道,然后面试官就提醒我从存储效率上来考虑问题……

    我回来后百度了下,发现网上的回答大都是关于链表的代码实现的,并没有关于链表本质深层次的分析,于是我便做以下分析:

    单链表与双链表的结构图如下:

    从以上结构可以得出双链表具有以下优点:

    1、删除单链表中的某个结点时,一定要得到待删除结点的前驱,得到该前驱有两种方法,第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后,重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的,指针的总的移动操作都会有2*i次。而如果用双向链表,则不需要定位前驱结点。因此指针总的移动操作为i次。

    2、查找时也一样,我们可以借用二分法的思路,从head(首节点)向后查找操作和last(尾节点)向前查找操作同步进行,这样双链表的效率可以提高一倍。

    可是为什么市场上单链表的使用多余双链表呢?

    从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这时一种工程总体上的衡量。

     

     

     

     

    展开全文
  • 单链表和双向链表的数据结构都包含指向下一个元素指针 next, 双向链表还包括指向上一个元素指针 previous 单链表只能向后遍历, 双向链表向前向后都可以遍历
    • 单链表和双向链表的数据结构都包含指向下一个元素指针 next, 双向链表还包括指向上一个元素指针 previous
    • 单链表只能向后遍历, 双向链表向前向后都可以遍历
    展开全文
  • c++实现单链表与双链表的基本操作,包含建立,插入,删除,遍历等。
  • Node环境下通过npm可以获取list的几个相关库,但是我们这里注重于自己动手实现,接下来就一起来看一下Node.js环境下JavaScript实现单链表与双链表结构
  • 单链表与双向链表

    2017-12-08 18:41:11
    单链表 链表中的数据是以节点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个...双向链表也叫双链表,是链表的一种,它的每个数据结
     
       单链表 
    

    链表中的数据是以节点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

    以"结点的序列"表示线性表称作线性链表(单链表)

    单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。

    双向链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

    关于单链表的代码

    #include<stdio.h>
    #include<stdlib.h>
    #define len sizeof(struct number)
    struct number{
    	int value;
    	struct number *left;                       
    	struct number *right;
    };          
    struct number * create(int n){
    	struct number *head;
    	struct number *p1,*p2;
    	p1=p2=(struct number*)malloc(len);//关于该函数的原型,在以前malloc返回的是char型指针,新的ANSIC标准规定,该函数返回为void型指针
    	if(p1->left==NULL){
    		head=p1;
    		scanf("%d%d",&p1->value,&p2->value);
    		p1->right=p2;
    	}
    	else{
    		p1=(struct number*)malloc(len);
    		scanf("%d",p2->value);
    		p1->right=p2;
    		p2->right=NULL;
    	}
    	return(head);
    }
    int main(){  
    	struct number *pt;
    	printf("单链表:");
    	pt=create();
    	system("pause");
    }



    展开全文
  • 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度...

    昨天面试官面试的时候问了我一道关于链表的问题:情境如下

    面试官:请说一下链表跟数组的区别?

    我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

    根据以上分析可得出数组和链表的优缺点如下:

     

    数组的优点

    随机访问性强(通过下标进行快速定位)
    查找速度快


    数组的缺点

    插入和删除效率低(插入和删除需要移动数据)
    可能浪费内存(因为是连续的,所以每次申请数组之前必须规定数组的大小,如果大小不合理,则可能会浪费内存)
    内存空间要求高,必须有足够的连续内存空间。
    数组大小固定,不能动态拓展


    链表的优点

    插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)
    内存利用率高,不会浪费内存(可以使用内存中细小的不连续空间(大于node节点的大小),并且在需要空间的时候才创建空间)
    大小没有固定,拓展很灵活。


    链表的缺点

    不能随机查找,必须从第一个开始遍历,查找效率低
     

    面试官:那请说一下单链表和双链表的区别?

     

    我:

    单链表只有一个指向下一结点的指针,也就是只能next
    双链表除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点,顾名思义,单链表只能单向读取


    面试官:从你的描述来看,双链表的在查找、删除的时候可以利用二分法的思想去实现,那么这样效率就会大大提高,但是为什么目前市场应用上单链表的应用要比双链表的应用要广泛的多呢?

    我:……这个我真的不知道,然后面试官就提醒我从存储效率上来考虑问题……

    我回来后百度了下,发现网上的回答大都是关于链表的代码实现的,并没有关于链表本质深层次的分析,于是我便做以下分析:

    单链表与双链表的结构图如下:

    从以上结构可以得出双链表具有以下优点:

    1、删除单链表中的某个结点时,一定要得到待删除结点的前驱,得到该前驱有两种方法,第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后,重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的,指针的总的移动操作都会有2*i次。而如果用双向链表,则不需要定位前驱结点。因此指针总的移动操作为i次。

    2、查找时也一样,我们可以借用二分法的思路,从head(首节点)向后查找操作和last(尾节点)向前查找操作同步进行,这样双链表的效率可以提高一倍。

    可是为什么市场上单链表的使用多余双链表呢?

    从存储结构来看,每个双链表的节点要比单链表的节点多一个指针,而长度为n就需要 n*length(这个指针的length在32位系统中是4字节,在64位系统中是8个字节) 的空间,这在一些追求时间效率不高应用下并不适应,因为它占用空间大于单链表所占用的空间;这时设计者就会采用以时间换空间的做法,这时一种工程总体上的衡量。

    原文:https://blog.csdn.net/kangxidagege/article/details/80211225
     

    展开全文
  • 主要为大家详细介绍了java实现单链表、双向链表的相关资料,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 单链表与双链表知识点:1.单链表双链表的定义需要注意的地方:检测耗费的时间:单链表双链表的关系手写c++中的LinkedList 具体代码请看:NDKPractice项目的datastructure 知识点: 1.单链表双链表的定义 ...
  • 我们这里采用的是不带头单链表和带头结点的循环双向链表供大家参考。 单链表 typedef struct SListNode { int data ; struct SListNode* next ; }SListNode ; //封装了一个指向链表节点指针的结构体,通过这个...
  • 循环单链表和双向链表的建立
  • 文章目录前言一、链表1.单链表2.双链表二、单链表1.成员变量2.getSize()和isEmpty()3.链表的虚拟头节点1.什么是链表的虚拟头结点2....本节讲述的是单链表与双链表基础方法的原理及实现,双链表将在单链表
  • 单链表与双链表知识点 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。...
  • java实现自己的单链表双链表、Map存储,java实现自己的单链表双链表、Map存储
  • 单链表与双链表

    2019-04-14 09:40:47
    链表:动态分配内存,内存不连续,定位元素时间复杂度O(N),插入或删除的时间复杂度O(1)。 优点: (1)插入或删除的速度快 (2)内存利用效率高,不浪费内存(可以不要求空间连续,而且在需要时才创建) (3)...
  • 单链表双链表区别

    千次阅读 2019-01-23 18:34:33
    双链表既有指向下一个结点的指针,也有指向上一个结点的指针 二、适用情况不同 单向链表更适合元素的增加删除 双向链表更适合元素的查询工作 三、读取不同 单链表只能单向读取 双链表可以双向读取 ...
  • 链表跟数组的区别: 数组随机访问性强(通过下标进行快速定位),查找速度快; 链表不能随机查找,必须从第一个开始遍历,查找效率低 数组插入和删除效率低(插入和删除需要移动数据), 链表插入删除速度快(因为有...
  • 单链表与双链表交换相邻结点比较 单链表结点结构体 typedef struct Listnode1{ //为单链表设置的结点结构体 int data; struct Listnode1 *next; }Listnode1; 双链表结点结构体 typedef struct Listnode2{ ...
  • 单链表 双链表
  • 一、单链表中的循环链表: 目前我们的链表最后一个结点的pNext指向的是NULL;循环链表中的最后一个结点的pNext指向的是头结点; 循环链表和不是循环链表区别:判断条件不一样! p->pNext == NULL; p->pNext ...
  • 文档包括带表头单链表的实现,双链表的操作,双链表的冒泡排序,不带表头的单链表,双向链表、链表节点的排序
  • 数组与链表 数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。 ...
  • 单链表与双链表一、前言二、单链表概念讲解三、单链表代码讲解add_head()函数insert()函数del()函数四、双链表 一、前言 在平时我们的作业中,我们有可能会遇到对于数组需要进行一个数或者是一批数的插入处理。在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,990
精华内容 13,996
关键字:

单链表与双链表的区别