[CS50] week5 - Data structures part1

初めに

今回は配列とポインタの違い、構造体（ノード）の生成や単方向・双方向リストの扱い方をまとめてみました。

このことを書いていいかはわかりませんが、よく誤解されるようで前置きとしてご説明させていただきます。

これまでの投稿（JavaScript関連の文章そして現在CS50の文章も）はあくまでも練習を兼ねて自分の勉強メモのつもりで書いています。メモの中身を提示するため一応タグでは書いておいたが、内容が多い場合勉強メモのタグは抜けています。

前にある方の文章では、投稿する行為自体は一種の自己アピールというのを目にしたけれど、自分としては練習のほうが一番の目的です。自己満足だと思われるかもしれないが、学んだことや自分の理解をこうして文章にできるのはもう十分嬉しいです。

参考文章でほぼ英語の文章を取り上げたのは、英語のほうが用語が統一されていることが多く、検索結果も例も多いのでキーワードや記録としてメモっています。初心者でありながら、このメモが少しお役に立てれば嬉しく思います。

日本語も英語も母語ではないので文法が間違ったり、変な解釈の仕方してしまった場合はあらかじめご了承ください。

Memo

データ構造での必要な基本機能：

• 生成（Create）
• 走査（Traverse）
• 捜査（Search）
• 挿入（Insert）
• 削除（Delete）

Big O：

malloc() in function：

incorrect example

void newArray(int *local, int size)
{
  local = (int *)malloc(size * sizeof(int));
}
int main()
{
  int *ptr;
  newArray(ptr, 10);
}

C言語で関数内部に引数を渡す方式はpass by value、値（アドレスも値の一種）をコピーして入れるということで、上例のように関数newArray()内部の変数int *localには関数main()のptrに保存されている値（何も指してない状態ではコンパイル時はNULLで初期化される）をコピーして入れる。この行為自体がsharing（アドレスの共有）とも呼ばれ、つまりlocalとptrと同じアドレスを指しているということです。

ここでlocalにmalloc()から新しいアドレスを与えるのは、localにほかのアドレスに指させるとのことだけでnewArray()が終了したら変数localも消滅され、結果としてptrには動的メモリを入れてもらえずlocalの消滅で保存されたアドレスも失くし、free()もできないままメモリリークが発生する。

correct example

void newArray(int **local, int size)
{
  *local = (int *)malloc(size * sizeof(int));
}
int main()
{
  int *ptr;
  newArray(&ptr, 10);
  free(ptr);
}

ダブルポインタlocalなら、ポイントptrのアドレス自体が保存されているので、*localを通してptrのアドレスへアクセスし、malloc()から割り当てられたアドレスを入れる。

（malloc()に明示的にキャストすべきかどうかは別の話ですので省きます。）

Storage

配列（Array）

連続メモリ（contiguous memory）

配列を格納するというのは配列の初めの要素のアドレスを格納することです。

#include <stdio.h>
int main(void)
{
  int numbers[4] = {10, 20, 30, 40};
  for (int i = 0; i < 4; i++)
  {
    printf("numbers[%d] value: %d; address: %p;\n", i, numbers[i], &numbers[i]);
  }
  return 0;
}
// numbers[0] value: 10; address: 0x7ffc338039b0;
// numbers[1] value: 20; address: 0x7ffc338039b4;
// numbers[2] value: 30; address: 0x7ffc338039b8;
// numbers[3] value: 40; address: 0x7ffc338039bc;

Array vs. Pointer vs. Double pointer）

&：アドレスを抽出する／パスする。
*：ポインタに格納されたアドレスを辿って、アドレスの保持している値をアクセスしパスする。

  int numbers[4] = {10, 20, 30, 40};

  // use "&" to extract the address
  printf("numbers array address (number[0]): %p\n", &numbers); // numbers array address (number[0]): 0x7ffd743960b0
  printf("numbers[0] address: %p\n", &numbers[0]); // numbers[0] address: 0x7ffd743960b0
  printf("numbers[1] address: %p\n", &numbers[1]); // numbers[1] address: 0x7ffd743960b4

  // use "*" to access the address and pass the value
  printf("value in numbers[0] address: %d\n", *numbers); // value in numbers[0] address: 10
  printf("value in numbers[1] address: %d\n", *(numbers + 1)); // value in numbers[1] address: 20

  // so we can reassign the value by using "*"
  *numbers = 100;
  *(numbers + 1) = 200;
  printf("value in numbers[0] address: %d\n", *numbers);  // value in numbers[0] address: 100
  printf("value in numbers[1] address: %d\n", *(numbers + 1));  // value in numbers[1] address: 200

