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

Присмотрись к строке

*pcur = (*pcur)->next

Можешь в дебаге посмотреть этот свой лист на 3 элемента при удалении среднего, и где там какой некст будет.

Компа к сожалению сейчас нет, но думаю что *pcur станет адресом следующего элемента

А тут тогда что будет?

pcur = &(*pcur)->next

Не, у меня ошибка в объявлении, видимо от жары моск ничерта не работает, pcur это указатель на указатель и соответственно объявление struct item **pcur;

pcur=&(*pcur)->next адрес следующего элемента тоже (: , не, действительно приду домой и в дебаге гляну…

struct item pcur;

Нет (возможно, корень недопонимания именно тут ;) ).

struct item **pcur;

не могу понять как

pcur — это указатель на указатель на struct item,
*pcur — это указатель на struct item,
*pcur = (*pcur)->next; — это исключение элемента из списка, изменение поля next (или головы first),
pcur = &(*pcur)->next; — переход к адресу next (на следующий элемент).

Если читали паскалевскую часть:

var
  p: ^PItem;
  t: PItem;
//...
  p := @first;
  while p^ <> nil do begin
    if p^^.data < 0 then begin
      t := p^;
      p^ := p^^.next;
      Dispose(t);
    end else
      p := @(p^^.next);
  end;

по книге А.В. Столярова

Не стоит. Научитель bad practice и неверной терминологии. Возьмите Кнута.

pcur=&(*pcur)->next адрес следующего элемента тоже (:

Нет, это адрес самого поля next элемента:

pcur=&( (*pcur)->next )

Нет, у тебя разница между хм, как бы объяснить заменить указатель и заменить значение по указателю.

ссылается на адрес которого уже нет

*pcur = (*pcur)->next;

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

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

всегда хранится указатель на предыдущий элемент

повнимательнее с кванторами общности ;)
например, в примере ТС «указатель на предыдущий элемент» не хранится. Но если это утверждение ошибочно на ваш взгляд, прошу просто показать, «указатель на предыдущий элемент» хранится где?

PS. Известно, что о терминах не спорят ;-) Обычно очевидно, что «предыдущий» — это тот, что перед текущим и «дважды перед» следующим.
PPS. Если исправить на «всегда хранится или может быть вычислен указатель на предыдущий элемент», то претензий нет.

пример вообще кривой.

это что?

struct item pcur;

тут должен быть указатель на структуру, а не сама структура.

и как это понимать, если верно предыдущее.

struct item *tmp = *pcur;

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

и кстати в этом его кривом коде нет апдейта предыдущего элемента. у него предыдущий элемент показывает на удаленный элемент списка. список удачно разрушен.

тут должен быть указатель на структуру, а не сама структура

Нет. Тут должен быть указатель на указатель на структуру:

struct item **pcur;

в этом его кривом коде нет апдейта предыдущего элемента. у него предыдущий элемент показывает на удаленный элемент списка. список удачно разрушен.

Если учесть предыдущее замечание, нет. При удалении элемента список остается корректным, связность не нарушается.

Впрочем, об этом уже написано выше. Тему не читай, сразу отвечай…

в мне предлагаете делать выводы по неверноему коду? поправьте его сначала. он неверен в первой же строке.

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

канонически нужен только указатель на текущий и предыдущий, если есть операции удаления или вставки.

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

Списки бывают как двусвязными, так и односвязными, в последних указатель на предедущий элемент не хранится. Это не мешает вставлять и удалять в таком списке элементы. Советую подучить матчасть и такой ерунды боьше не писать:

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

поправьте его сначала

Я поправил. См. Помогите разобраться с односвязным списком. (комментарий)

Вы предлагаете писать:

var
  p, t: PItem;
//...
  while (first <> nil) and (first^.data < 0) do begin
    t := first;
    first := first^.next;
    Dispose(t);
  end;
  if first = nil then Exit;
  p := first;
  while p^.next <> nil do
    if p^.next^.data < 0 then begin
      t := p^.next;
      p^.next := p^.next^.next;
      Dispose(t);
    end else
      p := p^.next;

