一、链表与数组
链表和数组是两种常见的基础数据结构。
链表若干个节点组成,每个节点将包含两部门:数据域和指针域;数据域用来存储数据元素,指针域用来存储下一个节点的地址。数组是除链表外另一常见的基础数据结构,它只鸥一个属性即它的大小。它们都是线形结构,是实现线形表ADT的两种方式。
链表和数组在存储数据时具有一个共同的特点,即所存储的数据必须均为同一类型。链表和数组最大的区别为:在物理结构即在内存中,数组是连续储存的,而链表是非连续的。
这种物理上的特性决定了这两种线形结构在逻辑上的差异。在逻辑上:数组使用时必须预先分配内存,链表在使用时则是按需分配;数组大小一旦确定就不能更改,链表的大小可以自由修改。数组在访问时非常方便迅速,可以看成是基本操作,但若要对一个数组进行插入、删除、增加等操作将会很麻烦,成本将很高;链表在每一次访问时都需要从头节点开始遍历,时间复杂度很高,但是对于链表中每一个节点进行编辑操作就很方便,只需要调整该节点的数据域和指针域即可。因此,在使用这两种数据结构时,应根据实际情况挑选适合的一种。一般对于一旦设定久基本无需更改、访问较多的数据结构采用数组更为理想;对于数据大小不确定或不断变化、编辑操作较多的数据结构采用链表更为理想。
三、链表与数组队列
1.队列:队列是一种特殊的线形表,特殊之处在于它只能在表的两端进行操作,且只能在队列的队尾进行插入,在队首进行删除。那么问题来了,我们的数组队列竟然可以在任意位置进行操作?所以我们这里应该是用数组模拟一个链表。
无论是使用链表还是使用数组,队列都需要具有以下功能:
add()//在队尾添加一个元素
get(int index)//获取制定位置的元素
delete(int index)//删除一个制定位置的元素
insert(int index,要插入元素的类型 要插入的元素)//在制定位置插入一个元素
length()//获取队列的长度
....
2.队列的实现
1)基于链表的实现
在创建链表前,首先必须为它创建一个节点类。节点类包含两个属性:存储的数据、指
向下一节点的指针。
2)基于数组的实现
由于数组大小在设定后是不可变的,所以我们可以定义一个新数组,再将原数组中的数据拷贝到新数组中,这样就模拟出了一个可自由操作的数组。但是需注意,这种方式的时间复杂度很好,当数据量很大时,性能将会很不好。
分享到:
相关推荐
循环链表队列的代码实现 循环数组队列的代码实现
队列关于数组与链表的实现, linux c语言
利用数组和链表实现队列的基本操作,如入队,出队,读出队首元素
python利用数组和链表实现栈和队列 数组和链表.pdf
go语言通过数组和链表的方式实现队列 数组和链表.pdf
数组、链表、队列、栈数据结构特点,各自优点和缺点 数组和链表.pdf
超级数组和链表及栈队列
数组、链表、堆栈和队列、线性表和顺序表 数组和链表.pdf
数据结构的定义 数据结构是计算机存储、组织数据的方式,用于高效地访问和修改数据。...Java提供了丰富的数据结构库,包括数组、链表、栈、队列等,这些数据结构为程序员提供了处理各种问题的工具和方法。
线性结构和非线性结构、稀疏数组、队列、链表(LinkedList) 数组和链表.pdf
数组、链表、队列、栈的区别和联系 数组和链表.pdf
完整代码 正确产生结果 三个类分开写 class linklist { protected: struct node { int data; node *next; }; node *head; int length; public:
常见的数据结构(栈、队列、数组、链表和红黑树) 数组和链表.pdf
经过一上午的学习,对数据结构有了新的认识和理解 数组 数组是由有限个相同类型的变量所组成的有序集合,它可以进行元素的插入、删除、查找等操作,它的物理存储方式是顺序存储,访问方式是随机访问,利用下标查找...
进行多项式运算,运用链表,队列,数组等数据结构。
在队列的代码中,引用了链表的代码
队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,只允许在表的后端(rear)进行插入操作,下面介绍一下java使用数组和链表实现队列的示例
c语言数组指定位置插入和删除-玩转C语言链表,单链表双向链表的建立遍历插入删除... 数组和链表.pdf
目录: 数据结构中的一些概念 栈(stack) 队列 链表 python中字典对象实现原理 数组 一....1、数据结构是什么 简单来说,数据结果就是设计数据以何种方式存储在计算机中 ...数据结构:数组、栈、队列、链表、树、图、
数据结构实验报告+代码(链表 二叉树 图 字符串 数组 排序 队列 栈)