轻松驾驭数据结构04线性表链式存储结构 [复制链接]

前面研究了线性表的顺序存储结构，它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此，线性表访问元素的时间复杂度为O(1)。由于线性表逻辑关系上相邻的元素在物理位置上也相邻，线性表在作插入或删除元素时，需要移动大量元素，其时间复杂度为O(n)，其中n为线性表的长度。

链式存储结构

线性表也可以采用链式存储结构来存储线性表元素，链式存储结构不要求逻辑上相邻的两个元素在物理位置上也相邻，因此在插入或删除线性表元素时，不需要移动大量元素。由于线性表各元素的存储单元不再是连续的存储空间，无法在物理位置上表示元素间的逻辑关系，因此需要在线性表元素中增加额外的信息来存储元素间的逻辑关系。

线性表元素除了存储元素本身的信息之外，还需要存储一个指向其后继元素的信息，通过该信息可以获取其后继元素的存储位置。这两部分信息构成了线性表数据元素的存储映象，称为节点。它包括两个域，一个是存储元素本身信息的域称作数据域名；一个是存储直接后继元素存储位置的域称作指针域，指针域中存储的信息称作指针域（见图2-2）。n个节点链接成一个链表，称为线性链表，当节点只包含一个指针域时，称为线性链表，也称为单链表。

图2-3给出了单链表结构，整个链表的存取必须从头指针开始，头指针指示链表中第一个节点的存储位置。由于最后一个数据元素没有直接后继，因此线性单链表中最后一个结点的指针为空（NULL）。

例如，使用单链表存储下面的线性表。

｛北京，济南，成都，西安，上海，昆明｝

用链表结构存储线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，逻辑上相邻的两个元素其物理存储位置不要求紧邻，因此这种结构称为非顺序存储结构或链式存储结构。