配列を格納する変数はアドレスを格納するとのことで、ポインタに近い概念で*を使えばアドレスにある値をアクセスできるし、操作することもできます。

  // use a pointer to store the address of numbers
  // int *ptr = numbers;
  int *ptr;
  ptr = numbers; // ptr is a pointer variable, only can store address
  // we can pass array without "&", because "numbers" also store the first address of array
  // but if we pass a int ,char or pointer...etc, we have to use "&"

  printf("numbers array address (numbers[0]): %p\n", ptr); // numbers array address (numbers[0]): 0x7ffd743960b0
  printf("dereference(access) the address of numbers in ptr: %d\n", *ptr); // dereference(access) the address of numbers in ptr: 100
  printf("extract the address of ptr: %p\n", &ptr); // extract the address of ptr: 0x7ffd743960a8

ポインタにアドレスを預ける場合は&を使ってアドレスを提供する必要があるけれど、numbersのようにすでにアドレスを格納している変数なら、&使わなくてもアドレスをアサインすることができます。

ポインタptrに*を使うというのは、ptrに格納するアドレスを経由して、アドレスの持っている値をアクセスしてパスしたり操作したりすることで、配列の操作と似ているが、配列は長さにかかわらず連続メモリで、ポインタは参照先が一つのメモリか連続メモリの初めのアドレスでも保存できます。概念上は変わらないけれど使い方が違います。

（なぜextractという言葉を使うのか、私の理解では&でアドレスをパスするのはアドレスに入ったのでなく、一つのメモリには型、値、変数名、アドレスなど持っているなか、ただ必要な部分つまりアドレスだけを抽出してパスするのです。しかし無くすわけではない。）

  // int **pp = &ptr; // pp is a double pointer, only can store address too
  int **pp;
  pp = &ptr;
  printf("extract the address of pp: %p\n", &pp); // extract the address of pp: 0x7ffd743960a0
  printf("pp store the address of ptr: %p\n", pp); // pp store the address of ptr: 0x7ffd743960a8
  printf("use * to access pp, so we can get the address in ptr: %p\n", *pp); // use * to access pp, so we can get the address in ptr: 0x7ffd743960b0
  printf("use ** to access the address in ptr (numbers[0]): %d\n", **pp); // use ** to access the address in ptr (numbers[0]): 100

そしてダブルポインタの理解ですが、これら図を作成する理由であり、最初は調べてもどう解釈しても何だかモヤモヤするところがあって、図にしてたら関係性を分かって、
**ppは実は*(*pp)のように、
初めは*ppでppの値（ptrのアドレス）へアクセスし、
*(*pp)でptrの値（ある変数のアドレス）を再びアクセスして値をパスする
...ということをやっと理解できました。

（ほかに気づいたことですが、pp(0x7ffd743960a0)>>ptr(0x7ffd743960a8)>>numbers(0x7ffd743960b0)、といったアドレスの順としては、配列のアドレスが後ろにしたのは一連のメモリロケーションを取るためだったと考えられます。もし先に取ってしまったら、この連続した空間を解放してもほかに割り当てしようとしても使いにくくなる気がします。）

下は多次元配列の逆参照（dereference）の演算についての参考文章です。

多次元配列（Multidimensional array）

