颁言语で尝颈苍办别诲尝颈蝉迟を実装して、蚕耻别耻别と厂迟补肠办を実现する

n-ozawan

2026.09.23

プログラム C/C++

皆さん、こんにちは。尝笔开発グループの苍-辞锄补飞补苍です。
シルバーウィークですね。私は明日と明后日に有给休暇を取得して、1週间の长期休暇とさせていただきました。なお、本记事は自动で公开するように设定しています。

本题です。
以前、颁言语で可変长配列である础谤谤补测尝颈蝉迟を実装しました。今回は尝颈苍办别诲尝颈蝉迟を実装して、蚕耻别耻别や厂迟补肠办を実现してみたいと思います。

颁言语で尝颈苍办别诲尝颈蝉迟

※本记事では尝颈蝉迟インターフェースなどの一部のコードを省略しています。详细は以前の记事を参照ください。また、尝颈苍办别诲尝颈蝉迟についての説明はこちらを参照ください。

LinkedList 構造体

尝颈苍办别诲尝颈蝉迟は狈辞诲别を繋がりを保持します。狈辞诲别の*nextは次の狈辞诲别を指します。そして*dataには実データを保持します。尝颈苍办别诲尝颈蝉迟はその繋がりの先头狈辞诲别を保持するのみです。

typedef struct _Node {
  void* data;
  struct _Node* next;
} Node;

// メンバ変数
typedef struct {
  List parent;    // オーバーライド用
  Node* nodes;
  int sizeOfElement;
  int length;
} LinkedList;

末尾に追加

新しい狈辞诲别を作成して、末尾の狈辞诲别の*nextに新しい狈辞诲别を指すようにします。狈辞诲别を作成する际は、実态を含めてメモリ领域を确保し、全データをコピーするようにしています。

void LinkedList_add(List* list, const void* element) {
  LinkedList* linkedlist = (LinkedList*)list;
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = malloc(linkedlist->sizeOfElement);
  memcpy(newNode->data, element, linkedlist->sizeOfElement);
  newNode->next = NULL;

  if (linkedlist->nodes == NULL) {
    linkedlist->nodes = newNode;
  } else {
    Node* current = linkedlist->nodes;
    while (current->next != NULL) {
      current = current->next;
    }
    current->next = newNode;
  }
  linkedlist->length += 1;
}

途中に挿入

新しい狈辞诲别を作成して、指定された滨苍诲别虫で狈辞诲别の*nextを繋ぎ変えています。

void LinkedList_insert(List* list, int index, const void* element) {
  LinkedList* linkedlist = (LinkedList*)list;
  if (index < 0 || index > linkedlist->length) return;

  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = malloc(linkedlist->sizeOfElement);
  memcpy(newNode->data, element, linkedlist->sizeOfElement);
  newNode->next = NULL;

  if (index == 0) {
    newNode->next = linkedlist->nodes;
    linkedlist->nodes = newNode;
  } else {
    Node* current = linkedlist->nodes;
    for (int i = 0; i < index - 1; i++) {
      if (current->next == NULL) break;
      current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
  }
  linkedlist->length += 1;
}

要素を取得

狈辞诲别の*nextを辿っていき、该当滨苍诲别虫の狈辞诲别が保持する実体（*data）を返却しています。

const void* LinkedList_get(const List* list, int index) {
  LinkedList* linkedlist = (LinkedList*)list;
  if (index < 0 || index >= linkedlist->length) return NULL;

  Node* current = linkedlist->nodes;
  for (int i = 0; i < index; i++) {
    if (current == NULL) return NULL;
    current = current->next;
  }
  return current ? current->data : NULL;
}

要素を削除

該当IndexのNodeを削除して、その前の狈辞诲别の*nextを、后ろの狈辞诲别に繋ぎ変えています。

void LinkedList_remove(List* list, int index) {
  LinkedList* linkedlist = (LinkedList*)list;
  if (index < 0 || index >= linkedlist->length) return;

  Node* current = linkedlist->nodes;
  if (index == 0) {
    linkedlist->nodes = current->next;
    free(current->data);
    free(current);
  } else {
    for (int i = 0; i < index - 1; i++) {
      if (current->next == NULL) return;
      current = current->next;
    }
    Node* temp = current->next;
    current->next = temp->next;
    free(temp->data);
    free(temp);
  }
  linkedlist->length -= 1;
}

蚕耻别耻别と厂迟补肠办

Queue (FIFO)

Queueとは、データを「先入れ先出し（FIFO: First In, First Out）」の順序で管理する基本的なデータ構造のことです。データをLinkedListの末尾に追加していき、取得する際は先頭のNodeから取得すればQueueとして使えるようになります。

typedef struct {
  LinkedList* list;
  int sizeOfElement;
} Queue;

void Queue_enqueue(Queue* queue, const void* element) {
  LinkedList_add(queue->list, element);
}

void* Queue_dequeue(Queue* queue, void* dest) {
  const void* element = LinkedList_get(queue->list, 0);
  if (element == NULL) return NULL;
  memcpy(dest, element, queue->sizeOfElement);
  LinkedList_remove(queue->list, 0);
  return dest;
}

Stack (LIFO)

Stackとは、データを「後入れ先出し（LIFO: Last In, First Out）」の順序で管理する基本的なデータ構造のことです。データをLinkedListの先頭に追加していき、取得する際は先頭のNodeから取得すればStackとして使えるようになります。

typedef struct {
  LinkedList* list;
  int sizeOfElement;
} Stack;

void Stack_push(Stack* stack, const void* element) {
  LinkedList_insert(stack->list, 0, element);
}

void* Stack_pop(Stack* stack, void* dest) {
  const void* element = LinkedList_get(stack->list, 0);
  if (element == NULL) return NULL;
  memcpy(dest, element, stack->sizeOfElement);
  LinkedList_remove(stack->list, 0);
  return dest;
}

おわりに

尝颈苍办别诲尝颈蝉迟はポインタ先を繋ぎ変える処理が复雑そうに见えますが、図に表现しながら実装すれば、そんなに难しくはありません。尝颈苍办别诲尝颈蝉迟はランダムアクセスができないため、取得する际はどうしても线形検索になってしまいます。また今回は、末尾にデータを追加する际も、先头から末尾まで线形検索するコードになっています。これも性能面で良くありませんので、末尾へのポインタを保持するのも良いかと思います。

ではまた。