単方向リストを勉強がてら久々にビールを飲みながらC++で書いてみました。
これをやると、ポインタって何かってよく理解できますね。
しかしビールを飲むと、わけのわからないミスをしでかします…。
ソースコード
#include <iostream> #include <exception> namespace My { template <typename T> class SinglyLinkedList { private: struct Node { T value; Node *next; Node() : value(0), next(nullptr) { } ~Node() { } }; Node *head_; int number_; Node *create(T value) { Node *node = new Node(); node->value = value; node->next = nullptr; return node; } void destroy(Node *node) { delete node; node = nullptr; } public: SinglyLinkedList() : head_(nullptr) ,number_(0) { } ~SinglyLinkedList() { Node *cur = nullptr; for (Node *node = head_; node != nullptr; cur = node, node = node->next) { destroy(cur); } } void push_front(T value) { Node *new_node = create(value); if (head_ == nullptr) { head_ = new_node; } else { Node *node = head_; head_ = new_node; head_->next = node; } number_++; } void push_back(T value) { Node *new_node = create(value); if (head_ == nullptr) { head_ = new_node; } else { Node *node = head_; Node *tail = nullptr; for (; node != nullptr; tail = node, node = node->next); tail->next = new_node; } number_++; } void insert(int pos, T value) { Node *new_node = create(value); if (pos == 0) { push_front(value); } else if (pos < number_ - 1) { Node *prev = nullptr; Node *node = head_; for (int i = 0; i < pos; ++i) { prev = node; node = node->next; } prev->next = new_node; new_node->next = node; number_++; } else if (pos == number_ - 1) { push_back(value); } else { throw std::bad_exception(); } } void pop_front() { Node *node = head_; head_ = node->next; destroy(node); number_--; } void pop_back() { Node *node = head_; Node *prev = nullptr; Node *tail = nullptr; for (; node != nullptr; prev = tail, tail = node, node = node->next); prev->next = nullptr; destroy(tail); number_--; } void erase(int pos) { if (head_ == nullptr) { throw std::bad_exception(); } Node *node = head_; if (pos == 0) { pop_front(); } else if (pos < number_ - 1) { Node *prev = node; for (int i = 0; i < pos; ++i) { prev = node; node = node->next; } prev->next = node->next; destroy(node); number_--; } else if (pos == number_ - 1) { pop_back(); } else { throw std::bad_exception(); } } void display() { for (Node *node = head_; node != nullptr; node = node->next) { std::cout << node->value << ' '; } std::cout << std::endl; } }; } auto main()->int { try { My::SinglyLinkedList<int> list; list.push_back(2); list.display(); list.push_back(3); list.display(); list.push_back(4); list.display(); list.push_front(1); list.display(); list.push_front(0); list.display(); list.insert(1, 3); list.display(); std::cout << "---------" << std::endl; list.pop_back(); list.display(); list.pop_front(); list.display(); list.erase(2); list.display(); list.pop_back(); list.display(); std::cout << "---------" << std::endl; list.push_back(4); list.display(); } catch (std::exception& e) { std::cout << e.what() << std::endl; } }
イテレーターがねえ！とか
追加するたびnewしてる…とかいろいろ足りないところありますが、
勉強で書くにはこれで十分でしょう。
双方向リストじゃないと微妙に実用性ないですね。
ちょこっと変えると双方向リストになります。
実行結果
$ ./list.exe 2 2 3 2 3 4 1 2 3 4 0 1 2 3 4 0 3 1 2 3 4 --------- 0 3 1 2 3 3 1 2 3 3 1 3 3 1 --------- 3 1 4
参考リンクなど
以前にも書いてたな…