多次元配列とポインタについても少し気になって、

  int x[10][20];
  char y[10][20];
  int z[10][20][30];
  printf("int x[10][20] size is %zu\n", sizeof(x));
  // int x[10][20] size is 800
  printf("char y[10][20] size is %zu\n", sizeof(y));
  // char y[10][20] size is 200
  printf("int z[10][20][30] size is %zu\n", sizeof(z));
  // int z[10][20][30] size is 24000

  int *px[10][20];
  char *py[10][20];
  int *pz[10][20][30];
  // the size of the pointer is 4 for 32-bit machine, or 8 for 64-bit machine
  printf("char* size is %zu\n", sizeof(char *));
  // char* size is 8
  printf("int* size is %zu\n", sizeof(int *));
  // int* size is 8
  printf("int *px[10][20] size is %zu\n", sizeof(px));
  // int *px[10][20] size is 1600
  printf("char *py[10][20] size is %zu\n", sizeof(py));
  // char *py[10][20] size is 1600
  printf("int *pz[10][20][30] size is %zu\n", sizeof(pz));
  // int *pz[10][20][30] size is 48000

ポインタのサイズは環境により変わっていく。ここのデモコードは CS50 の IDE でテストしたので 8 Byte でした。

ポインタは、同じ要素数の配列と比べると倍以上のサイズを占めているように見えるが、ここで2次元配列を例にしてみると、

  // two dimensional array
  // char fruits[][10] = {
  //     "apple",
  //     "banana",
  //     "orange"};
  // note: fruits[][] or fruits[4][] are invalid
  //
  char fruits[4][10] = {
      {'a', 'p', 'p', 'l', 'e', '\0'},
      {'b', 'a', 'n', 'a', 'n', 'a', '\0'},
      {'o', 'r', 'a', 'n', 'g', 'e', '\0'},
  };

  // char *pf[] = {
  //     "apple",
  //     "banana",
  //     "orange"};
  //
  char *pf[3];
  char *a = "apple";
  char *b = "banana";
  char *c = "orange";
  pf[0] = a;
  pf[1] = b;
  pf[2] = c;

  printf("address of first element in pf is %p\n", *pf);
  // address of first element in pf is 0x55e86451b06d
  printf("address of second element in pf is %p\n", *(pf + 1));
  // address of second element in pf is 0x55e86451b073
  printf("address of third element in pf is %p\n", *(pf + 2));
  // address of third element in pf is 0x55e86451b07a

  printf("address of pf is %p\n", &pf);
  // address of pf is 0x7ffd86ec3ea0
  printf("address of pf is %p\n", pf);
  // address of pf is 0x7ffd86ec3ea0

  printf("fruits size is %zu\n", sizeof(fruits));
  // fruits size is 40
  printf("pf size is %zu\n", sizeof(pf));
  // pf size is 24

ポインタは連続メモリの初め要素のアドレスだけ格納するので、多次元配列のように固定されたサイズの中でデータを格納するよりポインタ配列のほうは柔軟性があって無駄もありません。

そしてほかに気になることもあって、

  char fruits[4][10];
  fruits[0][0] = 'a';
  fruits[0][1] = 'p';
  fruits[0][2] = 'p';
  fruits[0][3] = 'l';
  fruits[0][4] = 'e';
  fruits[0][5] = '\0';

  // fruits[1] = "banana"; // string is also a array(pointer)
  // note: this action is error
  // it means you try to change the address of fruits[1]
  // we have to know "fruit[4][10]" had got an address each itself
  // when it declared.
  // in other words, we try to put multiple address in one address
  // it doesn't make sense.

  char *element2 = "banana";
  *fruits[1] = *element2; // ok, but this is meaningless

  // // char *strncpy(char *dest, const char *src, size_t n)
  // // copy source(string) into destination(array)
  // strncpy(fruits[2], "orange", 9);
  // // note: this may cause another problem
  // // if string is beyond the counting number
  // // strncpy() won't provide nul-terminate('\0').
  // // we have to restrict the counting number is less than element length
  // // and we have to initialize array by '\0' or add '\0' at the end of element
  // fruits[2][9] = '\0'; // add '\0' at the end of element

  // char *strncat(char *string1, const char *string2, size_t count);
  // string1 and string2 will be passed to an address
  char *element3 = "orange";
  fruits[2][0] = '\0';
  // printf("%lu\n", strlen(fruits[2])); // 0
  strncat(fruits[2], element3, 9);
  // printf("%lu\n", strlen(fruits[2])); // 6

  for (int i = 0; i < 3; i++)
  {
    printf("%s\n", fruits[i]);
  }
  // apple
  // b
  // orange

