LoginSignup
16
16

More than 5 years have passed since last update.

@yokoto

C++ 連結リスト

Last updated at Posted at 2016-12-15

説明がおかしいと思うので随時修正します。

連結リストとは？

・最も基本的なデータ構造の1つ。
・ノード毎に任意のデータと、1つの参照（リンク）を持つ。
・この参照（リンク）は、リスト上の次のノードを指す。
・リストの最後尾ならNull値を格納するか、空のリストを指す。
cf. 連結リスト -Wikipedia

・今回は一番単純な線形片方向リストを実装する。

連結リストと配列の違い

・連結リストでは要素の挿入は無制限に可能だが、配列はサイズが決まっているために限界がある。
・連結リストがシーケンシャルアクセス（先頭からの順次アクセス）を得意とするが、配列はインデックスを持つためランダムアクセス性に優れている。（シーケンシャルアクセスも多くのマシン上では、連結リストよりも配列の方が高速である。）
ex. ヒープソートのようにインデックスによって高速に要素を参照する必要がある場合、連結リストは不向き。
・連結リストの別の欠点は、参照（リンク）のための余分な領域を必要とする。
ex. char型やboolean型のような小さなデータ要素を連結リストで操作するのは（1文字ごとにノードを割り当てて文字列操作を実現するなど）、速度の面でもメモリ消費の面でも無駄が多い。
cf. 連結リストと配列 -Wikipedia

今回実装する連結リストの機能

・リストの最後にノードを追加する。
・リスト内にノードを挿入する。
・リスト内を移動する。
・ノードを削除する。
・リストを削除する。

数をデータとして持つノードの連結リスト


class NumberList
{
private:
  // リストの構造を宣言
  struct ListNode
  {
    double value;  // このノードが持つ値
    struct List *next;  // 次のノードを指す
  };

  ListNode *head;  // リストの先頭のノードへのポインタ

public:
  // コンストラクタ
  NumberList()
  {
    head = NULL;
  }
  // デストラクタ
  ~NumberList();

  // 連結リストの機能
  void appendNode(double);
  void insertNode(double);
  void deleteNode(double);
  void displayList() const;
};

新たなノードを作成する

・新たなノードのためのメモリを割り当てる。

newNode = new ListNode;

・新たなノードの値を初期化する。

newNode->value = num;

・新たなノードの参照（リンク）にNULLをセットする。

newNode->next = NULL;

リストの最後にノードを追加する

・基本的な順序
　1. 新たなノードを作成する。
　2. リストの最後に新たなノードを追加する。
　　・if リストが空
　　　- headポインタに新たなノードをセットする。
　　・else,
　　　1. リストを最後までループする。
　　　2. 新たなノードを最後のノードの参照（リンク）としてセットする。

・appendNode関数

void NumberList::appendNode(double num)
{
  ListNode *newNode;  // 新たなノード
  ListNode *nodePtr;  // リスト内を移動する用のノード

  // 新たなノードのメモリを割り当て、
  // valueにnumを代入、
  // nextにNULLをセット
  newNode = new ListNode;
  newNode->value = num;
  newNode->next = NULL;

  // リストにノードがなければ、
  // newNodeを最初のノードにする
  if (!head)
  {
     head = newNode;
  }
  else  // そうでなければ、最後にnewNodeを挿入する
  {
    // nodePtrをリストの先頭として初期化する
    nodePtr = head;

    // リストの最後のノード（nodePtr->nextがnull）を見つける
    // nodePtr->nextがnullであるとき、ループを出る
    while (nodePtr->next)
    {
      nodePtr = nodePtr->next;
    }

    // 最後のノードとしてnewNodeを挿入する
    nodePtr->next = newNode;
  }
}

・main関数

int main()
{
  // NumberListオブジェクトを宣言
  NumberList list;

  // リストにいくつかの値を追加してみる
  list.appendNode(2.5);
  list.appendNode(7.9);
  list.appendNode(12.6);
  return 0;
}

リストの任意の場所にノードを挿入する

・今回は新たなノードを、それが持つ値よりも大きい値を持つノードの前に挿入する。
・リストを調べるには２つのポインタが必要。
　1. 挿入される新たなノードの値よりも、大きい値を持つノードを指すポインタ
　2. 挿入する場所の前にあるノードを指すポインタ
・新たなノードは、これらのポインタが指し示すノードの間に挿入される。

・insertNode関数

