Nodeクラスとリストの構築
Nodeデータクラスを定義し、ノードを手作業で連結してリストを構築し、ポインターの変化を可視化するinsert/delete/printヘルパーを書きます。
「Nodeクラスとリストの構築」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
連結リストとは
連結リストは、各ノードが値と次のノードへのポインターを保持するノード列です。配列とは異なり、ノードはメモリ上に分散しているため、インデックスによる O(1) アクセスはありません。その代わり、位置が既知であれば要素を移動せずに O(1) で挿入・削除できます。
Python では、各ノードを val と next を持つ小さなクラスで表します。ノードをつなげることでリストを作り、最後のノードの next を None にして終端を示します。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')配列からリストを構築する
面接では、リストを渡されて対応する連結リストを構築するよう求められたり、その逆を求められたりすることがよくあります。ヘルパー関数 build と to_list は覚えておく価値があります。build は配列からノードをつなぎ、to_list はリストをたどって値を集め、簡単に検証できるようにします。
n 個の要素から連結リストを構築するには、O(n) 時間と O(n) 空間が必要です。ダミーヘッドノードを使うと、最初のノードが変わる場合の境界ケースを簡単に処理できます。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]先頭と末尾への挿入
新しいノードを先頭に挿入する処理は O(1) です。ノードを作成し、その next を以前の先頭に向け、新しいノードを先頭として返します。末尾への挿入では、最後のノードまで走査する必要があるため O(n) かかり、その後で新しいノードをつなぎます。
ダミーヘッドノードを使うと、dummy.next が常に実際の先頭を指すため、どちらの挿入でも空のリストに対する特別な処理が不要になります。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> None値でノードを削除する
指定した値を持つ最初のノードを削除するには、curr の 1 つ前を指す prev ポインターを保持します。curr.val == target になったら、prev.next = curr.next としてそのノードを飛ばします。ここでもダミーヘッドが特に役立ちます。実際の先頭ノードを削除する場合の特別な処理が不要になり、prev は常にダミーノードから開始できるためです。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))ポインターの変更を可視化する
よくある間違いは、ポインターを更新するときにノードを見失うことです。上書きする前に必ず next を保存してください。まず saved = curr.next とし、その後で再代入します。リストを矢印でつないだ箱として描き、コードを書く前に紙の上で各ポインターの更新をシミュレーションしてください。この視覚的な方法により、面接中の意図しない null ポインターエラーを防げます。
Python では、curr.next を再代入しても curr 自体には影響しません。ただし、保存する前に curr.next への参照を失うと、リストを前方にたどれなくなります。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4単方向連結リストと双方向連結リスト
単方向連結リストは next ポインターだけを保持するため、走査は一方向です。双方向連結リストは prev と next の両方を保持するため、O(1) で逆方向に走査でき、ノードへの直接参照があれば O(1) で削除できます（prev を追跡するループも必要ありません）。
Python の collections.deque は双方向連結リストとして実装されているため、O(1) の appendleft と popleft をサポートします。面接では単方向連結リストを実装することが多く、双方向連結リストは LRU キャッシュの設計で登場します。
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')長さ、末尾、出力のヘルパー
連結リストの面接で常に用意しておくべきユーティリティ関数は 3 つあります。length(head) は O(n) でノード数を数え、tail(head) は O(n) で最後のノードを返し、print_list(head) はデバッグ用にリストを整形します。これらを用意しておけば、ヘルパー処理を再実装するのではなく、中心となるアルゴリズムに集中できます。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)連結リストでの 2 ポインター法の準備
2 ポインター法は配列と同じように連結リストでも重要ですが、ポインターが指すのはインデックスではなく連結リストのノードです。よく使う構成には、中央要素の特定やサイクル検出に使うスローポインターとファストポインター（ファストポインターは 2 倍の速さで移動します）や、削除と反転に使う前のノードと現在のノードの組があります。
両方のポインターを必ず明示的に初期化し、null 終端のチェックを慎重に行ってください。fast and fast.next によって、ファストポインターが末尾付近にあるときの null ポインターエラーを防げます。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)ダミーヘッドパターン
ダミーヘッド（番兵ノード）パターンは、連結リストの問題で最も役立つテクニックの 1 つです。値 0 のダミーノードを先頭に追加すると、空のリストや実際の先頭の変更を特別扱いする必要がなくなります。結果は常に dummy.next です。このパターンは、ソート済みリストのマージ、末尾から n 番目の要素の削除、リストの分割など、さまざまな場面で使われます。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]時間計算量と空間計算量
連結リストの多くの操作の計算量は次のとおりです。インデックスによるアクセス：O(n) — 先頭から走査する必要があります。既知のノードでの挿入・削除：O(1) — ポインターをつなぎ直すだけです。位置 k での挿入・削除：O(k) — まず走査します。検索：O(n) — 最悪の場合はリスト全体を調べます。追加のデータ構造を除けば、インプレース操作の空間計算量はすべて O(1) です。
配列と比較してみましょう。配列は O(1) のアクセスを提供しますが、要素を移動する必要があるため、挿入・削除は O(n) です。任意の位置での挿入と削除が頻繁に発生する場合は、連結リストのほうが適しています。
連結リストの面接のヒント
連結リストのコードを書く前に、箱と矢印でリストを視覚的に描いてください。空のリスト、1 ノードだけのリスト、長さが偶数の場合と奇数の場合という境界ケースを声に出して確認します。ダミーヘッドを使って境界条件を簡単にしてください。早い段階で必ず if not head を確認します。コードを書いた後は、3 ノードのリストで解答をトレースし、面接官に指摘される前にポインターのエラーを見つけてください。
連結リストのバグの多くは、次の 3 つの原因から生じます。上書きする前に next を保存し忘れること、終了条件のオフバイワン、そして先頭が変わる境界ケースを処理しないことです。ダミーノードを使えば、3 つ目の問題は完全になくせます。
理解度チェック
このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認します。
レッスンのまとめ
このレッスンでは、連結リストが val フィールドと next フィールドを持つ Node オブジェクトから構成されること、ダミーヘッドパターンによって先頭の変更に関する境界ケースをなくせること、そしてスロー・ファストの 2 ポインター構成が中央要素の特定とサイクル検出の基礎になることを学びました。次は、面接で最もよく出題されるポインター問題の 1 つである連結リストの反転に取り組みます。
よくある質問
「Nodeクラスとリストの構築」レッスンは無料ですか？
はい。「Nodeクラスとリストの構築」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「Nodeクラスとリストの構築」で何を学びますか？
Nodeデータクラスを定義し、ノードを手作業で連結してリストを構築し、ポインターの変化を可視化するinsert/delete/printヘルパーを書きます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「Nodeクラスとリストの構築」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- Nodeクラスとリストの構築
- 連結リストを反転する
- Floydのアルゴリズムによる循環検出
- マージ、分割、末尾からN番目を探す