初心者である私は、fruits[1] = "banana";という書き方がなぜダメだったのかなと。上の図を作ってたら、実際配列の中身は一個一個ちゃんとした値が入っていて、ポインタは値のアドレスを格納するだけなので、ほかの値のアドレスを入れ替えても問題ないのはもちろんですが、配列の要素にほかのアドレスを入れることはできません。（そもそもアドレスは文字列配列に格納できる型でもなかった。pfのようにポインタの配列ならポインタを格納することはできる。）

配列とポインタ、データをストックする概念は全く一緒ではあるが、格納できるデータ型や扱い方の話になると全然違います。

そして特定の要素に文字列を入れるためにほかの方法も探ってみました。

元々strncpy()を使って書いてみたが、strncpy()の扱いにくいところを考えるとほかの方法も調べて、そして参考資料が述べたようにstrncat()のほうがより安全で、'\0'(nul-terminate)も自動的に入れてくれる。

単方向リスト（Singly linked list）

ノードとノードが片方向に繋がっているリスト構造。ノード自体は今のノードにあるデータと、次のノードのアドレスを格納するポインタで構成されている。

ここからのコードはほぼ模写、コメントは自分なりに書いたノートです。

// implement singly linked list
#include <stdio.h>
#include <stdlib.h>

struct Node
{
  int data; // value in current node
  struct Node *next; // next node address
};

void display(struct Node *node)
{
  while (node != NULL)
  {
    printf("%d\n", node->data); // access value
    node = node->next;          // go to next node address
  }
}

int main(void)
{
  // initialize nodes
  struct Node *head = NULL;
  struct Node *node2 = NULL;
  struct Node *node3 = NULL;
  struct Node *node4 = NULL;

  // allocate a memory of struct Node size, as struct Node pointer to store
  head = (struct Node *)malloc(sizeof(struct Node));
  node2 = (struct Node *)malloc(sizeof(struct Node));
  node3 = (struct Node *)malloc(sizeof(struct Node));
  node4 = (struct Node *)malloc(sizeof(struct Node));

  // assign value and connect
  head->data = 10;
  head->next = node2;

  node2->data = 20;
  node2->next = node3;

  node3->data = 30;
  node3->next = node4;

  node4->data = 40;
  node4->next = NULL; // the end of singly-linked list

  display(head);

  return 0;
}
// 10
// 20
// 30
// 40

参考文章でもネットで探せば構造体やノードの関連図はごまんとあると思いますが、やっぱりどこか足りないと感じて図も一緒に作成してみました。（自分の勉強メモのつもりで書いたもので、自分解釈の比重が多かったです。）

基本実装（Basic implementation）

• 一番目のノードの挿入
• 一番目のノードの削除
• 特定の値のサーチ
• データ全体の出力

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node *next;
} sllnode;

// insert element at the first
// ** (double pointer): store the address of pointer
void insertFirst(sllnode **head, int data)
{
  // allocate memory for the newNode
  sllnode *newNode = (sllnode *)malloc(sizeof(sllnode));
  // assign value
  newNode->data = data;
  // let the next node of newNode store the address of current head
  newNode->next = *head;

  // reassign the address of the newNode back to the argument
  *head = newNode;
}

// delete element at the first
void deleteFirst(sllnode **head)
{
  // store the address of the current head
  sllnode *temp = *head;

  // if the current head is pointing NULL
  if (*head == NULL)
  {
    printf("Linked list is empty, nothing to delete\n");
    return;
  }
  *head = (*head)->next;

  printf("\n%d deleted\n", temp->data);
  free(temp); // remember to free the removed element
}

// search element in linked list
// if we find the element is for insertion or deletion
// we should store the address of the linked list pointer by using **
void search(sllnode *node, int key)
{
  int position = 1; // the current position
  int flag = 0;     // find the element or not

  while (node != NULL)
  {
    if (node->data == key)
    {
      flag = 1;
      break;
    }
    node = node->next;
    position++;
  }

  if (flag)
  {
    printf("%d present at %d position\n", key, position);
  }
  else
  {
    printf("%d does not present anywhere\n", key);
  }
}

