返回目录

§2.3 单链表和循环单链表

§2.3.1 单链表的定义

用一个指针表示结点间的逻辑关系，单链表的一个存储结点包含两个部分：

  • data：数据域，用于存储线性表的一个数据元素，也就是说在单链表中一个结点存放一个数据元素。
  • next：指针域（链域），用于存放一个指针，该指针指向后继元素对应的结点，也就是说单链表中结点的指针用于表示后继关系。

单链表分为带头结点和不带头结点两种类型。

§2.3.2 单链表基本操作

初始化、销毁函数需要分配、释放内存。

整体创建单链表有头插法（简单，得到的相反）、尾插法（麻烦，得到的相同），复杂度O(n)\mathrm{O}(n)。

指定指针pp 处插入、删除O(1)\mathrm{O}(1)，但找到指定位置O(n)\mathrm{O}(n)。

§2.3.3 循环单链表

尾结点的 next 域指向头结点。

比如求约瑟夫环。

§2.3.4 双链表和循环双链表

双链表中用 两个指针 表示结点间的逻辑关系。

  • prior：指向其前驱结点的指针域。
  • next：指向其后继结点的指针域。

循环双链表可以直接从头向前走到尾节点，尾部操作都是O(1)\mathrm{O}(1)。循环双链表最聪明。

§2.3.5 顺序表与链表的比较

顺序存储结构

  • 优点：无须为表示线性表中元素之间的逻辑关系而增加额外的存储空间，存储密度大。具有 随机存储 特性。
  • 缺点：插入和删除操作需要移动大量元素。如果采用静态数组存储线性表元素，其 空间大小分配难以掌握，大大了会浪费空间，分小了易发生上溢出；如果采用动态数组存储线性表元素，其算法设计比较复杂。

链式存储结构

  • 优点：由于采用结点的动态分配方式，具有 良好的适应性。插入和删除操作只需修改相关指针域，不需要移动大量元素。
  • 缺点：为表示线性表中元素之间的逻辑关系而需要增加额外的存储空间（指针域），存储密度小。不具有随机存储特性。