[CS50] week5 - Data structures part2

# 初めに
前回の続きです。

https://qiita.com/hu-yu/items/1a3657afd27e3cd18757

# 単方向リスト（Singly linked list）
## 反転（Reverse）
### 反転された値を格納する配列

https://prepinsta.com/c-program/reversing-a-linked-list-without-changing-the-links-between-the-nodes/

リストにアクセスして値をコピーし、配列の最後尾から最初まで値を入れていく。リストの順はそのままです。

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

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

// note: don't know why use static here?
static void reverse(demoNode **headRef)
{
  demoNode *current = *headRef;
  int size = 0;

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

  int arr[size];
  int count = size - 1;

  current = *headRef;
  while (current != NULL)
  {
    arr[count--] = current->data;
    current = current->next;
  }

  current = *headRef;
  count = 0;
  while (current != NULL)
  {
    current->data = arr[count++];
    current = current->next;
  }
}

void display(demoNode *node)
{
  printf("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;
  demoNode *node4 = NULL;

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

  head->data = 10;
  head->next = node2;
  node2->data = 12;
  node2->next = node3;
  node3->data = 3;
  node3->next = node4;
  node4->data = 25;
  node4->next = NULL;

  display(head);
  reverse(&head);
  display(head);

  return 0;
}
// List: 10 12 3 25
// List: 25 3 12 10
```
複雑なことを考えなくても反転した要素を出力するメソッドですが、データタイプが違っている場合はたぶん通用しないと思います。

（こういったときには、ポインタ配列なら解決できそうかな...？やったことないのでアイディアとして残ります。）

### リストノードを逆順に出力する
https://prepinsta.com/c-program/for-printing-reverse-of-a-linked-list-without-actually-reversing/

```c
// form the last node to the first node
void display(demoNode *node)
{
  if (node == NULL)
  {
    return;
  }
  display(node->next);
  printf("%d ", node->data);
}

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

  printf("Enter size of linked list: ");
  scanf("%d", &size);
  for (int i = 0; i < size; i++)
  {
    current = (demoNode *)malloc(sizeof(demoNode));

    printf("Enter the data: ");
    scanf("%d", &(current->data));
    current->next = NULL;

    if (head == NULL)
    {
      head = current;
    }
    else
    {
      previous->next = current;
    }
    previous = current;
  }
  display(head);
  printf("\n");
  return 0;
}
// Enter size of linked list: 3
// Enter the data: 1
// Enter the data: 2
// Enter the data: 3
// 3 2 1
```

### リストノードを反転する

https://prepinsta.com/c-program/for-reversing-a-linked-list-by-changing-links-between-the-nodes/

膨大なデータの入力では、ノードがいつも最初の位置に挿入したら、ループで最後の位置を探さずすぐに入れれるのが効率的ですが、入力順とは逆になってしまって不便なこともあります。なのでリストを反転するのがとても重要だと思います。

```c
void reverseLinkedList(demoNode **head)
{
  demoNode *previous = NULL;
  demoNode *next = NULL;
  demoNode *current = *head;

  // not empty list
  while (current != NULL)
  {
    // store second node address first
    next = current->next;
    // point to the previous node address
    // head node points to NULL
    current->next = previous;
    // the previous node moves one position ahead
    previous = current;
    // the current node also moves on
    current = next;
    // note: head(first node)->
  }
  *head = previous;
}

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