// display all element in linked list
void display(sllnode *node)
{
  printf("\nLinked list: \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n\n");
}

int main()
{
  sllnode *head = NULL;

  // use '&' to put the address of head
  insertFirst(&head, 10);
  insertFirst(&head, 20);
  insertFirst(&head, 30);
  insertFirst(&head, 40);
  insertFirst(&head, 50);

  // display or search function doesn't have to use '&'
  // they receive a data object(struct)
  display(head);

  search(head, 30);
  search(head, 100);

  deleteFirst(&head);

  display(head);

  return 0;
}
// Linked list:
// 50 40 30 20 10

// 30 present at 3 position
// 100 does not present anywhere

// 50 deleted

// Linked list:
// 40 30 20 10

ノードの挿入（Insertion）

最初：void insertStart(demoNode **head, int data)
最後：void insertLast(demoNode **head, int data)
任意：void insertPosition(int position, int data, demoNode **head)
これらを模写しながら上のdemoNode **headと、void display(demoNode *node)のdemoNode *nodeと、どう違うかに気になって、

上の例で簡潔に言うと、insertStart()はmain()で呼び出され、引数のheadポインタアドレス（&head）をinsertStart()関数内のdemoNode **headによってheadに保存させる。

newNode->next = *headの*headは実際の意味では*で引数のheadポインタアドレスへアクセス、最終的にNULLに辿り着いた。それでmain()のheadはNULLに指す必要もなくなり、*head = newNodeでは*でmain()のheadへ再びアクセスし、newNodeのアドレスに置き換えて、newNodeを指させる。

もう一つ気づいたことですが、insertStart()のnewNodeは自動記憶域で呼び出されたけど、malloc()でヒープから動的記憶域を獲得しているからfree()されるまで消えないということ。なのでdeleteメソッドでは削除するノードを最後にfree()しなければメモリリークになってしまうんですね。

最初の位置に挿入（Insertion at the beginning）

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node *next;
} demoNode;

void insertStart(demoNode **head, int data)
{
  // allocate memory to create a new node
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  // assign value
  newNode->data = data;
  // let "next" always store the current address of head
  newNode->next = *head;
  // let "head" pointer always store the current address of node as head element
  *head = newNode;
}

void display(demoNode *node)
{
  printf("Linked list: \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 15;
  head->next = node2;

  node2->data = 30;
  node2->next = NULL;

  display(head);
  insertStart(&head, 25);
  insertStart(&head, 50);
  display(head);

  return 0;
}
// Linked list:
// 15 30
// Linked list:
// 50 25 15 30

最後の位置に挿入（Insertion at the end）

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node *next;
} demoNode;

void insertStart(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

void insertLast(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));

  newNode->data = data;
  // newNode is the last element
  newNode->next = NULL;

  if (*head == NULL)
  {
    *head = newNode;
    return;
  }

  demoNode *temp = *head;
  while (temp->next != NULL)
  {
    temp = temp->next;
  }
  temp->next = newNode;
}

void display(demoNode *node)
{
  printf("Linked list : \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;

  insertStart(&head, 10);
  insertStart(&head, 20);
  insertStart(&head, 15);

  insertLast(&head, 5);
  insertLast(&head, 6);
  insertLast(&head, 11);

  display(head);
  return 0;
}
// Linked list : 
// 15 20 10 5 6 11

指定位置に挿入（Insertion at nth position）

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node *next;
} demoNode;

// calculate object size to prevent buffer bound issue
int calcSize(demoNode *node)
{
  int size = 0;
  while (node != NULL)
  {
    node = node->next;
    size++;
  }
  return size;
}

void insertStart(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;

  *head = newNode;
}