var
  p, pp, t: PItem;
//...
  while (first <> nil) and (first^.data < 0) do begin
    t := first;
    first := first^.next;
    Dispose(t);
  end;
  if first = nil then Exit;
  pp := first;
  p := pp^.next
  while p <> nil do
    if p^.data < 0 then begin
      t := p;
      pp^.next := p^.next;
      p := p^.next;
      Dispose(t);
    end else begin
      pp := p;
      p := p^.next;
    end;

var
  p: ^PItem;
  t: PItem;
//...
  p := @first;
  while p^ <> nil do
    if p^^.data < 0 then begin
      t := p^;
      p^ := p^^.next;
      Dispose(t);
    end else
      p := @(p^^.next);

var
  p: ^PItem;
  t: PItem;
//...
  p := @first;
  while p^ <> nil do with p^^ do
    if data < 0 then begin
      t := p^;
      p^ := next;
      Dispose(t);
    end else
      p := @next;

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

да вы шо! речь у меня шла про хранение указателя на предыдущий при проходе по списку! а не в элементе списка.

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

чисто для хохмы попросил чатгпт выполнить запрос

«write in c removing element from a single linked list»

вижу прекрасное наличие указателя prev в функции removeNode. о чем и весь сырбор.

код не проверял, но вроде, если по диагонали - похоже.

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};

// Function to remove a node with a given key
void removeNode(struct Node** head_ref, int key) {
    // Store head node
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Changed head
        free(temp); // Free old head
        return;
    }

    // Search for the key to be deleted, keep track of the previous node
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If key was not present in linked list
    if (temp == NULL) return;

    // Unlink the node from linked list
    prev->next = temp->next;

    free(temp); // Free memory
}

// Function to push a new node to the linked list
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Create the linked list 1->2->3->4->5
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    printf("Linked list before removal: ");
    printList(head);

    // Remove node with data 3
    removeNode(&head, 3);

    printf("Linked list after removal: ");
    printList(head);

    return 0;
}

вот тут в цикле проходится список и апдейтится prev. вот тебе и «квантор общности».

 while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

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

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

Пример не тождественен заданию, сюрприз, removeNode() удаляет не больше одного элемента списка.
Задание же было немного иным: удалить элементы списка, имеющие отрицательные значения.
На всякий случай: «элементы» — это во множественном числе ;)

PS. Врямя, когда подобная ИИшница станет сколь-либо значимым аргументом, пока еще не наступило ;)

PPS. Тема совсем о другом: помочь ТС разобраться с тем кодом, что он привел в стартовом сообщении темы, с учетом исправленной опечатки **pcur.

Возьмите Кнута.

Лучше Тимофея Хирьянова. Он объяснятор от бога ИМХО.

https://www.youtube.com/watch?v=XmuZ_U_GLYY

вы программист или где. для вас расширить алгоритм с удаления одного элемента на удаление всех элементов…непосильная задача, полностью алгоритм переворачивающая?

неужели сложно поставить где-надо цикл, и удалить все?

или мне опять чатгпт для вас спрашивать? я спрашиваю чисто для вас ибо для меня тут вообще нет вопросов.

удаление отрицательных и удаление по равенству ключей… это разновидность операции по формальному условию. возражение ваше тут наивно и непринимается.

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

в сговоре с чатгпт просьба не подозревать.

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node
struct Node {
    int data;
    struct Node* next;
};

// Function to remove all nodes with a given key
void removeAllNodes(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // Traverse the list and remove nodes with the given key
    while (temp != NULL) {
        if (temp->data == key) {
            if (prev == NULL) {
                *head_ref = temp->next;
            } else {
                prev->next = temp->next;
            }
            struct Node* to_delete = temp;
            temp = temp->next;
            free(to_delete);
        } else {
            prev = temp;
            temp = temp->next;
        }
    }
}

// Function to push a new node to the linked list
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to print the linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head = NULL;

    // Create the linked list 1->2->3->4->5->3->3
    push(&head, 3);
    push(&head, 3);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    printf("Linked list before removal: ");
    printList(head);

    // Remove all nodes with data 3
    removeAllNodes(&head, 3);

    printf("Linked list after removal: ");
    printList(head);

    return 0;
}

