数据结构:数组、链表、栈、队列的理解

解释定义

数据结构:

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。再简单描述一下:数据结构就是描述对象间逻辑关系的学科。

如果还是不太清楚下面会举例说明的。

数据存储结构:

简单的讲就是数据在计算机中的存储方式。

常用的数据存储方式有两种:顺序存储,非顺序存储。顺序存储就是把数据存储在一块联系的存储介质(硬盘或内存等)中。反之就是非顺序存储咯。Java中的数组就是典型的顺序存储,链表就是非顺序存储。数组存储数据时会开辟出一块联系内存,按顺序存储。链表先不会开辟出一块内存来,而是只需要知道下一个节点存储的位置,就能把所以的数据连起来了。所以单向链表的最后一个节点是指向Null的。

数组、链表、栈和队列是最基本的数据结构,任何程序语言都会涉及到其中的一种或多种。

数组

数组是数据结构中很基本的结构,很多编程语言都内置数组。

在java中当创建数组时会在内存中划分出一块连续的内存,然后当有数据进入的时候会将数据按顺序的存储在这块连续的内存中。当需要读取数组中的数据时,需要提供数组中的索引,然后数组根据索引将内存中的数据取出来,返回给读取程序。在Java中并不是所有的数据都能存储到数组中,只有相同类型的数据才可以一起存储到数组中。

所有的数据结构都支持几个基本操作:读取、插入、删除。

因为数组在存储数据时是按顺序存储的,存储数据的内存也是连续的,所以他的特点就是寻址读取数据比较容易,插入和删除比较困难。简单解释一下为什么,在读取数据时,只需要告诉数组要从哪个位置(索引)取数据就可以了,数组会直接把你想要的位置的数据取出来给你。插入和删除比较困难是因为这些存储数据的内存是连续的,要插入和删除就需要变更整个数组中的数据的位置。举个例子:一个数组中编号0->1->2->3->4这五个内存地址中都存了数组的数据,但现在你需要往4中插入一个数据,那就代表着从4开始,后面的所有内存中的数据都要往后移一个位置。这可是很耗时的。

链表

在java中创建链表的过程和创建数组的过程不同,不会先划出一块连续的内存。因为链表中的数据并不是连续的,链表在存储数据的内存中有两块区域,一块区域用来存储数据,一块区域用来记录下一个数据保存在哪里(指向下一个数据的指针)。当有数据进入链表时候,会根据指针找到下一个存储数据的位置,然后把数据保存起来,然后再指向下一个存储数据的位置。这样链表就把一些碎片空间利用起来了,虽然链表是线性表,但是并不会按线性的顺序存储数据。

由于链表是以这种方式保存数据,所以链表在插入和删除时比较容易,读取数据时比较麻烦。举个例子:一个链表中0->1->2->3->4这五个内存地址中都存了数据,现在需要往2中插入一条数据,那么只需要更改1号和2号中记录下一个数据的位置就行了,对其他数据没有影响。删除一条数据与插入类似,很高效。但是如果是想要在链表其中取出一条数据,就需要从0号开始一个一个的找,直到找到想要的那条数据为止。

链表中插入

链表中删除

栈是一种先进后出的数据结构,数组和链表都可以生成栈。当数据进入到栈时会按照规则压入到栈的底部,再次进入的数据会压在第一次的数据上面,以此类推。

在取出栈中的数据的时候会先取出最上面的数据,所以是先进后出。

由于数组和链表都可以组成栈,所以操作特点就需要看栈是由数组还是链表生成的了,然后就会继承相应的操作特点。

队列

队列是一种先进先出的数据结构,数组和链表也都可以生成队列。当数据进入到队列中时也是先进入的在下面后进入的再上面,但是出队列的时候是先从下面出,然后才是上面的数据出,最晚进入的队列的,最后出。

举个简单的例子:可以把栈和队列看成是两根管子,这两根管子是用来存储数据的,有可能是数组生成的也有可能是链表生成的,栈的这根管子有一头是封死的,所以像这个管子放数据只能从一个口进,拿出数据的时候也只能从这一个口拿出来。而队列这根管子呢两个口都是敞开的,一个口负责进数据,另一个口负责出数据,所以从一进口先进去的数据,在出口处会先被拿出来。

另外栈和队列其实是可以互相转换的。后续再把代码的例子补上,太晚了,先写到这吧。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏成长道路

java常用对象

boolean b=Pattern.matches("(86)*0*1\\d{10}",mobile);//大陆手机号码的匹配 日期类 Date date =...

24700
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 五、高阶函数

314100
来自专栏上善若水

s002android逆向安全初级篇之android smali语法总结

smali中有两类数据类型:基本类型和引用类型。 引用类型是指数组和对象,其他都是基础类型。

26240
来自专栏Pythonista

封装与扩展性

封装在于明确区分内外,使得类实现者可以修改封装内的东西而不影响外部调用者的代码;而外部使用用者只知道一个接口(函数),只要接口(函数)名、参数不变,使用者的代码...

10030
来自专栏Java 源码分析

数据结构Stack

​ 在很多应用中,我们需要维护多个对象的集合,这种操作非常简单。我们可能想要向集合中 加入某个元素,去掉某个元素,以及遍历 集合中的元素并对他们执行某种操...

34160
来自专栏黑泽君的专栏

【Java面试复习经典】传智播客Java就业班入学测试题及答案解析(2012年版)

  共50道题,每道题2分,总分100分,80分为合格。   注意,题目有多选,也有单选。请认真作答。

19330
来自专栏张善友的专栏

C# 4.0 Optional Parameters 和Named Parameters

Optional Parameters 是C# 4.0的特色之一,可减少重载函数的数量,却可达到相同的效果,加快开发效率。在使用上就跟C++一样,只需用等号为函...

21670
来自专栏北京马哥教育

对Python老司机99%有帮助的简明语法总结乱编

本文由马哥教育Python实战开发班6期学员推荐,转载自互联网,作者为赖笔小新,感谢作者的辛苦付出和贡献。 最近发现进入python群的朋友都在你是如何自学py...

32170
来自专栏架构之路

Java 中冷门的 synthetic 关键字原理解读

看JAVA的反射时,看到有个synthetic ,还有一个方法isSynthetic() 很好奇,就了解了一下: 1.定义 Any constructs int...

36750
来自专栏程序你好

C# 7.3新特性一览

10730

扫码关注云+社区

领取腾讯云代金券