void insertPosition(int position, int data, demoNode **head)
{
  int size = calcSize(*head);

  // if position == 0, should use insertStart method
  // if position < 0, it is invalid
  // if position > size, it would cause buffer bound issue
  if (position < 0 || position > size)
  {
    printf("no place for insertion, or %d is a invalid position\n", position);
  }
  else if (position == 0)
  {
    // printf("position is %d, please use insertStart method\n", position);
    // return;

    // "**" has stored the address of pointer in variable "head"
    // so it doesn't have to use "&"
    // "*head" means go to access the address of pointer
    insertStart(head, data);
  }
  else
  {
    demoNode *temp = *head;
    demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
    newNode->data = data;
    newNode->next = NULL;

    // singly linked list have to following its order before insertion
    // temp already at the address of head, which means it has been moved
    // then we decrease the position and move onto the next node until nth
    while (--position)
    {
      temp = temp->next;
    }
    // before insertion, store the next node first
    newNode->next = temp->next;
    // connect temp and newNode
    temp->next = newNode;
  }
}

void insertLast(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = NULL;

  if (*head == NULL)
  {
    *head = newNode;
    return;
  }

  // always remember that we should not change the address stored in *head
  demoNode *temp = *head;

  while (temp->next != NULL)
  {
    temp = temp->next;
  }
  temp->next = newNode;
}

void display(demoNode *node)
{
  printf("Linked list: \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;
  insertStart(&head, 10);
  insertStart(&head, 20);
  insertStart(&head, 30);

  insertLast(&head, 5);
  insertLast(&head, 6);
  insertLast(&head, 7);

  insertPosition(0, 100, &head);
  insertPosition(-1, 100, &head);
  insertPosition(10, 100, &head);
  insertPosition(1, 100, &head);
  insertPosition(3, 100, &head);

  display(head);
  return 0;
}
// no place for insertion, or -1 is a invalid position
// no place for insertion, or 10 is a invalid position
// Linked list:
// 100 100 30 100 20 10 5 6 7

真ん中に挿入（Insertion at the middle）

int getCurrentSize(demoNode *node)
{
  int size = 0;

  while (node != NULL)
  {
    size++;
    node = node->next;
  }
  return size;
}

void insertMiddle(demoNode **head, int data)
{
  demoNode *temp;
  int size;
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;

  // if list is empty
  if (*head == NULL)
  {
    newNode->next = *head;
    *head = newNode;
    return;
  }
  // otherwise
  temp = *head;
  size = getCurrentSize(*head);
  int middle = (size % 2 == 0) ? (size / 2) : (size + 1) / 2;

  // traverse to the current middle position
  while (--middle)
  {
    temp = temp->next;
  }
  newNode->next = temp->next;
  temp->next = newNode;
}

int main(void)
{
  int input;

  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 15;
  node2->next = node3;
  node3->data = 30;
  node3->next = NULL;

  display(head);
  insertMiddle(&head, 1);
  display(head);
  insertMiddle(&head, 2);
  display(head);

  return 0;
}
// List: 10 15 30
// List: 10 15 1 30
// List: 10 15 2 1 30

ソートされたリストに挿入（Insertion in a sorted list）

demoNode *createNode(int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = NULL;
  return newNode;
}

void insertSortedList(demoNode **head, demoNode *newNode)
{
  // if head node is empty or greater than new node
  if (*head == NULL || (*head)->data >= newNode->data)
  {
    newNode->next = *head;
    *head = newNode;
    return;
  }

  // locate the node before insertion
  // make sure current head is not pointing NULL,
  // and next node value is less than new node
  demoNode *current = *head;
  while (current->next != NULL && current->next->data < newNode->data)
  {
    current = current->next;
  }
  // let new node connect next node first, then connect new node
  newNode->next = current->next;
  current->next = newNode;
}

int main(void)
{
  int input;

  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 15;
  node2->next = node3;
  node3->data = 30;
  node3->next = NULL;

  display(head);
  printf("Insert node value: ");
  scanf("%d", &input);
  insertSortedList(&head, createNode(input));
  display(head);

  return 0;
}
// List: 10 15 30
// Insert node value: 5
// List: 5 10 15 30

// List: 10 15 30
// Insert node value: 40
// List: 10 15 30 40

削除（Deletion）

最初の位置から削除（Deletion from the beginning）

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
  int data;
  struct Node *next;
} demoNode;

void deleteStart(demoNode **head)
{
  demoNode *temp = *head;
  // check list is empty or not
  if (*head == NULL)
  {
    printf("List is empty, nothing to delete");
    return;
  }

  // move head to next node
  *head = (*head)->next;
  printf("Delete: %d\n", temp->data);
  free(temp);
}

