Linked lists

English

Nodes joined by pointers

A linked list is a chain of small structs called nodes, scattered around the heap.
Each node holds a value and a pointer to the next node. Follow the pointers to walk the list.
Unlike an array, a list can grow one node at a time without moving the others.

Русский

Узлы, соединённые указателями

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

English

A self-referential struct

A node is a struct that contains a pointer to its own type:
struct Node { int data; struct Node *next; }; — data is the value, next points to the following node.
This is given for you as Node in each starter. The last node's next is NULL.

Русский

Самореферентная структура

Узел — это структура, содержащая указатель на сам тип:
struct Node { int data; struct Node *next; }; — data является значением, next указывает на следующий узел.
Это предоставляется вам как Node в каждом старте. Последний узел имеет next = NULL.

English

head and the NULL end

A single pointer, the head, points to the first node. From there you reach the rest.
The very last node points to NULL, which marks the end of the list.
An empty list is just head == NULL — there are no nodes at all.

Русский

Head (голова) и NULL конец

Один указатель, head (голова), указывает на первый узел. Оттуда вы достигаете остальных.
Самый последний узел указывает на NULL, что обозначает конец списка.
Пустой список — это просто head == NULL; узлов нет совсем.

#include <stdio.h>

typedef struct Node { int data; struct Node *next; } Node;

int main(void) {
    // A tiny list on the stack: 10 -> 20 -> 30 -> NULL
    Node n3 = {30, NULL};
    Node n2 = {20, &n3};
    Node n1 = {10, &n2};
    const Node *head = &n1;

    // Walk it: follow ->next until NULL, counting nodes
    int count = 0;
    const Node *cur = head;    // start at the head
    while (cur != NULL) {      // stop at the NULL end
        count++;
        cur = cur->next;       // step to the next node
    }
    printf("length = %d\n", count);   // length = 3
    return 0;
}

English

Adding a node at the front

To add to the front, make a new node, point its next at the old head, and return the new node as the new head.
This is fast — it does not touch any other node.
Because the head changes, the function returns the new head, and the caller saves it.

Русский

Добавление узла в начало

Чтобы добавить в начало, создайте новый узел, направьте его next на старый head, и верните новый узел как новый head.
Это быстро — оно не затрагивает другие узлы.
Поскольку head изменяется, функция возвращает новый head, и вызывающий код сохраняет его.

English

Common mistakes

Never lose the head pointer, or the whole list is unreachable.
Free every node; the last node points to NULL.

Русский

Распространенные ошибки

Никогда не теряйте указатель head, иначе весь список станет недоступным.
Освободите каждый узел; последний узел указывает на NULL.

English

Now you try

Walk a list with a cur pointer and cur = cur->next, stopping at NULL.
New nodes come from malloc(sizeof(Node)); the checker frees the list. Do not write a main.

Русский

Теперь попробуйте сами

Проходите по списку с помощью указателя cur и cur = cur->next, останавливаясь при NULL.
Новые узлы поступают из malloc(sizeof(Node)); проверчик освобождает список. Не пишите не main.

Explore · ⁨Исследовать⁩

Nodes and pointers

Each node points to the next; insert/delete by re-linking.

Complete int length(const Node *head) so it counts the nodes in the list (0 for an empty list). Walk with ->next until NULL. The Node type is given. Do not write a main.

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Count the nodes from head (0 for NULL). Do not write main(). */
int length(const Node *head) {
    return 0;   /* walk with ->next until NULL */
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Complete int sum_list(const Node *head) so it returns the total of every node's data (0 for an empty list). The Node type is given. Do not write a main.

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Total every node's data (0 for NULL). Do not write main(). */
int sum_list(const Node *head) {
    return 0;   /* walk and add cur->data */
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Complete Node *push_front(Node *head, int value) so it makes a new node (with malloc), points its next at the old head, and returns it as the new head. The checker frees the list. Do not write a main.

#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

/* Make a new node holding value, link it before head, return it. Do not write main(). */
Node *push_front(Node *head, int value) {
    /* malloc a Node, set its data and next, return it */
    return head;
}

Click Run to see the output here. · ⁨Нажмите Запустить, чтобы увидеть результат здесь.⁩

Nodes joined by pointers

Узлы, соединённые указателями

A self-referential struct

Самореферентная структура

head and the NULL end

Head (голова) и NULL конец

Adding a node at the front

Добавление узла в начало

Common mistakes

Распространенные ошибки

Now you try

Теперь попробуйте сами

Nodes and pointers

Handout · ⁨Раздаточный материал⁩

Log in or create account · ⁨Войти или создать аккаунт⁩

Your subject · ⁨Ваш предмет⁩

All sections · ⁨Все разделы⁩

Feedback & help · ⁨Обратная связь и помощь⁩