Помогите разобраться с односвязным списком.

Это базовые структуры в сришке. Это статический язык, те массивы у тебя определенного размера, например, char arr[100], а, если, тебе требуется динамика, то приходится извращаться так. В этих односторонних и двухсторонних списках нет первого или какого-то там элемента, там структура хранит ссылки на следующий и предыдущий элементы, а так же какие-то значения… В высокоуровневых языках это применяется примерно не реже чем никогда

Бже, да он даже на своем сайте пишет, что он не программист. Единственное как он программировал - это на паскале в 90х. А полез писать книги по программированию: Американский суд частично удовлетворил антимонопольный иск Epic Games к Apple (комментарий)

Он пишет «я последний раз на Паскале писал в первой половине девяностых»

Ты пишешь «Единственное как он программировал - это на паскале в 90х»

Могу только сказать, что ты точно не программист, если основами логики не владеешь.

А еще, расскажите мне зачем нужен singly linked list кроме собеседований?

А какую альтернативу связному списку ты бы предложил?

А какую альтернативу связному списку ты бы предложил?

Подозреваю что товарищ конкретно о single-linked list (aka std::forward_list<>) в противовес double-linked list (aka std::list<>) речь ведёт, и в чём-то я с ним солидарен так как используется он действительно крайне редко.

Эх, ведь зарекался я…

и не мучьте ж. двойной косвенностью. она тупо медленней, за счет лишнего разыменования, чем просто указатель.

Думается мне что то что вы отыграете убрав «лишний» dereference будет съедено первым же free(). И код от Столярова объективно чище и понятнее.

чатгпт правильно написал. смотрите у него

Полное Г написал ваш чат-жпт. Не надо так делать, вообще никогда. Если уж и разворачивать то так чтобы if (prev) не проверялось на каждой итерации после того как он стал не nullptr, ie резать цикл на 2: «до» и «после».

Вы сами себе противоречите.

Где?

Думается мне что то что вы отыграете убрав «лишний» dereference будет съедено первым же free().

а если там не будет free? а если будет один free на миллион элементов? а если там вообще не будет удалений, а будет вставка элемента.

Полное Г написал ваш чат-жпт.

чатгпт сам ничего не пишет. он просто показывает, как пишут другие в таких случаях. то, что было в его тренировочных датасетах, то он и напишет.

в «коде столярова» три лишних операции чтения памяти как минимум: везде где есть адресное выражение - (*pcur), и это при любой ветке if.

даже если ни один ключ не подойдет, вы делаете вместо трех(сравнение текущего на нул, проверка ключа, переписывание текущего) обращений к памяти, шесть в лучшем случае! канонический способ вместо трех лишних обращений делает переписывание из регистра в регистр.

 while (*pcur)
        if ((*pcur)->data == key) {
            struct Node* tmp = *pcur;
            *pcur = (*pcur)->next;
            free(tmp);
        } else
            pcur = &(*pcur)->next;

столярова спасает только то, что оптимизатор все равно его алгоритм переделает на канонический и что есть кеширование памяти.

Вы слепой или прикалываетесь?

в языке Си все имеет побочный эффект.

Чистая функция-то может быть.

В языках программирования чистая функция — это функция, которая:

• является детерминированной;
• не обладает побочными эффектами.

вы делаете вместо трех(сравнение текущего на нул, проверка ключа, переписывание текущего) обращений к памяти, шесть в лучшем случае!

Да перестаньте вы уже фантазировать. Где здесь «шесть в лучшем случае(!) обращений к памяти»?

читать меня не умеем?

столярова спасает только то, что оптимизатор все равно его алгоритм переделает на канонический и что есть кеширование памяти.

убери свой -02, и поставь -O0, и будет 6.

разве непонятно, что (*pcur) это лишнее чтение?

разве непонятно, что (*pcur) это лишнее чтение?

Абсолютно непонятно. Более того - приведённый пример прямо доказывает что это не так. Хочется вам дрручками добиваться оптимального asm’а в -O0, ну что ж - дело хозяйское, всех остальных интересуют исключительно билды с -O2 и выше.

Абсолютно непонятно.

а что непонятно? (*ptr) это операция вида

"прочитать из памяти по адресу, который лежит в переменной <ptr>"

в каноническом алгоритме адрес текущего хранится в регистре. а столяровском - адрес текущего хранится в памяти, на которую указывает регистр.

потому любой доступ к текущему у столярова требует дополнительного чтения из памяти. причем эта память относится к предыдушему элементу, а работает он с текущим(проверяет key и берет next), отсюда будут лишние проблемы с локальностью кеша(это если оптимизатором не привести алгоритм столярова к каноническому).

короче для обучения такой код негоден. он и неканоничен, и сложен для понимания за счет лишней косвенности. да и неэффективен.

убери свой -02, и поставь -O0, и будет 6

https://godbolt.org/z/K48jfs9Yj
почитайте и прослезитесь ;-)

С -O0 вариант с двумя явными указаталями тоже не блещет, да?

короче для обучения такой код негоден. он и неканоничен, и сложен для понимания за счет лишней косвенности.

Чего чего?? Он прост как пробка, и концептуально правилен - минимум moving parts. А вот то что вы всеми силами пытаетесь помешать компилятору делать его работу - вот ЭТО банально непрофессионально.

да и неэффективен.

Обалдеть. В каком месте?

