連結列表

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);
}