链接列表

C 语言没有定义链表数据结构。如果你使用 C 并需要链接列表，则需要使用现有库（例如 GLib）中的链接列表或编写自己的链接列表界面。本主题显示链接列表和双链表的示例，这些列表可用作编写自己的链接列表的起点。

单链表

该列表包含由一个名为 next 的链接组成的节点。

数据结构

struct singly_node
{
  struct singly_node * next;
};

双重链表

该列表包含由两个名为 previous 和 next 的链接组成的节点。链接通常引用具有相同结构的节点。

数据结构

struct doubly_node
{
  struct doubly_node * prev;
  struct doubly_node * next;
};

Topoliges

线性或开放

圆形或环形

程序

绑定

将两个节点绑定在一起。

void doubly_node_bind (struct doubly_node * prev, struct doubly_node * next)
{
  prev->next = next;
  next->prev = prev;
}

制作循环链表

void doubly_node_make_empty_circularly_list (struct doubly_node * head)
{
  doubly_node_bind (head, head);
}

制作线性链表

void doubly_node_make_empty_linear_list (struct doubly_node * head, struct doubly_node * tail)
{
  head->prev = NULL;
  tail->next = NULL;
  doubly_node_bind (head, tail);
}

插入

让我们假设一个空列表总是包含一个节点而不是 NULL。然后插入过程不必考虑 NULL。

void doubly_node_insert_between
(struct doubly_node * prev, struct doubly_node * next, struct doubly_node * insertion)
{
  doubly_node_bind (prev, insertion);
  doubly_node_bind (insertion, next);
}

void doubly_node_insert_before
(struct doubly_node * tail, struct doubly_node * insertion)
{
  doubly_node_insert_between (tail->prev, tail, insertion);
}

void doubly_node_insert_after
(struct doubly_node * head, struct doubly_node * insertion)
{
  doubly_node_insert_between (head, head->next, insertion);
}