链表1

线性表的链式表示与实现1

基本概念

线性表的链式表示又称为非顺序映像或链式映像

特点

• 链表中元素的逻辑次序和物理次序不一定相同

• 链表中的存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的

• 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等（顺序存取法）

链表结构

• 链式结构每个存储元素叫结点

1. 结点：由数据域和指针域组成

2. 数据域存储元素数值数据

3. 指针域存储直接前趋结点或后继节点的存储位置

• 链表：n个结点由指针链组成一个链表

• 每个链表都有头指针

  1. 单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名

• 头结点：是指在链表的首元结点之前附设的一个结点

• 首元结点：是指链表中存储第一个数据元素a1的结点

头结点的好处

1. 便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理

2. 便于空表和非空表的统一处理 无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

链表的种类

单链表

双链表

循环链表