数据结构基础：线性表学习笔记

1、线性表定义

线性表是指n个元素的有限序列(n>=0),通常用(a1,a2,a3...,an),来表示。

2、线性表特点

1、存在唯一的一个首元素

2、存在唯一一个尾元素

3、除第首元素外，每个元素只有一个直接前驱。

4、除尾元素外，每个元素只有一个直接后继。

3、线性表的存储结构

3.1 线性表的顺序存储

定义：线性表的顺序存储是指用一组连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理存储位置上也相邻。这种存储方式无需占用额外的存储空间来存储。

优点：可以随机读取 表中的元素。按照序号检索元素比较快。

缺点：插入、删除元素都需要移动元素。

3.2 线性表的链式存储

3.2.1 线性表的概念

定义：是节点来存储数据元素，元素节点的地址可以连续，也可以不连续。因此节点之间的元素的存储必须有逻辑关系。

元素节点：包含数据域、指针域（存储该元素的直接前驱、直接后继的位置信息）

优点：插入和删除操作不需要移动元素。、

缺点：只能顺序的读取元素，不能随机读取。

3.2.2 线性链表的分类

单链表：最后一个节点指针域为null

循环链表：最后一个指针域为指向第一个节点。因此循环链表可以从任意节点开始遍历整个链表。

双向链表：每个节点包含两个指针，分别指明当前元素的直接前驱和直接后继的存储信息。可以从两个方向遍历链表中的元素。

3.3  线性表顺序存储和链式存储比较