void NumberList::insertNode(double num)
{
  ListNode *newNode;  // 新たなノード
  ListNode *nodePtr;  // リスト内を移動する用のノード
  ListNode *previousNode = NULL;  // 前にあるノード

  /// 新たなノードにメモリを割り当て、
  // valueにnumを代入
  newNode = new ListNode;
  newNode->value = num;

  // リストにノードがなければ、
  // newNodeを最初のノードにする
  if (!head)
  {
     head = newNode;
  }
  else  // そうでなければ、任意の場所にnewNodeを挿入する
  {
    // nodePtrをリストの先頭として初期化する
    nodePtr = head;

    // numより小さい値を持つ全てのノードをスキップする
    // nodePtr->valueがnumより大きい値を持つとき、ループを出る
    while (nodePtr != NULL && nodePtr->value < num)
    {
      previousNode = nodePtr;
      nodePtr = nodePtr->next;
    }

    // 新たなノードがリストの先頭にあるならば、
    // 他のすべてのノードの前にそれを挿入する
    if (previousNode == NULL)
    {
      head = newNode;
      newNode->next = nodePtr;
    }
    else  // そうでなければ、前のノードの後に挿入する
    {
      previousNode->next = newNode;
      newNode->next = nodePtr;
    }
  }
}

・main関数

  // リストの真ん中にノードを挿入する
  list.insertNode(10.5);

リスト内を移動する

・連結リスト内の各ノードを見る。
・基本的な順序
　1. 最初に、リスト内を移動する用のノードをheadにセット
　2. while リスト内を移動する用のノードがNULLでない
　　1. リスト内を移動する用のノードを、前にあるノードとしてセット
　　1. リスト内を移動する用のノードの参照（リンク、つまり次のノード）を、そのノード自体としてセット

ノードを削除する

・連結リストからノードを削除するために使われる。
・リストが動的メモリを使用しているのならば、メモリからノードを削除する。
・２つのポインタを必要とする
　1. 削除されるノードへのポインタ
　2. 削除されるノードの前にあるノードへのポインタ

・deleteNode関数

void NumberList::deleteNode(double num)
{
  ListNode *nodePtr;  // リスト内を移動する用のノード/削除されるノード
  ListNode *previousNode;  // 前にあるノード

  // リストがからならば、何もしない
  if (!head)
    return;

  // 最初のノードが削除するべきノードかどうかを決定する
  if (head->value == num)
  {
    nodePtr = head->next;
    delete head;
    head = nodePtr;
  }
  else
  {
    // nodePtrをリストの先頭として初期化する
    nodePtr = head;

    // numと一致しない値を持つ全てのノードをスキップする
    // nodePtr->valueがnumと同じ値を持つとき、ループを出る
    while (nodePtr != NULL && nodePtr->value < num)
    {
      previousNode = nodePtr;
      nodePtr = nodePtr->next;
    }

    // nodePtrがリストの最後になければ、
    // previousNodeの参照（リンク）をnodePtrの参照（リンク）にセットし、
    // nodePtrを削除する
    if (nodePtr)
    {
      previousNode->next = nodePtr->next;
      delete nodePtr;
    }
  }
}

・main関数

  // 真ん中のノードを削除する
  cout << "真ん中のノードを削除する。\n";
  list.deleteNode(7.9);

  // リストを表示する
  cout << "残されたノード。\n";
  list.displayList();
  cout << endl;

  // 最後のノードを削除する
  cout << "最後のノードを削除する。\n";
  list.deletenode(12.6);

  // リストを表示する
  cout << "残されたノード。\n";
  list.displayList();
  cout << endl;

  // 最後に残ったノードを削除する
  cout << "最後に残ったノードを削除する。\n";
  list.deletenode(2.5);

  // リストを表示する
  cout << "残されたノード。\n";
  list.displayList();
  return 0;

連結リストを削除する

・リスト内の全てのノードを削除しなければならない。
・そのためには、各ノードを１つずつ見て移動する。
・各ノードで、
　1. リストからノードをほどく
　2. リストが動的メモリを使っているならば、ノードのメモリを開放する
・リストの先頭をNULLにセットする。

・NumberListデストラクタ

NumberList::~NumberList()
{
  ListNode *nodePtr;  // リスト内を移動する用のノード/削除されるノード
  ListNode *nextNode;  // 次にあるノード

  // nodePtrをリストの先頭として初期化する
  nodePtr = head;

  // nodePtrがリストの最後になければ、
  while (nodePtr != NULL)
  {
    // nodePtrの参照（リンク）をnextNodeとしてセットする
    nextNode = nodePtr->next;

    // 現在のノードを削除する
    delete nodePtr;

    // nodePtrに次のノードをセットする
    nodePtr = nextNode;
  }
}
16
16
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
16
16