既然我们这一节要说的是线性表与链表的内容,那么肯定要对数据结构的概念有一个认识。首先,数据结构一般分为逻辑结构、物理结构,逻辑结构指的是数据对象元素之间的相互关系,物理结构一般指的是数据的存储结构。逻辑结构主要包括集合结构、线性结构、树形结构、图形结构,物理结构主要有链式存储和线性存储。在数据结构的分析过程中,逻辑结构和物理结构是一种相辅相成的关系。
线性表的数据存储位置都是独立的、并且一个位置紧跟着下一个位置,在第 0 个位置上存储的数据是 a1、第一个位置上是 a2、以此类推,直到最后一个数据 an。假如说,要删除其中的一个数据 a2、那么紧接着 a3 就会移动到原来 a2 的位置、a4 就会移动到 a3 的位置,以至于最后 a2 之后的每一个数据都要向前移动一位,这也就使得线性存储的数据在删除的过程中效率会变得比较低。反之,线性存储结构存储数据时都是顺序存储的,没有指针对位置的指引操作,它的查询速度是相对比较快的。
和线性存储结构不同的是,链式存储结构可以在本身的数量中附加变量、利用附加变量指向前一个或者后一个数据,在进行插入、删除操作时只要改变数据的附加变量的指向就可以实现而不用改变前后数据的存储地址。比如:如果同样是删除 a2 数据的情况,在删除 a2 数据后 a1 的向后附加变量就会指向 a3、a3 的向前附加变量就会指向 a1,这样一来并没有改变 a2 数据以后的数据位置,只是改变了 a1、a3 的附加变量的数据位置指向。
在 Java 语言中,比较明显的线性表、链式表分别是 ArrayList、LinkedList,研究过 JDK 源码应该知道,这两种表分别都有的各自的添加、删除、查询方法,其两种表在实现这三种方法时也是截然不同的。下面我们分别拿出 ArrayList、LinkedList 的 add() 方法进行比较一下。注意:这里实例用的是 JDK1.8 源码展示。
// ArrayList 实现 add() 方法
publicbooleanadd(E e){
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// add() 方法没有指定添加的数据对象的位置
// 实现也比较简单,直接将数据对象赋值到数组中
// LinkedList 实现 add() 方法
publicvoidadd(int index, E element){
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
voidlinkBefore(E e, Node<E> succ){
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
本节就说到这里,以免大家视觉疲劳、源码部分有兴趣的猿童鞋可以自己深入研究。下一节我们看一下栈与队列的数据结构,记得关注后续更新、哈哈!
更多精彩关注微信公众号【老王说编程】>>>
相关推荐
数据结构中对象的定义,存储的表示及操作的实现. 2.线性:线性表、栈、队列、数组、字符串(广义表不考) 树:二叉树 集合:查找,排序 图(不考) 能力: 分析,解决问题的能力 过程: ● 确定问题的数据。...
该文档属于数据结构的一部分,其中包含数据结构绪论、算法、线性表、链表,可以为程序员系小白提供0基础学习资料,
从编写底层驱动的思路来编写了库,整个编写只为实现简单的链表结构代码,对于程序员来说,编写驱动要对用户自定义的任何数据都足够开放容纳,而对于用户来说,底层代码的实现要尽量封装隐秘。用户只需要会调用即刻。...
数据结构反映了数据元素之间的结构关系。链表是一种 A ,它对于数据元素的插入和删除 B 。 通常查找线性表数据元素的方法有 C 和 D 两种方法,其中 C 是一种只适合于顺序存储结构但 E 的方法;而 D 是一种对顺序和...
从编程的角度来看,数据结构与算法几乎是最朴素的基础知识了,这一关,是每一个立志当好程序员的必经之路。 为此,樊老师结合多年的工作经验,经过长时间的准备,精心打造了《数据结构基本原理与算法应用》课程,...
线性表综合题 (1) 按照输入的顺序建立顺序表 (2) 对顺序表进行排序(直接插入、冒泡、选择、快速、合并) (3) 按照由大到小的顺序建立一个单链表 (4) 链表逆置 (5) 将顺序表和链表合并成一个有序表。...
(2)下列数据结构中,能用二分法进行查找的是( )。A)顺序存储的有序线性表 B)线性链表C)二叉链表 D)有序线性链表 (3)下列关于栈的描述正确的是( )。A)在栈中只能插入元素而不能删除元素B)在栈中只能...
B)程序的测试必须由程序员自己去完成C)程序经调试改错后还应进行再测试 D)程序经调试改错后不必进行再测试(2)下列数据结构中,能用二分法进行查找的是A)顺序存储的有序线性表 B)线性链表...
9.1.1 线性表的定义及逻辑结构 9.1.2 线性表的基本操作 9.2 顺序存储结构 9.3 链式存储结构 9.3.1 单链表上的基本运算 9.3.2 循环链表 9.3.3 双向链表 9.4 线性表的分析 9.4.1 线性表的实现分析 9.4.2 ...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
》主要定位于有一定C/C++语言编程基础、想通过学习算法与数据结构提升编程水平的读者,也可作为具有一定编程经验的程序员以及大中专院校学生学习数据结构和算法的参考书。 第1篇 算法基础篇 1 第1章 算法概述 2 ...
• 数组(静态数组、动态数组)、线性表、链表(单向链表、双向链表、循环链表)、队列、栈、树(二叉树、查找树、平衡树、线索树、线索树、堆)、图等的定义、存储和操作 • Hash(存储地址计算,冲突处理) ...