`

数组和链表的关系

    博客分类:
  • C++
阅读更多
  • 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少或不插入和删除元素,就应该用数组。
  • 链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

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

(3)相同点:都是存储一组类型相同的数据。

 

本文参考:http://blog.csdn.net/rangf/article/details/8183718

分享到:
评论

相关推荐

    pythonlist是数组还是链表实现的-数组和链表结构(python)-1 数组和链表.pdf

    -数组和链表结构(Python)" Python列表是一个非常常用的数据结构,但是它究竟是数组还是链表实现的?在Python中,列表是使用链表结构实现的,但是在某些情况下,也可以使用数组结构来实现。那么,为什么Python列表...

    数组和链表的区别和优缺点总结 数组和链表.pdf

    3. 数组中的元素顺序关系由元素在数组中的位置确定,链表中的结点顺序关系由结点所包含的指针来体现 4. 对于不是固定长度的列表,使用可能最大的数组来描述,会浪费许多内存空间 5. 对于元素的插入、删除操作非常...

    数组和链表的区别和优缺点总结! 数组和链表.pdf

    * 数组中的元素顺序关系由元素在数组中的位置(即下标)确定,链表中的结点顺序关系由结点所包含的指针来体现。 使用场景: * 对于不是固定长度的列表,用可能最大的数组来描述,会浪费许多内存空间。 * 对于元素...

    数组和链表(使用场景和反转链表) 数组和链表.pdf

    数组和链表是两种基本且常用的数据结构,它们各有优缺点,适用于不同的场景。 数组是一种顺序存储结构,它在内存中占据一块连续的空间。数组的主要优点在于其随机访问的高效性,可以通过索引直接访问任意位置的元素...

    php数组和链表的区别总结 数组和链表.pdf

    在编程领域,数组和链表是两种常见的数据结构,它们各有优缺点,适用于不同的场景。在PHP这样的开发语言中,理解这两种数据结构的区别至关重要,有助于优化代码性能。 首先,我们从逻辑结构的角度来分析数组和链表...

    数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf

    数组、链表、堆栈和队列、线性表和顺序表 数组、链表、堆栈和队列是最基本的数据结构,任何程序都会涉及到其中的一种或多种。数据结构是指数据之间的相互关系,即组织形式,有逻辑结构和物理结构之分。逻辑结构有...

    java数组和链表数据结构的区别 数组和链表.pdf

    1. **插入和删除速度快**:链表的插入和删除操作只需改变元素之间的指针关系,而无需移动元素,时间复杂度通常为O(1)。 2. **内存利用率高**:链表可以根据需要动态地分配内存,不必像数组那样预设连续的内存空间,...

    [数据结构]数组与链表的优缺点和区别 数组和链表.pdf

    数组和链表是两种基本的数据结构,它们各自有其独特的优缺点,适用于不同的场景。下面将详细介绍这两种数据结构以及它们的区别。 首先,数组是一种线性数据结构,它将元素在内存中连续存放,每个元素占用相同的内存...

    数组和链表的理解,及各自的优缺点 数组和链表.pdf

    数组和链表是两种基本的数据结构,它们在存储和处理数据方面有着不同的特性和应用场景。 首先,数组是一种线性数据结构,它在内存中分配了一段连续的空间来存储相同类型的数据。数组的主要优点在于它的随机访问性能...

    数据结构顺序表、链表和数组是逻辑结构还是物理(存储)结构? 数组和链表.pdf

    在实际应用中,数组可以实现顺序表、链表和树等多种逻辑结构。顺序表、链表和数组之间的关系是非常复杂的,每种结构都有其特点和优缺点,需要根据实际情况选择合适的结构。 数据结构顺序表、链表和数组是逻辑结构...

    链表和数组的区别 (2) 数组和链表.pdf

    数组和链表是两种基本的数据结构,它们在存储和访问数据方面有显著的差异,各自具有独特的优点和适用场景。了解这些区别对于理解和优化算法至关重要。 首先,数组是一种线性的数据结构,其特点是所有元素在内存中是...

    数据结构的学习——数组和链表.zip

    本资料包“数据结构的学习——数组和链表.zip”着重讲解了两种基本的数据结构:数组和链表,它们在编程中扮演着核心角色,特别是在处理大量数据时。 数组是一种线性数据结构,其中的元素存储在内存中的连续位置。...

    顺序表和数组(易混淆),线性表,链表的区别与联系 数组和链表.pdf

    本节内容将对顺序表、数组、线性表、链表的概念和区别进行详细解释,并对它们之间的联系进行分析。 逻辑结构和物理结构的概念 ------------------------ 在讨论数据结构之前,需要首先弄清楚逻辑结构和物理结构的...

    数组表示循环链表约瑟夫环

    这种方法保证了无论m和n的关系如何,报数都会在数组范围内循环。 为了实现这个算法,我们需要以下步骤: 1. 初始化数组,每个元素代表一个节点。 2. 设置计数器为1,从虚拟头节点开始报数。 3. 当计数器达到m时,...

    练习题-数组双向链表.pdf

    1. **双向链表的初始化**:初始化时,数组中维护两个链表:“正在使用的链表”(Using链表)和“空闲链表”(Free链表)。其中Using链表的链表头是`array[1]`,Free链表的链表头是`array[0]`。初始化条件如下: ``...

    基于二维数组和十字链表的Apriori算法 数组和链表(02).pdf

    改进后的算法通过一次扫描数据库,结合二维数组和十字链表的数据结构,实现了更高效的频繁项集挖掘。实验结果显示,这种改进算法在运行效率上较其他算法有所提升,尤其是在处理大数据量时,内存占用得到有效控制。 ...

    线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf

    - 链表:如单向链表、双向链表和循环链表等。 - 栈:一种后进先出(LIFO)的数据结构,用于表达式求值、函数调用栈等。 #### 二、非线性结构 非线性结构指的是数据元素间的关系不是简单的线性关系,而是更复杂的...

    C语言培训 指针 数组 结构体 链表

    掌握C语言的关键在于理解和运用指针、数组、结构体和链表等核心概念。 **一、学习编程语言的一些建议** 1. **多动手**:编程实践是学习编程的最有效方式。通过编写和调试程序,可以深入理解语言的特性和工作原理。...

    图的数组,链表表示以及两种表示法的转换

    对于图的存储结构,有多种表示方法,其中较为常见的有两种:邻接矩阵(即数组表示)和邻接表(即链表表示)。下面将详细介绍图的数组表示。 #### 邻接矩阵 邻接矩阵是表示图的一种常用方法,它适用于稠密图。在...

Global site tag (gtag.js) - Google Analytics