連結リストとは

連結リスト（Linked List）の各データをノード（Node)って呼ぶ。で、このノードたちはポインター（pointer）というものでお互いにつながっている。

単方向リスト（Singly Linked List）の場合は下記のようみたいに一つの方向にしか巡回ができないけど、両方向の場合はどの方向でも移動できる。

# 単方向リスト (Singly Linked List)

|   0x00   | --> |   0x17   | --> | nil |
-----------       -----------     -------
| ノード A |      | ノード B |      | \0  |

ノードの構造はだいたいこんな感じ。ここでnextは次のノードのアドレスを持つポインターになる。

Node {
    T data;
    Node *next;
}

連結リストの特徴としてはデータの挿入の削除が早い。その反面、探索はO(n)で遅い方になる。もし探索の演算がもっと大事な場合は、ハッシュテーブル（Hash Table）とか配列（Array）を使った方がいい。