void display(demoNode *node)
{
  printf("List: \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 20;
  node2->next = node3;
  node3->data = 30;
  node3->next = NULL;

  display(head);
  deleteStart(&head);
  display(head);
  deleteStart(&head);
  display(head);

  return 0;
}
// List:
// 10 20 30
// Delete: 10
// List:
// 20 30
// Delete: 20
// List:
// 30

最後の位置から削除（Deletion from the end）

void deleteEnd(demoNode **head)
{
  // use temp to store the address of target
  demoNode *temp = *head;
  demoNode *previous;

  // check list exist or not
  if (*head == NULL)
  {
    printf("List is empty, nothing to delete");
    return;
  }

  // check the current node is the last one or not
  if (temp->next == NULL)
  {
    printf("%d delete\n", (*head)->data);
    *head = NULL;
    free(temp);
    return;
  }

  // traverse to the last node
  while (temp->next != NULL)
  {
    previous = temp;
    temp = temp->next;
  }

  previous->next = NULL;
  printf("%d deleted\n", temp->data);
  free(temp);
}

void display(demoNode *node)
{
  printf("List: \n");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  printf("%zu\n", sizeof(demoNode)); // 16

  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 20;
  node2->next = node3;
  node3->data = 30;
  node3->next = NULL;

  display(head);
  deleteEnd(&head);
  display(head);
  deleteEnd(&head);
  display(head);
  deleteEnd(&head);
  display(head);

  return 0;
}
// 16
// List:
// 10 20 30
// 30 deleted
// List:
// 10 20
// 20 deleted
// List:
// 10
// 10 delete
// List:
//

任意の位置から削除（Deletion from nth position）

int getCurrentSize(demoNode *node)
{
  int size = 0;
  while (node != NULL)
  {
    node = node->next;
    size++;
  }
  return size;
}

void deletePosition(demoNode **head, int nth)
{
  demoNode *temp = *head;
  demoNode *previous;

  int size = getCurrentSize(*head);

  if (nth < 1 || nth > size)
  {
    printf("%d is not a valid position at current list\n", nth);
    return;
  }

  // delete and free the first node
  if (nth == 1)
  {
    *head = (*head)->next;
    printf("Deleted: %d\n", temp->data);
    free(temp);
    return;
  }

  // traverse to the nth node
  while (--nth)
  {
    previous = temp;
    temp = temp->next;
  }

  // skip the nth node(temp), and connect the next node
  previous->next = temp->next;
  printf("Deleted: %d\n", temp->data);
  free(temp);
}

void display(demoNode *node)
{
  printf("Current List: ");
  while (node != NULL)
  {
    printf("%d ", node->data);
    node = node->next;
  }
  printf("\n");
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 8;
  node2->next = node3;
  node3->data = 15;
  node3->next = NULL;

  display(head);
  deletePosition(&head, 2);
  display(head);
  deletePosition(&head, 3);
  display(head);
  deletePosition(&head, 1);
  display(head);

  return 0;
}
// Current List: 10 8 15
// Deleted: 8
// Current List: 10 15
// 3 is not a valid position at current list
// Current List: 10 15
// Deleted: 10
// Current List: 15

指定する値によって削除（Deletion with specified value）

位置ではなく、値を指定して削除する。
一つの値を削除するなら各々のケースに分けて、

• Case1: リスト自体は存在しない。
• Case2: リストは存在するけどノード一つしかない。
  • Case2-1:ノードの持っている値はターゲットの値だったので削除されて、リストがエンプティになった。
  • Case2-2:ノードの持っている値はターゲットの値ではなかったため、見つからなかった。
• Case3: チェックを入れる。
  • 残りのリストでは指定の値が見つからない。
  • 残りのリストでは指定の値が見つかったらカウントする。
• Case4: 複数のターゲットが存在する。
  • Case4-1: 最初の位置に現れたため削除し、次のループに入る。
  • Case4-2: 最初ではない位置に見つかったので、リストを中断させないように前のノードと次のノードを連結してからターゲットを削除し、次のループに入る。

値の削除は難しかった...。

void deleteByValue(demoNode **head, int targetValue)
{
  demoNode *temp = *head;
  demoNode *previous;
  int count = 0;

  // Case1: no nodes in list
  if (temp == NULL)
  {
    printf("Case1: Empty List\n");
    return;
  }

  // Case2: one node list
  if (temp->next == NULL)
  {
    if (temp->data == targetValue)
    {
      *head = NULL;
      printf("Case2-1: Value %d is deleted, list is empty\n", targetValue);
      free(temp);
      return;
    }
    else
    {
      printf("Case2-2: Value %d is not found\n", targetValue);
      display(*head);
      return;
    }
  }

  // traverse the list to check
  // Case3: not found or counting present times
  while (temp != NULL)
  {
    if (temp->data == targetValue)
    {
      count++;
    }
    temp = temp->next;
  }

  if (count == 0)
  {
    printf("Case3: Value %d is not found\n", targetValue);
    return;
  }

  // traverse the list to find target
  // Case4: two or more target in list
  for (int i = 0; i < count; i++)
  {
    temp = *head;

    // case4-1: target is the first node
    if (temp != NULL && temp->data == targetValue)
    {
      *head = temp->next;
      printf("Case4-1: Value %d at the first node, deleted\n", targetValue);
      free(temp);
      continue;
    }

    // case4-2
    while (temp != NULL && temp->data != targetValue)
    {
      previous = temp;
      temp = temp->next;
    }
    previous->next = temp->next;
    printf("Case4-2: Value %d deleted\n", targetValue);
    free(temp);
  }
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;
  demoNode *node4 = NULL;
  // note: Case1: Empty List

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));
  node4 = (demoNode *)malloc(sizeof(demoNode));
  // note: Current List: 0

  head->data = 1;
  head->next = node2;
  node2->data = 1;
  node2->next = node3;
  node3->data = 3;
  node3->next = node4;
  node4->data = 2;
  node4->next = NULL;

  display(head);           // List: 1 1 3 2
  deleteByValue(&head, 5); // Case3: Value 5 is not found
  deleteByValue(&head, 2); // Case4-2: Value 2 deleted
  display(head);           // List: 1 1 3
  deleteByValue(&head, 1);
  // Case4-1: Value 1 at the first node, deleted
  // Case4-1: Value 1 at the first node, deleted
  display(head);           // List: 3
  deleteByValue(&head, 3); // Case2-1: Value 3 is deleted, list is empty
  deleteByValue(&head, 1); // Case1: Empty List

  return 0;
}

