对迄今为止学到的线性列表进行时间复杂度分析总结的顺序记忆结构线性列表的最大问题是插入和删除大量的要素,对效率产生了很大的影响。 为了提高效率,引出逻辑结构上相连但物理结构上没有相连的存储方式——链式存储结构。
定义链存储结构
创建一个结构,该结构不仅需要存储数据元素本身的信息,还需要存储每个数据元素与其直接相连的元素之间的逻辑关系。 下图:
在这里,ai和ai 1是线形表的2个邻接的数据要素,但是他们在物理存储器上并不邻接。
链存储结构的逻辑结构
在基于链接存储结构的线性表中,每个节点都有一个存储数据元素本身的数据域和一个存储相邻节点地址的指针域,让我们来看看内存中更直观的链接存储结构图。
上图显示了链表中节点在内存中的地址不是连续的。
链表的分类
链表可以分为单链表、循环链表、双向链表。
链表:每个节点只包含直接跟随的地址信息。
循环链表:单链表中最后一个节点的直接后继是第一个节点。
双向链表:单链表的节点包含直接前驱和后续地址信息。
链表的概念
头节点:链表的辅助节点,只包含指向第零个数据元素的指针,没有数据信息。 头节点始终指向第0个元素,因此可以很容易地在运行时定位元素。
数据节点:表示链表中数据元素的节点,表示为数据域和指针域。
尾部节点:存储在尾部节点中的地址信息可用于区分链表的类型。 空:单链表。 第0个节点地址:循环链表。 随机值:不正确的链表。
单链表的节点定义
struct node : publicobject { tvalue; Node* next; (;
该节点从顶级父类Object继承。
包含通用变量。
指向Node结构的指针变量。
成员变量是公共访问级别。
链表的插入操作
从第一个节点开始,用当前指针定位到要插入的目标位置
从堆空间请求新节点以初始化数据域
执行插入操作。
操作图:
链表的删除操作
从开头节点开始,用current指针定位到目标位置
使用toDel指针指向要删除的节点
执行删除操作
操作图:
总结:
链表中的数据元素不与物理内存相邻。
链表中的节点包括数据域和指针域。
头节点用于辅助放置数据元素,便于插入和删除。
插入和删除操作必须保证链表的完整性。