0Pricing
Zig Academy · Урок

Односвязный список

Узлы, владение и обход.

«Односвязный список» — бесплатный урок Zig Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Zig Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Zig Academy содержит 4 уроков всего.

Что такое связный список

Односвязный список соединяет значения: каждый узел хранит значение и указатель на следующий узел либо null в конце. 🔗

Определите Node

Node — это структура со значением и необязательным указателем на следующий узел. Необязательность означает, что последний узел указывает на null.

const Node = struct {
    value: i32,
    next: ?*Node,
};

Почему указатель необязательный

Конструкция ?*Node позволяет безопасно завершить цепочку. Специальное сигнальное значение для обозначения конца не требуется.

next: ?*Node

List отслеживает начало

Сам List хранит только первый узел, называемый начальным, и распределитель, которому принадлежат все узлы.

const List = struct {
    head: ?*Node,
    alloc: std.mem.Allocator,
};

Выделите один узел

Чтобы добавить значение, попросите распределитель create один Node в куче. В результате вы получите указатель на новое хранилище.

const node = try self.alloc.create(Node);

Добавьте элемент в начало

Самая дешёвая вставка выполняется в начале: направьте новый узел на старый начальный узел, а затем сделайте его новым начальным узлом. Это выполняется за постоянное время.

node.* = .{ .value = v, .next = self.head };
self.head = node;

Пройдите по цепочке

Для обхода начните с начального узла и переходите по каждому указателю next, пока не достигнете null. Цикл while хорошо подходит для этого.

var cur = self.head;
while (cur) |n| {
    std.debug.print("{d}\n", .{n.value});
    cur = n.next;
}

Захват раскрывает optional

Запись while (cur) |n| выполняет тело, пока cur не равен null, а n является раскрытым указателем. Цикл завершается на null.

while (cur) |n| { ... }

Вам принадлежит каждый узел

Каждый узел был создан распределителем, поэтому каждый нужно вернуть. Если забыть хотя бы один, распределитель для тестирования сообщит об утечке.

Освободите весь список

В 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 };
    };
}

Быстрая проверка

Вы освобождаете узлы связного списка по одному. Что нужно сделать перед уничтожением каждого узла?

Итоги

Узлы хранят значение и необязательный указатель next. List отслеживает начальный узел и распределитель, добавляет элементы в начало и освобождает узлы по одному. 🎯

Часто задаваемые вопросы

Урок «Односвязный список» бесплатный?

Да — полный текст урока «Односвязный список» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Zig Academy, подпишись на CoddyKit PRO. Курс Zig Academy содержит 4 уроков всего.

Чему я научусь в уроке «Односвязный список»?

Узлы, владение и обход. Ты практикуешь Zig Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Zig Academy?

Предыдущий опыт не требуется. Zig Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Односвязный список»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Zig Academy?

Да. Каждый урок Zig Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Обобщённый стек с нуля
  2. Односвязный список
  3. Использование HashMap и AutoHashMap
  4. Профилирование и компромиссы безопасности
← Назад к Zig Academy