C++で連結リストを1から実装する

データ構造第3弾、今回は連結リストを実装してみます。
これまでスタックやキューを実装してきましたが、今回はちょっとそれらより難しそうです。

目標

標準ライブラリに入っている連結リストを、自分で実装してみることで理解する。

双方向連結リスト

双方向連結リストとは、リストの各要素が、それぞれ直前と直後の要素の情報を持つようにリンクさせたデータ構造のことです。
要素の削除や挿入を定数時間で高速に行えますが、要素へのアクセスにかかります。実用の場面ではそれほど使われないみたいです。

実装してみる

とはいうものの、勉強のために一度実装してみます。今回実装するのは双方向連結リストで、次のような機能を備えています（標準ライブラリのリストはもっと色々な機能があります）。

insert(x)	先頭にキーxの要素を挿入する
delete_key(x)	キーxを持つ最初の要素を削除する
delete_first()	先頭の要素を削除する
delete_last()	末尾の要素を削除する

ポイントとなるのが、番兵と呼ばれる特殊なノードで、これは先頭の要素と末尾の要素にリンクして、特定の値を持たず、両者をつなぐ役割を持っています。これによってスマートに実装できます。要素の挿入や削除は、ノードのリンクをつなぎかえることによって行います。また、要素にアクセスするには、ノードのリンクを目的のノードまで次々と辿っていきます。
ここでは番兵をnilとし、Nodeクラスのメンバであるポインタprev、nextがそれぞれ直前、直後のノードを指しています。また、メンバ変数keyでノードに格納されている値にアクセスします。

#include<iostream>
using namespace std;

class LinkedList {
private:
  class Node {
  public:
    int key;
    Node *prev;
    Node *next;
  };
  
  Node *nil;  // 番兵

  // keyを持つ最初のノードのポインタを返す
  Node* list_search(int key) {
    Node *current = nil->next;
    while (current != nil && current->key != key) {
      current = current->next;
    }
    return current;
  }

  // 引数に与えられたノードを削除
  void delete_node(Node *node) {
    if (node == nil) return;  // nodeが番兵の時は何もしない
    // リンクつなぎ変え
    node->prev->next = node->next;
    node->next->prev = node->prev;
    delete node;  // メモリ解放
  }
  
public:
  LinkedList() {
    nil = new Node;
    nil->prev = nil;
    nil->next = nil;
  }

  // keyを先頭に挿入
  void insert(int key) {
    Node *x;  // 新しいノードをさすポインタ
    x = new Node;
    x->key = key;
    // リンクのつなぎ替え
    x->next = nil->next;
    nil->next->prev = x;
    nil->next = x;
    x->prev = nil;
  }  

  // keyを持つ最初のノードを削除
  void delete_key(int key) {
    delete_node(list_search(key));
  }

  // 先頭を削除
  void delete_first() {
    delete_node(nil->next);
  }

  // 末尾を削除
  void delete_last() {
    delete_node(nil->prev);
  }

  // リストの全ての要素を表示
  void print_list() {
    int cnt = 0;
    Node *current = nil->next;
    
    while (current != nil) {
      if (cnt++ > 0) cout << " ";
      cout << current->key;
      current = current->next;
    }
    cout << endl;      
  }
  
};

int main(void) {
  LinkedList l;
  // 1~10を格納
  for (int i = 10; i > 0; i--) l.insert(i);
  l.print_list();
  // 末尾を削除
  l.delete_last();
  l.print_list();
  // 先頭を削除
  l.delete_first();
  l.print_list();
  // 3を削除
  l.delete_key(3);
  l.print_list();

  return 0;
}

実行結果

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
2 4 5 6 7 8 9

まとめ

連結リストを実装しました。ポインタがぽんぽん出てくるので、C++初心者には少し難しかったです。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.