什么是节点、链表

为了解决顺序存储结构插入、删除元素时的不方便,我们需要让每一个元素除了存储数值之外,还要让其存储下一个元素的位置,那么存储数值的地方叫做数据域,存储下一个节点地址的地方就做指针域。这两个部分就组成了一个结点。

多了结点连成一个链表。即线性表的链式存储结构。如果链表中的每一个节点都只有一个指针域,那么该链表叫做单链表。

链表的组成

  • 首节点:第一个存放数据的有效节点
  • 尾节点:最后一个存放数据的有效节点,常用来判断单链表的结束位置。
  • 头结点:首节点之前的节点,数据域中没有内容,指针域存放着第一个有效节点的位置,不是链表必须的组成
  • 头指针:指向首节点或者头结点的指针变量,他是链表必须的组成
  • 尾指针:指向尾结点的指针变量

链表的特点

  • 链表的节点是离散存储的,每一个节点的位置不一定是紧挨着,可能离得很远
  • 结点之间通过指针相连
  • 每一个结点只有一个前驱或者后继结点
  • 每一个节点都有data域、指针域
  • 头结点根据需求可有可无
  • 节点中存放的数据类型是一样的

确定一个链表需要的参数

  • 头指针:它存放的是头结点的地址,可以找到头结点,头结点可以找到首节点

链表的分类

  • 单链表:尾结点和首节点没有接连
  • 双向链表:将终端结点的指针由空指针指向头结点
  • 循环链表:每个节点有两个指针域,一个域指向前一个节点,后一个域指向下一个节点,首尾节点也连接起来

各种链表图示

  • 空单链表

  • 无头结点单链表如下:

  • 有头结点单链表示意图

  • 空循环链表

  • 非空循环链表

  • 空双向链表

  • 非空双向链表

参考资料