线性表的实现分析
顺序存储和链式存储的对比:
顺序表 | 链表 | |
空间性能 | 顺序表的存储空间是静态分布的,需要一个固定长度的数组,因此总有部分数组元素被浪费。 | 链表的存储空间是动态分布的,因此不会产生空间的浪费。但是需要额外的空间来为每个节点保存引用。 |
时间性能 | 顺序表中元素的逻辑顺序和物理存储顺序是保持一致的,因此支持随机读取,在查找、读取方面性能较好。 | 链表采用链式结构存储数据,因此在插入、删除元素时性能较好。 |
如下图:
线性表是增强版数组:
从某种程度上来讲,线性表是数组的加强:
- 线性表的长度可以动态改变,但Java数组的长度是固定的;
- 线性表可以插入元素,数组无法插入元素;
- 线性表可以删除元素,数组无法删除元素,只能将指定元素置为null或者0;
- 线性表可以搜索指定元素的位置,数组一般没有此方法;
- 线性表提供方法来清空所有元素,数组一般没有类似方法
JDK提供的线性表:
其中,ArrayList就是顺序线性表,LinkedList就是链式线性表。对于初学者,只要会使用JDK提供的线性表即可,可以查看下相关的源码,对其实现原理有所了解,待小有所成后,可以自己动手编写线性表的实现。
相关推荐
线性表的实现:插入,删除等操作
线性表分析及Java实现
此代码主要是实现线性表的链式的相关操作,建议程序执行前先分析代码,再做相关的操作。
要求完成两个同样功能的程序,一个程序采用顺序存储结构,另一个程序采用链表实现线性表的存储。其中链表实现时,要求利用两个升序链表的结点实现归并,即归并时不能新建结点,归并后原来两个升序链表的存储空间不在...
数据结构和算法分析中的链表 和线性表的实现
关于数据结构的教程,详细实例很多. 任务2.1 线性表的逻辑结构; 任务2.2 线性表的顺序存储结构;...任务2.3 顺序表的基本操作的实现; 任务2.4 线性表的链式存储; 任务2.5 链表的基本操作; 任务2.6 改进的链式存储。
数据结构与算法(五)线性表的应用案例分析实现 定义线性表节点的结构.pdf
此代码主要是线性表的顺序实现,操作者先分析代码,在进行相应的操作。
数据结构之线性表- 一元稀疏多项式计算器 这个我就不用介绍了吧
2.4 线性表的应用:一元多项式的表示及运算2.4.1 一元多项式的表示2.4.2一元多项式的实现其中一元多项式代码在VS13中运行无误。
试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1,a2...,an)逆置为(an,an-1,...,a1)。 选题9:(难)单链表拆分。 将带头结点的单链表LA中分拆成LB和LC两条单链表,LA中的data域...
数据结构 C语言 线性表 实验报告 原代码和实验报告
试分别以不同的存储结构实现线性表的就地逆置法,即在原表的存储空间中将线性表(a1,a2,...,an)逆置为(an,...,a1)。 (1)以顺序表作存储结构,设线性表存储于a[1:arrsize]的前elenum个分量中。 (2)以...
在C语言描述的数据结构与算法分析中,如何实现链式存储的线性表和运算
用VC编写的线性表就地逆置,赫夫曼树,快速排序的代码的实验报告
本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下: 插入、删除结点的代码有点多,但这样提高了代码的可读性,且不增加时间复杂度,不会影响程序性能 #include using ...
C语言 定义单链表的结点类型 对单链表的一些基本操作
对于一篇给定的英文文章,分别利用线性表和二叉排序树来实现单词频率的统计,实现低频词的过滤,并比较两种方法的效率。 实习要求: 1. 读取英文文章文件(InFile.txt),识别其中的单词。 2. 分别利用线性表和...
存储结构分为两种,线性表的这两种存储结构在时间复杂度上各有特色,若在操作中涉及遍历、查找较多的话,则宜用顺序存储结构;若涉及插入、删除较多的话,则宜用链式存储;具体选择哪一种存储结构要根据需要进行的...