动态链表的创建

时间:2022-12-04 16:57:00

一、内存的两种访问方式


1、随机访问方式

对于数组来说,他的所有元素在内存中是连续存储的,因而很容易计算出每个元素的内存地址,从而可以直接访问数组中的任意一个元素。


2、顺序访问方式

对于链表来说,不同的结点在内存中存储的位置是随机的,因而无法计算出每个结点的内存地址,从而只能从第一个结点开始依次访问。

因此,需要将第一个结点的地址保存起来。


二、如何保存第一个结点的地址?

1、带头结点的链表

若是将第一个结点的地址存储到一个专门的结点的指针域中,那么这种链表称为带头结点的链表。


动态链表的创建

这个专门的结点称为头结点,头结点的数据域中不存储任何有效数据。

这种链表也有头指针,不过此时的头指针变量中存储的是头节点的地址。

看起来头结点似乎多余,实际上引入头结点能够简化链表的创建、插入和删除等操作。


为何要创建一个函数

原因:需要返回头指针的地址,便于后面遍历、删除等操作


动态链表的创建


动态链表的创建

时刻谨记这张图!

因为指针p一直表示末指针,所以创建一个新指针,利用之后,此刻就变成了末指针