Deletion for alternate nodes

void deleteAlternateNode(demoNode *head)
{
  // if (head == NULL)
  // {
  //   return;
  // }
  // demoNode *previous = head;
  // demoNode *current = head->next;
  // while (previous != NULL && current != NULL)
  // {
  //   // skip and free current node
  //   previous->next = current->next;
  //   free(current);

  //   // moves to next node
  //   previous = previous->next;
  //   if (previous != NULL)
  //   {
  //     current = previous->next;
  //   }
  // }

  // recursion
  if (head == NULL)
  {
    return;
  }

  demoNode *target = head->next;
  
  if (target == NULL)
  {
    return;
  }

  head->next = target->next;
  free(target);
  // call itself until target point to NULL
  deleteAlternateNode(head->next);
}

int main(void)
{
  demoNode *head = NULL;
  demoNode *node2 = NULL;
  demoNode *node3 = NULL;
  demoNode *node4 = NULL;
  demoNode *node5 = NULL;

  head = (demoNode *)malloc(sizeof(demoNode));
  node2 = (demoNode *)malloc(sizeof(demoNode));
  node3 = (demoNode *)malloc(sizeof(demoNode));
  node4 = (demoNode *)malloc(sizeof(demoNode));
  node5 = (demoNode *)malloc(sizeof(demoNode));

  head->data = 10;
  head->next = node2;
  node2->data = 15;
  node2->next = node3;
  node3->data = 30;
  node3->next = node4;
  node4->data = 35;
  node4->next = node5;
  node5->data = 50;
  node5->next = NULL;

  display(head);
  deleteAlternateNode(head);
  display(head);

  return 0;
}
// List: 10 15 30 35 50
// List: 10 30 50