[数据结构笔记]线性表(一)
## 什么是线性表
线性表是零个或多个数据元素的有限序列。
线性表的抽象数据类型
ADT 线性表List
Data
线性表的数据对象集合为{a1,a2,....,an},每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个直接前驱元素,除了最后一个an外,每一个元素有且只有一个直接后续元素。数据元素之间的关系是一对一的关系。
Operation
// 初始化
// 判断线性表是否为空
// 清空线性表
// 返回某个位置的元素
// 判断是否存在某个元素,返回其位置
// 插入元素
// 删除元素
// 放回线性表的元素个数
endADT
线性表的顺序存储结构
线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。
Java里的ArrayList就是使用数组来实现的顺序存储。
顺序存储结构的优缺点
优点
不需要为表中元素之间的逻辑关系而增加额外的存储空间
可以快速地存取表中任一位置的元素
缺点
插入和删除需要移动大量的元素
当线性表长度变化较大时,难以确定存储空间的容量
造成存储空间”碎片”
线性表的链式存储结构
为了表示每个数据元素ai 与其直接后继数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域,指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像,称为结点(Node)。
n个结点(ai的存储映像)链结成一个链表,即为线性表(a1,a2,…,an)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表。
链表中第一个结点的位置叫做头指针。
用java语言来描述一个结点。
public class Node {
Object data;
Node next;
}
由上面的代码我们知道,结点由存放数据元素的数据域和存放后继结点地址的指针域组成。
java中的LinkedList就是使用链式存储结构实现。
单链表结构与顺序存储结构对比
如果线性表查找多,而插入删除少,适宜采用顺序存储结构。如果插入删除比较多,适宜采用单链表结构。
当线性表中的元素个数变化较大时或者根本不知道有多大时,最好采用单链表结构。