для вас расширить алгоритм с удаления одного элемента на удаление всех элементов…

ага, сказав «А», потрудитесь дойти до «Б» ;)

полностью алгоритм переворачивающая?

вот заодно и посмотрим как оно бывает с похожестью одного на другое ;)

это разновидность операции по формальному условию. возражение ваше тут наивно и непринимается

это ваш офтопик не принимается ;)
А по существу высказаться забыли... Зачем приходил? Чего хотел? ;)

Зачем приходил? Чего хотел? ;)

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

Это сильно лучше исходного?

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

а как оно будет если на руст переписать?

не апдейтится предыдущий-то. он указывает на удаленный. и не на надо делать двойной указатель.

*pcur - это двойной указатель на текущий. раз вы сравниваете

(*pcur)->data == key

 struct Node* tmp = *pcur;
            *pcur = (*pcur)->next;
            free(tmp);

тут вы просто удаляете текущий и переставляете текущий на следующий… но у вас не корректирован указатель у предыдущего элемента списка. он все еще показывает на удаленный.

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

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

не апдейтится предыдущий-то.

Навык чтения кода на С все еще требует совершенствования.
Верю, все получится, не бросайте на полпути...

Linked list before removal: 1 -> 2 -> 3 -> 4 -> 5 -> 3 -> 3 -> NULL
Linked list after removal: 1 -> 2 -> 4 -> 5 -> NULL

Думаю, без меня уже всё объяснили, могу лишь сказать, что указатели это сложно, указатели на указатели это ещё сложней, и лучше такие вещи пытаться понять самому, от того, что тебе их объяснят, ты их сам понимать не начнёшь. Выпиши на бумажке ячейки с памятью (адреса, значения), проходи по шагам алгоритм, обновляй значения в каждой ячейке, в какой-то момент в голове щёлкнет понимание. Лучше всего именно на бумажке это всё делать, проигрывая алгоритм в голове. Помни, что указатель это просто двухбайтовое значение (ну не обязательно двухбайтовое, нынче чаще четырёх или восьми-байтовое, но для понимания алгоритма проще так).

            struct Node* tmp = *pcur;
            *pcur = (*pcur)->next;
            free(tmp);

тут вы ... переставляете текущий на следующий… но у вас не корректирован указатель у предыдущего элемента списка. он все еще показывает на удаленный.

Это заблуждение.
*pcur имеет тип (struct Node*) и указывает в начале алгоритма на голову списка, а затем на поля next его элементов. Модификация *pcur — это модификация головы списка или поля next — то самое «корректирование указателя у предыдущего элемента списка».

Перестановка «текущего на следующий» выполняется, когда не нужно удалять элемент, при этом меняется pcur (а не *pcur):

            pcur = &(*pcur)->next;

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

А она точно медленее двух указателей?
Компилятор из двойной косвенности всегда (или хотя бы чаще) сгенерирует код хуже, чем для двух указателей туда же?

Повторюсь, сравнить одно с другим можно, например, тут:
https://godbolt.org/z/4s7h53z1P

Не стоит.

Чушь.

Научитель bad practice

Да? Докажите.

и неверной терминологии.

Терминологии верной или неверной не бывает. А у Столярова она всегда оговаривается в скобочках, сносках или во фрагментах текста без засечек.

Возьмите Кнута.

Она гораздо уже. Только по алгоритмам и структурам данных. Ни про работу с сокетами и сетью, ни про работу с процессами и потоками, ни про низкоуровневое программирование, ни про парадигмы там не написано. Также стоит отметить, что в качестве «заданий со звездочкой» Кнут предлагает порой не решенные задачи в научном сообществе на текущий момент.

struct ListNode *removeElements(struct ListNode *head, int val)
{
    if (!head)
        return head;
    
    // remove nodes in the beginning
    while (head && head->val == val)
        head = head->next;
    
    struct ListNode *curr = head;
    struct ListNode *prev = NULL;
    