int main(void)
{
  int number;
  int data;
  demoNode *head = NULL;
  printf("Enter the number of nodes: ");
  scanf("%d", &number);
  printf("Enter the data in the nodes: \n");
  for (int i = 0; i < number; i++)
  {
    scanf("%d", &data);
    insert(&head, data);
  }

  printf("Given linked list: ");
  display(head);

  printf("Reversed linked list: ");
  reverseLinkedList(&head);
  display(head);

  return 0;
}
// Enter the number of nodes: 3
// Enter the data in the nodes:
// 2
// 3
// 5
// Given linked list: 5 3 2
// Reversed linked list: 2 3 5
```
`reverseLinkedList()`のループではとても短いコードで反転処理を済ませたが、実際はどう行っているかとても気になっていて図を作成してみました。

![reverselist1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/35306b9e-4dd3-6678-86b5-0a2fef6756fb.png)

![reverselist2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/0f3ff1e2-3c0c-5340-476f-1e962e4b5820.png)

![reverselist3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/e2dd3075-89fc-4262-8814-0f1039bd09df.png)

![reverselist4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/90b9a6e4-4b93-3566-4db4-c24d633ea100.png)

![reverselist5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/482e4f21-4bb9-86b8-cccc-a0293b78a283.png)

![reverselist6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/9841657f-b915-6e98-34fe-854c608b7493.png)

![reverselist7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/15c5481c-915f-c635-cb17-0cc70507a4cb.png)

![reverselist8.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/bfaa0dd3-9443-a1b2-3f8a-b0b308e413ed.png)

![reverselist9.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/71259ca7-c677-5920-1230-d16e191bf52e.png)

![reverselist10.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/15151f48-b31f-b112-2ba8-d3518faaf422.png)

![reverselist11.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/30908aae-7348-b8a7-3ace-2fc0ddb0ddab.png)

![reverselist12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/b6fe0013-eec5-cf0e-9125-15d3ae76d664.png)

![reverselist13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2477698/1d5dda3b-f19a-44fd-a96e-e04ecda29753.png)

（図では`head`が`main()`の`head`として作成されている。`reverseLinkedList()`の`*head`と同じものを指している。）

パースの経過も一緒に描いて少し読みづらいかもしれないが、要するにほかに三つのノードを用意しておいて、例えば`reverseLinkedList()`では`previous`と`current`は交換する主要ノードで、`previous`は初めから今施しているノードまでのリストを保存していて、最終的に`current`は前のノード`previous`に指させる。`next`は`current`の後のノードリストを把握する。すべてのアドレスを失わせないように最低でも三つのポインタによって保存されなければならない。（もっと賢い方法があるかもしれないがここでの話。）ノードが増えても残りのノードのアドレスをしっかり把握すれば中断されない。

（ポインタ`head`の中身では`demoNode1`のアドレスを持っているということで、`*head`は`demoNode1`にアクセスできて`head`と`demoNode1`が同じものだと思われがちですが、ポインタ`head`とノード`demoNode1`とは、生存範囲（storage）も中身に入れるものも全然違います。）

ループ内の手順としてはいつも通り後ろからですね。
`next`で次のループで処理するノードアドレスを持たせ、
`current`で今指しているノードの`next`を、前のノード`previous`に指させ、
`previous`が今指しているアドレスは`current->next`で参照されているから`previous`を移動させ、
`current`も次の`next`に移動させる。
最後のループが終わったとき`previous`が最後のノードに指していて、`current`は`NULL`に指している。
それで一番先頭の`*head`に最後のノード`previous`を。

### Reverse a linked list in groups of given size
指定した数でノードをグループにして反転させる。

https://prepinsta.com/c-program/to-reverse-a-linked-list-in-groups-of-given-size/

例えば参考文章のようにリストの構成要素は、
`20  15  64  8  1  53  45  17  58  91`があります。
`reverse (head, 4)`では4つのノードがグループとして処理する。
`8   64  15  20`,  `17  45  53  1`,  `91  58`

`reverse()`関数のループの中身は上の`reverseLinkedList()`関数のループは全く一緒で、ループ終了後もし次のノード`NULL`でなければ次のノード`next`が再帰関数の`head`として入れ、そしていつも反転したグループの最後のノード`previous`を返し、連結させる。
```c
demoNode *reverse(demoNode *head, int memberSize)
{
  demoNode *current = head;
  demoNode *next = NULL;
  demoNode *previous = NULL;
  int counter = 0;

  while (current != NULL && counter < memberSize)
  {
    next = current->next;
    current->next = previous;
    previous = current;
    current = next;
    counter++;
  }
  if (next != NULL)
  {
    head->next = reverse(next, memberSize);
  }
  return previous;
}

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

