単方向連結リスト
ノード、所有権、走査について学びます
「単方向連結リスト」はCoddyKit上の無料Zig Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはZig Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Zig Academyコースには全4レッスンが含まれています。
連結リストとは
単方向連結リストは値をつなぎ合わせます。各ノードは値と次のノードへのポインターを保持し、末尾ではnullを保持します。🔗
ノードを定義する
ノードは、値と次のノードへのオプショナルポインターを持つ構造体です。オプショナルであるため、最後のノードはnullを指せます。
const Node = struct {
value: i32,
next: ?*Node,
};ポインターがオプショナルである理由
?*Nodeを使うと、チェーンを安全に終端できます。末尾を示す特別な番兵値は必要ありません。
next: ?*Nodeリストで先頭を追跡する
リスト自体が覚えているのは、headと呼ばれる最初のノードと、すべてのノードを所有するアロケーターだけです。
const List = struct {
head: ?*Node,
alloc: std.mem.Allocator,
};ノードを1つ割り当てる
値を追加するには、アロケーターにヒープ上で単一のNodeをcreateするよう依頼します。新しく確保された領域へのポインターが返されます。
const node = try self.alloc.create(Node);先頭にプッシュする
最も低コストな挿入位置は先頭です。新しいノードを以前のheadに向け、それを新しいheadにします。これは定数時間で実行できます。
node.* = .{ .value = v, .next = self.head };
self.head = node;チェーンをたどる
走査するにはheadから始め、nullに到達するまで各nextポインターをたどります。whileループを使うとノードを簡潔に処理できます。
var cur = self.head;
while (cur) |n| {
std.debug.print("{d}\n", .{n.value});
cur = n.next;
}キャプチャでオプショナルをアンラップする
while (cur) |n|と書くと、curがnullでない間だけ本体が実行され、nにはアンラップされたポインターが入ります。nullに達するとループは終了します。
while (cur) |n| { ... }すべてのノードを所有する
各ノードはアロケーターから取得したものなので、すべて返却する必要があります。1つでも忘れるとリークとなり、テスト用アロケーターが報告します。
リスト全体を解放する
deinitでチェーンをたどりますが、解放する前にnextを取得してください。ノードは破棄した瞬間に存在しなくなるためです。
var cur = self.head;
while (cur) |n| {
const nxt = n.next;
self.alloc.destroy(n);
cur = nxt;
}ジェネリックにする
NodeとListを型返却関数で包み、i32だけでなく任意の要素型でリストを使えるようにします。
fn LinkedList(comptime T: type) type {
return struct {
const Node = struct { value: T, next: ?*Node };
};
}クイックチェック
連結リストのノードを1つずつ解放しています。各ノードを破棄する前に何をしなければなりませんか。
まとめ
ノードは値とオプショナルなnextポインターを保持します。リストはheadとアロケーターを管理し、先頭にプッシュして、ノードを1つずつ解放します。🎯
AI チューターと学ぶ Zig — 無料
ブラウザでリアルコードを書いて実行し、24/7 の AI チューターから瞬時にサポートを受け、ウェブまたはアプリで続きから学習できます。
- コース
- 30
- レッスン
- 120
よくある質問
「単方向連結リスト」レッスンは無料ですか？
はい。「単方向連結リスト」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Zig Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Zig Academyコースには全4レッスンが含まれています。
「単方向連結リスト」で何を学びますか？
ノード、所有権、走査について学びます ブラウザで直接実行するハンズオンコードでZig Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Zig Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのZig Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「単方向連結リスト」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このZig Academyレッスンでコードを書いて実行できますか？
はい。すべてのZig Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。