С -O0 вариант с двумя явными указаталями тоже не блещет, да?

вы всерьез пытаетесь доказать, что косвенность это не чтение из памяти??? и что лишняя косвенность это просто накладной расход?

нафиг ваши листинги, вопрос совершенно технический.

код от чатгпт - наивный. совершенно не нужно держать в цикле проверку prev на нул, это очевидно. ее надо сделать только один раз.

код от столярова не имеет такой проверки из-за косвенности. но потом страдает от этой самой косвенности каждую итерацию.

то есть оба варианта страдают от «проблемы первого элемента» по своему.

А вот то что вы всеми силами пытаетесь помешать компилятору делать его работу - вот ЭТО банально непрофессионально.

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

А еще, расскажите мне зачем нужен singly linked list кроме собеседований?

Вот тут, например, пишут что

All doubly linked types of data structures (lists and tail queues)  additionally allow:
	     1.	  Insertion of a new entry before any element in the list.
	     2.	  O(1) removal of any entry in the list.
       However:
	     1.	  Each element requires	two pointers rather than one.
	     2.	  Code	size  and execution time of operations (except for re-
		  moval) is about twice	that of	the singly-linked  data-struc-
		  tures.

Неужели врут насчет «Code size and execution time of operations is about twice that of the singly-linked data-structures» ?

Не функция, а операторы.

можно где-то так:

Node *filter(Node *list,int (*condition)(Node *))
{
	Node *head=NULL,*tail=NULL;
	inline Node* filter_next1(Node *curr,Node *next) {
		if (condition(curr)) {
			free(curr);
		} else {
			head=tail=curr;
		}
		return next;
	}
	inline Node* filter_next2(Node *curr,Node *next) {
		if (condition(curr)) {
			free(curr);
		} else {
			tail=tail->next=curr;
		}
		return next;
	}
	while(head==NULL && list!=NULL)
		list=filter_next1(list,list->next);
	while(list!=NULL)
		list=filter_next2(list,list->next);
	if (tail!=NULL)
		tail->next=NULL;
	return head;
}

О боже! Чтобы понять этот код надо несколько раз прочитать. Почему нельзя было нормально написать:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode fake;
    fake.next = head;
    struct ListNode* prev = &fake;
    struct ListNode* cur = head;
    while (cur) {
        struct ListNode * next = cur->next;
        if (cur->val == val) {
            prev->next = next; free(cur);
        } else {
            prev = cur;
        }
        cur = next;
    }
    return fake.next;
}

Терминологии верной или неверной не бывает. Щито? Вот вам пример «отсебятины» от автора: Побочные эффекты функций

Что вам там показалось неверным?

Не просто крайне редко, а нигде :) Афаик даже в ядре линукса двусвязный.

Не знаю как фряшники умудрились реализовать список, что он в 2 раза стал медленнее :D Хотя, те еще макаки.

Не знаю как фряшники умудрились реализовать список, что он в 2 раза стал медленнее

Можешь тут посмотреть linux/drivers/scsi/aic7xxx/queue.h, там все на макросах

приду домой

Беспокоюсь, как дела?

Типа понять нафига у тебя в коде какой-то фейк проще?

«Data Structures and program design in C» (Kruse, Leroy). Have a happy searching. :)

Не знаю как фряшники умудрились реализовать список, что он в 2 раза стал медленнее :D Хотя, те еще макаки.

Решил проверить, так ли оно на самом деле. И вот что оказалось:

> Gemini, разработана ли ОС FreeBSD макаками ?

Макаки не разрабатывали операционную систему FreeBSD.
Это распространенное заблуждение, которое, возможно, возникло из-за того, что некоторые исследователи использовали макак для изучения аспектов дизайна и тестирования программного обеспечения.

На самом деле FreeBSD разработана командой людей, известных как FreeBSD Project.

Важно отметить, что FreeBSD - это сложная система, созданная в результате работы многих людей.
Вклад макак в эту систему, если он вообще был, был лишь косвенным.

Это нода перед head. Стандартный подход, видел много раз в литературе по алгоритмам. Понять проще, да.

Та я то понимаю что это фейковая голова, но я не могу сказать что оно понятнее чем код из ОП.

Непонятность кода в ОП воощбе имеет мало отношения к алгоритму, а исключительно к привычке хм думать в чертырех измерениях. Я когда в школе связанные списки и ссылки тыкал по книжкам тоже половину неодуплял. Но как-то постепенно рассосалось.

Та я то понимаю что это фейковая голова, но я не могу сказать что оно понятнее чем код из ОП.

смысл фейковой головы в том, чтобы не проверять на prev == null. с фейковой головой prev сразу ставится на нее, и цикл становится по элементам становится простым.

И?

Две страницы срача из-за удаление элемента по предикату хорошо показывает всратость сишки.

Две страницы срача из-за удаление элемента по предикату хорошо показывает суть ЛОРа

fixed

Две страницы срача из-за удаление элемента по предикату хорошо показывает всратость сишки.

и що ви предложите взамен?

И?

например через месяц можно получить забавный баг..архитекторы изменят нагрузку узла на int[100500] и софт иногда будет неуловимо падать.

вообще масса перспектив :-) можно обеспечить работой всех, от QA до безопасников

Но зачем мне объяснение фейковой головы?

Раст уже не модно, поэтому zig.

Название как-то по-фашистски звучит. Лучше уж vlang тогда.