int main(void)
{
  demoNode *head = NULL;
  insert(&head, 10);
  insert(&head, 55);
  insert(&head, 24);
  insert(&head, 37);
  insert(&head, 45);
  insert(&head, 1);
  insert(&head, 9);
  insert(&head, 15);
  insert(&head, 66);

  printf("Before: \n");
  display(head);
  head = reverse(head, 4);
  printf("After: \n");
  display(head);

  return 0;
}
// Before:
// 66 15 9 1 45 37 24 55 10
// After:
// 1 9 15 66 55 24 37 45 10
```

## サーチ（Search）
### 指定する値を持つノードをサーチする（Search an element in list）
https://prepinsta.com/c-program/to-search-an-element-in-a-linked-list/

```c
// loop
// int searchElement(demoNode *head, int target)
// {
//   demoNode *current = head;
//   int index = 0;

//   while (current != NULL)
//   {
//     if (current->data == target)
//     {
//       return index;
//     }
//     current = current->next;
//     index++;
//   }
//   // not found
//   return -1;
// }

// recursion
int searchElement(demoNode *head, int target, int index)
{
  // list doesn't exist or value is not found
  if (head == NULL)
  {
    return -1;
  }

  if (head->data == target)
  {
    return index;
  }

  index++;
  return searchElement(head->next, target, index);
}

int main(void)
{
  int target;

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

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

  head->data = 10;
  head->next = node2;
  node2->data = 15;
  node2->next = node3;
  node3->data = 20;
  node3->next = node4;
  node4->data = 25;
  node4->next = NULL;

  printf("Current list: \n");
  display(head);
  printf("Enter value to search: ");
  scanf("%d", &target);

  // int index = searchElement(head, target);
  int index = searchElement(head, target, 0);
  if (index == -1)
  {
    printf("Element not found\n");
  }
  else
  {
    printf("Element found at position: %d\n", index + 1);
  }
  return 0;
}
// Current list:
// 10 15 20 25
// Enter value to search: 25
// Element found at position: 4

// Current list:
// 10 15 20 25
// Enter value to search: 5
// Element not found
```

### 真ん中のノードを見つけ出す（Find the middle element）
https://prepinsta.com/c-program/to-find-middle-element-of-the-linked-list/

ループでは倍速と普通の速度で移動するノードをそれぞれ設置し、普通のほうが1/2の速度で移動するので、倍速のほうが最後のノードか`NULL`を指しているようになったら、普通のほうが真ん中にいるということです。

```c
void findMiddle(demoNode *head)
{
  demoNode *normalSpeed = head;
  demoNode *doubleSpeed = head;

  if (head != NULL)
  {
    while (doubleSpeed != NULL && doubleSpeed->next != NULL)
    {
      doubleSpeed = doubleSpeed->next->next;
      normalSpeed = normalSpeed->next;
    }
    printf("The middle element in the linked list is: %d\n", normalSpeed->data);
  }
}

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 = 33;
  head->next = node2;
  node2->data = 10;
  node2->next = node3;
  node3->data = 5;
  node3->next = node4;
  node4->data = 26;
  node4->next = node5;
  node5->data = 67;
  node5->next = NULL;

  printf("Link: \n");
  display(head);
  findMiddle(head);

  return 0;
}
// Link:
// 33 10 5 26 67
// The middle element in the linked list is: 5
```

### リストの最後尾から指定位置のノードを見つけ出す（Find nth node from the end）
https://prepinsta.com/c-program/find-kth-node-from-end-of-the-linked-list/

```c
demoNode *findNthFromEnd(demoNode *head, int nth)
{
  demoNode *temp = head;
  int size = 0;

  // move onto the end
  while (temp)
  {
    size++;
    temp = temp->next;
  }

  // when nth is valid in list
  if (size >= nth && nth > 0)
  {
    temp = head;
    for (int i = 0; i < size - nth; i++)
    {
      temp = temp->next;
    }
  }

  return temp;
}

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