    while (curr) {
        if (curr->val == val)
            prev->next = curr->next;
        else
            prev = curr;
        
        curr = curr->next;
    }
    
    return head;
}

pcur = &(*pcur)->next;

omg!

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

Разбирайтесь.

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

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

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

Воистину omg!

    // итерация 1: curr==head, prev==NULL
    while (curr) {
        if (curr->val == val)
            // итерация 1: условие было истиной
            prev->next = curr->next;  // prev->... разыменование нулевого указателя

скорее всего даст асм хуже канонического(от чатгпт)

я вам дал и тот, и другой. Дважды. Держите в третий раз:
https://godbolt.org/z/4s7h53z1P

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

У вас с логикой плохо. Прочитайте код до ‘итерация 1’ и поймите, что условие не будет истиной с первого раза.

ТС, если нравится упражняться в говнокодстве, то вот еще так можно:

public ListNode removeElements(ListNode head, int val) {
    if (head == null) return null;
    head.next = removeElements(head.next, val);
    return (head.val == val) ? head.next : head;
}

zx_gamer, есть что сказать?

Ты не понимаешь как использовать структуры данных. А значит не умеешь писать хороший код.

условие не будет истиной с первого раза

Согласен, не будет, ложная тревога.

Другой момент: у ТС «владеющий» список, у вас «не владеющий».
В тех же условиях удаленные элементы — memory leak.
Или снова что-то не заметил?

Кроме предположений ничего в ответ не получил ;)

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

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

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

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

Да? Докажите.

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

Терминологии верной или неверной не бывает.

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

Наезд зачетный, но мой вопрос все еще в силе :)

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

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

(*curr)->key ///два чтения памяти

а в каноническом алгоритме «селектор доступа» это просто адрес текущего и то же самое пишется как

curr->key ///одно чтение

но в каноническом алгоритме адрес prev хранится явно, а у вас он сам curr фактически.

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

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

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

Вы читать умеете? Он последний раз программировал НА ПАСКАЛЕ в 90х. А на других языках он пишет и сейчас. Например он написал очень интересную библиотеку http://www.intelib.org для C++, которая позволяет в C++ писать на Intelib Lisp.

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

Никакой отсебятины тут нет. Это вполне известная концепция. Обычно понимается после изучения функциональных языков (вроде Lisp). Причем в книгах по функциональным языкам это именно так и называется «побочный эффект» и именно в том смысле.

А суть тут очень проста: в языке Си все имеет побочный эффект.

int a, b;
a = b; /* Эта запись возвращает int */

То есть мы используем, выражаясь по плюсовому, operator= не для того, чтобы вычислить значение функции, а главным образом для того, чтобы что-то чему-то присвоить.

А, например, в Паскале такого нет. := присваивает и ничего не возвращает. И это меняет образ мышления. В Паскале никто не возвращает коды ошибок как в Си как результат выполнения функции. Ведь printf ведь вызывают, чтобы он на stdout что-то напечатал, а не чтобы получить код ошибки.

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

Огосподи. Бегом в школу! Давайте, расскажите еще что в C и С++ не может быть pure function, потому что одно из условий - отсутствие побочных эффектов.

Вот такие вот как вы и вырастают на его говнокнигах.

Огосподи. Бегом в школу! Давайте, расскажите еще что в C и С++ не может быть pure function, потому что одно из условий - отсутствие побочных эффектов.

Чистая функция-то может быть. Речь про то, как язык влияет на мышление. Например на том же Паскале вы не увидите код, в котором функций возвращает ошибку: вы увидите процедуру, которая получает адрес переменной, в которую помещается ошибка.

Но дело не только в функциях, но и в выражениях. (a = b) не просто в a помещает b, но и возвращает a. В правильности этого решения сомневался Деннис Ритчи до смерти.

Вот такие вот как вы и вырастают на его говнокнигах.

Fun fact: я не учился языку Си по его книгам.

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

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

Посмотрите уже в словаре определение чистой функции и не распространяйте всякий бред.

(a = b) не просто в a помещает b, но и возвращает a.

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

a = b = c = d = e+f;

или

if (a = b) ....