目次
「みんなのデータ構造」でプログラミングで使うデータ構造を学ぶ
「みんなのデータ構造」(Amazonリンク)とは、コンピュータ・サイエンスの基礎となるデータ構造の教科書「Open Data Structure」の日本語訳です。Introduction to Algorithmsといったアルゴリズムの名著への橋渡しになるような、実用的なテーマが丁寧に説明されています。
この本でデータ構造を学ぶ意義は、訳者まえがきで以下のように説かれています。
- ソフトウェアのほとんどはシンプルなデータ構造の組み合わせでできている。
- 「みんなのデータ構造の内容がだいたいわかれば、いいエンジニアになれる。
また、わからない部分は読み飛ばしていいとも書かれています。さらに嬉しいことに、この書籍の中でも実務や学術研究で頻繁に登場する内容がピックアップされています。
- 配列: ArrayStack・ArrayQueue・ArrayDeque
- 連結リスト: SLList(Singly-Linked List)・DLList(Doubly-Linked List) 👈 この記事
- チェイン法を使ったハッシュテーブル: ChainedHashTable
- 二分木・二分探索木:BinaryTree・BinarySearchTree
- 赤黒木: RedBlackTree
- 二分ヒープ: BinaryHeap
- ソート: MergeSort・QuickSort
- グラフの探索: 幅優先探索・深さ優先探索
書籍のサンプルコードはC++ですが、何か1つプログラミング言語を知っていれば問題なく読み進めることができます。
弁護士ドットコムでは、エンジニア有志で本書の輪読会をしています。この本の内容をマスターして、競技プログラミングに挑戦するぞ！
SLList・DLListの感想・考察
- Arrayでは、先端、末尾の要素に対する追加add、削除removeはO(1)。しかし、それ以外のindexに対する要素の追加、削除はO(1 + min{i, n-i})
- SLListやDLListでは、先端head、末尾tailのノードの参照を保持する
- SLListはStackとQueueインターフェース（push, pop, add, remove）が実装できる（計算量はO(1)）
-
SLListは直前のノードの参照を保持していないが、DLListは各ノードが直前のノードの参照を保持する
- SLListは単方向。先端から末尾に辿るだけ
- DLListでは、先端のノードの直前と末尾のノードの次のノードはdummyノードとするため、循環できる
-
DLListでは、要素の取得get、変更set、追加add、削除removeの計算量はO(1 + min{i, n-i})である
- しかし、対象となるノードの参照を保持している場合に限り、計算量はO(1)となる
- SLListや、DLListは動的に要素を追加/削除する場面で適したデータ構造
- 一方、DLListは前後のノードの参照を持つため、メモリ効率が良くない。SLListの短所を改善するものの、空間計算量にデメリットが生じる。
コンピュータ・サイエンスの基礎を学びたい方や、競技プログラミングにチャレンジする方に「みんなのデータ構造」(Amazonリンク)はおすすめです。
連結リストとは何か
連結リストには、SLList(singly-linked list、単方向連結リスト)とDLList(doubly-linked list、双方向連結リスト)がある。
SLListは、Queue（add、remove）、Stack（push、pop）の操作をO(1)で実装できる。 DLListは、Queue、Stack、Dequeの操作をO(1)で実装できる。
配列（Array）と比較すると、連結リストの短所はget(i)、set(i, x)が全ての要素に対して定数時間ではなくなる。長所は、ノードへの参照uがあれば、uの削除やuの隣へのノードの挿入が定数時間で実行できること。
SLList: 単方向連結リスト
SLListは、StackとQueueインターフェースを実装する。push(x)、pop()、add(x)、remove()の実行時間はいずれもO(1)である。
ノードを定義する
各ノードuは、データu.xと参照u.nextを保持している。列の末尾のノードwにおいては、w.next = nullである。
class Node {
public:
T x;
Node *next;
Node(T x0) {
x = 0;
next = NULL;
}
};先頭と末尾のノードを変数に格納する。
Node *head;
Node *tail;
int n;push() - O(1)
先頭に要素を追加する。
T push(T x) {
Node *u = new Node(x);
u->next = head;
head = u;
if (n == 0) {
tail = u;
}
n++;
return u;
}pop() - O(1)
先頭の要素を取り出す。
T pop() {
if (n == 0) return null;
T x = head->x;
Node *u = head;
head = head->next;
delete u;
n--;
if (n == 0) tail = NULL;
return x;
}remove() - O(1)
先頭の要素を取り出す。popと実装は同じ。
T remove() {
if (n == 0) return null;
T x = head->x;
Node *u = head;
head = head->next;
delete u;
n--;
if (n == 0) tail = NULL;
return x;
}add() - O(1)
末尾に要素を追加する。
bool add(T x) {
Node *u = new Node(x);
if (n == 0) {
head = u;
} else {
tail->next = u;
}
tail = u;
n++;
return true;
}DLList: 双方向連結リスト
DLListは、Listインターフェースを実装する。get(i)、set(i, x)、add(i, x)、remove(i)の実行時間はいずれもO(1 + min{i, n-i})である。
ノードを定義する
前後のノードの参照を持つ。
struct Node {
T x;
Node *prev, *next;
}先頭のノードの前、末尾のノードの次にはdummyノードを設置する。
Node dummy;
int n;
DLList() {
dummy.next = &dummy;
dummy.prev = &dummy;
n = 0;
}i番目のノードを取得する。計算量はO(min{i, n-i})
Node* getNode(int i) {
Node* p;
if (i < n/2) {
p = dummy.next;
for (int j = 0; j < i; j++)
p = p->next;
} else {
p = &dummy;
for (int j = n; j > i; j--)
p = p->prev;
}
return (p);
}get()/set() - O(1 + min{i, n-i})
getNode(i)を利用する。
T get(int i) {
return getNode(i)->x;
}T set(i, x) {
Node* u = getNode(i);
T y = u->x;
u->x = x;
return y;
}add(i, x)/remove(i) - O(1 + min{i, n-i})
ノードwの直前にノードuを追加する。
Node* addBefore(Node *w, T x) {
Node *u = new Node(x);
u->prev = w->prev;
u->next = w;
u->prev->next = u;
u->next->prev = u;
n++;
return u;
}addは、addBeforeとgetNodeを組み合わせる。
void add(int i, T x) {
addBefore(getNode(i), x);
}ノードwを削除する。
void remove(Node *w) {
w->prev->next = w->next;
w->next->prev = w->prev;
delete w;
n--;
}次にremove(i)を実装する。
T remove(int i) {
Node *w = getNode(i);
T x = w->x;
remove(w);
return x;
}