int main(void)
{
  int arr[] = {1, 2, 3, 4, 5};
  int length = sizeof(arr) / sizeof(arr[0]);

  demoNode *head = NULL;
  for (int i = 0; i < length; i++)
  {
    push(&head, arr[i]);
  }

  display(head);

  // int nth = 5;
  int nth = 1;
  demoNode *node = findNthFromEnd(head, nth);

  if (node)
  {
    printf("nth node from the end is %d\n", node->data);
  }

  return 0;
}
// 5 4 3 2 1
// nth node from the end is 5
// 5 4 3 2 1
// nth node from the end is 1
```

## 最後尾に追加する（Append）と先頭に追加する（Prepend）
### 先頭に挿入すると最後尾に挿入する（Prepend and append）
前回での最初位置に挿入（InsertStart）と最後位置に挿入（InsertEnd）と同じロジックです。

```c
// insertStart/push/CreateNode...
void prependNode(demoNode **head, int data)
{
  demoNode *newNode = (demoNode *)malloc(sizeof(demoNode));
  newNode->data = data;
  newNode->next = *head;
  *head = newNode;
}

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

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

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

int main(void)
{
  demoNode *head = NULL;
  prependNode(&head, 1);
  prependNode(&head, 2);
  prependNode(&head, 3);
  display(head);

  appendNode(&head, 8);
  appendNode(&head, 9);
  appendNode(&head, 10);
  display(head);

  return 0;
}
// List: 3 2 1 
// List: 3 2 1 8 9 10
```

### ノードを最後尾から先頭に移動させる（Move the last node to the beginning）
https://prepinsta.com/c-program/to-move-the-last-n-node-of-a-linked-list-to-the-beginning-of-the-list/

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

void moveToFront(demoNode **head, int num)
{
  for (int i = 0; i < num; i++)
  {
    if (*head == NULL || (*head)->next == NULL)
    {
      return;
    }
    // the last one
    demoNode *last = *head;
    // the second-to-last one
    demoNode *secondLast = NULL;
    while (last->next != NULL)
    {
      secondLast = last;
      last = last->next;
    }
    // the second-to-last become the last one
    secondLast->next = NULL;
    // connect the original head
    last->next = *head;
    // become the first one
    *head = last;
  }
}

int main(void)
{
  // int num = 2;
  int num = 10;
  demoNode *head = NULL;
  push(&head, 56);
  push(&head, 12);
  push(&head, 31);
  push(&head, 69);
  push(&head, 20);
  push(&head, 75);
  push(&head, 6);
  push(&head, 17);

  printf("Before: \n");
  display(head);
  moveToFront(&head, num);
  printf("After: \n");
  display(head);

  return 0;
}
// Before:
// 17 6 75 20 69 31 12 56
// After:
// 12 56 17 6 75 20 69 31
```

## ソート（Sort）
### バブルソート（Bubble sort）
https://www.programiz.com/dsa/linked-list-operations#sort

```c
void sortLinkedList(demoNode **head)
{
  demoNode *current = *head;
  demoNode *nextNode = NULL;
  int tempValue = 0;

  if (head == NULL)
  {
    return;
  }

  // bubble sort
  while (current != NULL)
  {
    nextNode = current->next;

    while (nextNode != NULL)
    {
      if (nextNode != NULL && current->data > nextNode->data)
      {
        tempValue = current->data;
        current->data = nextNode->data;
        nextNode->data = tempValue;
      }
      nextNode = nextNode->next;
    }
    current = current->next;
  }
}

int main(void)
{
  demoNode *head = NULL;
  prependNode(&head, 1);
  prependNode(&head, 2);
  prependNode(&head, 3);
  display(head);

  sortLinkedList(&head);
  display(head);

  return 0;
}
// List: 3 2 1
// List: 1 2 3
```


## 折り畳み（Fold）
### リストを折り返す
https://prepinsta.com/c-program/for-fold-a-linked-list/

使い道はあまりよく分からないので一応参考文章をメモります。