文档章节

数组和链表的区别

toddler
 toddler
发布于 2015/01/05 21:31
字数 938
阅读 136
收藏 4

数组和链表的区别

  • 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少或不插入和删除元素,就应该用数组。

  • 链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

   *C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。
  (1) 从逻辑结构角度来看
     a, 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。
     b,链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
  (2)从内存存储角度来看
     a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。
     b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

 -----介绍的很详细,简单但有些地方容易忘,所以转过来和大家一起分享!

转自:http://www.cnblogs.com/FCWORLD/archive/2010/11/20/1882391.html

--------------------------------------------------------------------------------------------------------------------

备注:

个人理解,联想下生活中的例子便于理解记忆。

数组--->就像一列火车,有着车厢编号,每一节车厢里又有座位,座位也有编号,这就像二维数组。

              火车每一节之间是固定的,不便于拆分插入新的车厢,如果插入新的车厢,受影响的车厢都要更改编号,这很像                 修改数组的脚标。

链表--->更像是我们排队,只需要记住我在谁的后边,谁在我的后边就可以了。基于指针,方便插入、删除数据。但链表连接的内容可以在内存中不连续,因为依赖于指针。

            

© 著作权归作者所有

toddler
粉丝 13
博文 33
码字总数 21659
作品 1
济南
QA/测试工程师
私信 提问
【数据结构】数组、链表、队列、栈的区别和联系

目录 本文主要总结下数组、链表、队列、栈的区别和联系。 其实将这四个数据结构放在一起比较不是非常合适: 联系: 这四种数据结构都是线性表数据结构。 区别: 数组与链表是更加偏向数据存储...

写代码的木公
09/09
0
0
聊一聊前端算法面试——链表和数组

写在前面 今天来聊一聊前端面试中非常基础的两种数据结构——「数组」和「链表」。 先看下几个常见的面试题: 谈一谈链表和数组的区别 如何反转单向链表 在数组中找出三个数,使得它们的和为...

慕晨同学
09/01
0
0
java并发队列之ArrayBlockingQueue、LinkedBlockingQueue

ArrayBlockingQueue和LinkedBlockingQueue用法上没有什么区别,所以就放在一起把。 特点:阻塞队列,ArrayBlockingQueue定义时需要给定长度(有界队列),LinkedBlockingQueue定义时可给可不...

朝如青丝暮成雪
05/31
11
0
ArrayList、linklist、list的区别

List是一个接口,ArrayList和LinkedList是两个实现类,他们实现的方式不一样,其实LinkedList才是真正的链表(如果不清楚什么是链表,需要了解一下相关数据结构的知识,这不是一两句话能说清楚...

随智阔
2014/03/04
34
0
数据结构篇之链表1-链表的概念

近期为了面试做准备,复习了下关于链表的一些知识点,做个记录~ 首先何谓链表? 链式存储的线性表,简称链表。链表由多个链表元素组成,这些元素称为节点。结点之间通过逻辑连接,形成链式存...

青雨001
2018/11/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

分页查询

一、配置 /*** @author beth* @data 2019-10-14 20:01*/@Configurationpublic class MybatisPlusConfig { @Bean public PaginationInterceptor paginationInterceptor(){ ......

一个yuanbeth
21分钟前
2
0
在LINQPad中使用Ignite.NET

LINQPad是进行.NET开发的一款优秀工具,非常有利于Ignite.NET API的快速入门。 入门 下载LINQPad:linqpad.net/Download.aspx,注意要选择64位操作系统的AnyCPU版本; 安装Ignite.NET的NuGet...

李玉珏
34分钟前
2
0
JS其他类型值转化为Boolean类型规则

本文转载于:专业的前端网站➤JS其他类型值转化为Boolean类型规则 由于最近在笔试的时候,发现好多关于其他类型转化为Boolean类型的题目,因此总结一下! 一、String类型转化为Boolean 1.转化...

前端老手
45分钟前
5
0
EurekaClient自动装配及启动流程解析

在上篇文章中,我们简单介绍了EurekaServer自动装配及启动流程解析,本篇文章则继续研究EurekaClient的相关代码 老规矩,先看spring.factories文件,其中引入了一个配置类EurekaDiscoveryClie...

Java学习录
51分钟前
9
0
析构函数是否必须为虚函数?为何?

p517 在C++中,基类指针可以指向一个派生类的对象。如果基类的析构函数不是虚函数,当需要delete这个指向派生类的基类指针时,就只会调用基类的析构函数,而派生类的析构函数无法被调用。容易...

天王盖地虎626
51分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部