データ構造とアルゴリズム Vol.3

Vol.3: Doubly Linked List

この版ではDoubly Linked Listの必要性とその使い方について学びます。

Doubly Linked Listとは？

👌 Doubly Linked Listは頭（Head）と尻尾（Tail）を両方持っているという特徴があります。
👌 Doubly Linked Listの各ノードは、前ノードと後ろノードの情報を両方とも保存しています。

Doubly Linked Listの挿入プロセス

具現するイメージ

例）実行するコードの例

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

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

//前方でも後方でもアクセス可能
Node *head, *tail;

//挿入関数
void insert(int data){
  Node* node = (Node*)malloc(sizeOf(Node));
  node->data = data;
  Node* cur;
  //最初の元素
  cur = head->next;
  //我々が入れようとするデータより、見ているポインタノードのデータが小さいときに限って右に移動し続けるようにするため、昇順を維持可能
  while (cur->data < data && cur ! = tail) {
  cur = cur-> next;
  }
  Node* prev = cur->prev;
  prev->next = node;
  node->prev = prev;
  cur->prev = node;
  node->next = cur;

}

int main(void) {
  system("pause");
  return 0;
}

Doubly Linked Listの削除プロセス

具現するイメージ

deleteDoubly.png

例）実行するコードの例

上記のコードに以下のコードを追加

void removeFront() {
  Node* node = head->next;
  head->next = node->next;
  Node* next = node->next;
  next->prev = head;
  free(node);
}

void show() {
  Node* cur = head->next;
  while (cur != tail) {
    printf("%d", cur->data);
    cur = cur->next;
 }
}

完成したDoubly Linked Listの使用

例）実行するコードの例

上記のmainに以下のコードで修正

int main(void) {
  head = (Node*) malloc(sizeof(Node));
  tail = (Node*) malloc(sizeof(Node));
  head->next = tail;
  head->prev = head;
  tail->next = tail;
  tail->prev = head;
  insert(2);
  insert(1);
  insert(3);
  insert(9);
  insert(7);
  removeFront();
  show();
  system("pause");
  return 0;
}

🤔　結果は？
result-> 2 3 7 9

Doubly Linked List実装における注意点

❗上記のソースコードに加えて挿入および削除機能からの例外事項を処理する必要があります。
❗例として、これ以上削除する元素がないのに、削除する場合などをチェックする必要があります。

まとめ

👌 Doubly Linked Listは、各ノードが前ノード(Prev)と後ろノード(Next)の情報を保存しています。
👌 Doubly Linked Listを利用すると、リストの前から若しくは後ろからすべてアクセスできます。

📚参考講義：コンピューター工学専攻必須オールインワンパッケージOnline
👆 上記の講義はCとC++を言語を前提に説明しています。