女性向けエンジニアスクール
3秒でわかる
各要素が次の要素の場所を指し合って一列に並ぶデータ構造。途中への挿入や削除を、他の要素をずらさずに済ませたいときに使います。
もう少し詳しく
どういうものか
連結リストは、値と「次の要素への参照」を持つノードを鎖のようにつないで列を表すデータ構造です。配列のようにメモリ上で連続している必要がなく、必要になった時点でノードを 1 つ確保してつなぎ替えるだけで伸び縮みします。次だけを指すものを単方向リスト、前後どちらも指すものを双方向リストと呼びます。
なぜ必要か
配列の途中に要素を差し込むと、後ろの要素をすべて 1 つずつずらす必要があります。10 万件の先頭に挿入すれば 10 万回の移動です。連結リストなら、前後のノードの参照を 2 本つなぎ替えるだけで終わります。逆に「n 番目を取り出す」は先頭から辿るしかなく配列に負けます。どちらが速いかではなく、何を多く行うかで選ぶ構造です。
具体例
class Node:
def __init__(self, value):
self.value = value
self.next = <a href="/glossary/none" class="text-primary font-medium underline underline-offset-2 hover:text-primary-dark">None</a>
head = Node("a")
head.next = Node("c")
# a と c の間に b を差し込む
node_b = Node("b")
node_b.next = head.next
head.next = node_b
cur = head
while cur:
print(cur.value)
cur = cur.nextつなぐ順番を逆にすると c への参照が消えて、以降の要素をすべて失います。
つまずきやすいところ
似た用語との違い
双方向リストは各ノードが前後の参照を持つため、手元のノードから前へも戻れます。Java の LinkedList や Python の collections.deque はこの形で、両端への追加と削除が定数時間で終わります。キューやスタック、直近の履歴を保持する用途ではこの性質がそのまま利点になります。木構造やグラフも、参照でノードをつなぐという点では連結リストの発想の延長にあります。
| 操作 | 配列 | 連結リスト |
|---|---|---|
| n 番目の取得 | O(1) | O(n) |
| 先頭への挿入 | O(n) | O(1) |
| 位置が既知の削除 | O(n) | O(1) |
| メモリ配置 | 連続 | 分散 |
覚え方
宝探しのメモです。1 枚目のメモに 2 枚目の場所が書いてあり、順に辿るしかありません。途中に 1 枚差し込むのは簡単ですが、5 枚目だけをいきなり見ることはできません。
