Singly linked list, deleting an element, C++

Good afternoon. There is such a code for deleting an item from the list

void del(int n) // n - позиция удаляемого элемента
{
    // Mass - объекты, которые хранятся в списке
    Mass *temp = HEAD, *helping = temp;

    if ((temp != NULL) && (n <= size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
    {
        for (int i = 0; i < n; i++)
        {
            helping = temp; // предыдущее значение temp
            temp = temp->Next;
        }

        if (temp == HEAD) // если элемент который надо удалить первый
        {
            helping = temp;
            temp = temp->Next;
            HEAD = temp;
            cout << "Удаляемый элемент: " << *helping;
            free(helping);
            size--; // уменьшаем размер списка
            return;
        }
        else // иначе, если он в середине или конце
        {
            // 0 1 2 3 4
            // вводится, к примеру, 2. т.е. helping = 1, temp = 2;
            free(temp);
            size--;
            // 0 1 .. 3 4
            helping->Next = helping->Next->Next;
            // т.е. теперь 1 указывает не на 2, а на 3.
        }
    }

The beginning is worked out well, i.e. it removes the first element, but for some reason it does not work out the other elements. I think about it for the second day, my head is boiling. I imagine the algorithm like this:

  1. Deleting the{[9] element]}
  2. We shift the rest of the list items (from the left to the deleted item or from the right?)

Or even do so 1. Deleting the{[4] element]}

  1. We go through the entire list until we come across a remote one (NULL)
  2. We transfer the link from the element before the deleted one to the element after the deleted one (bypassing the deleted element itself)
  3. Repeat step 3 until there are no zero elements. Given that the end of the list we do not consider.

Thank you all so much for your help! I discovered a lot of new things in working with pointers. Special thanks

@MichaelPak for pointing out the direction in which to dig and pointing out a specific error and a detailed explanation,

@Mike for scolding me for using an irrational algorithm

@alexolut for suggesting the difference in between ned delete and malloc free

@Vlad from Moscow for a detailed solution to the problem and a cool idea about using an unsigned variable (I did so in the end).

I am very grateful to you, thank you very much!

Author: whalemare, 2015-11-18
Source

3 answers

In principle, you have written everything correctly except for two points.

The first is that the number of the element being deleted cannot be equal to size . size is always one more than the number of the last existing element, since the numbering of the elements starts from 0.

Therefore, instead of the condition

    if ((temp != NULL) && (n <= size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка

You should write

    if ((temp != NULL) && (n < size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
                          ^^^^^^^^

You would make your life easier if the variable size had an unsigned integer type. In this case, there would be no there is no need to check that n >= 0. You could declare size as having the type unsigned int or, as is usually the case, size_t.

The second is that you are trying to refer to an already deleted element in the sentence

helping->Next = helping->Next->Next;

You should first set the value of the field Next, and only then delete the element.

With that said, the function might look like this

void del(int n) // n - позиция удаляемого элемента
{
    if ((HEAD != NULL) && (n < size) && (n >= 0)) // если по этому номеру что-то лежит и этот элемент внутри списка
    {
        // Mass - объекты, которые хранятся в списке
        Mass *temp = HEAD, *helping = HEAD;

        for (int i = 0; i < n; i++)
        {
            helping = temp; // предыдущее значение temp
            temp = temp->Next;
        }

        if (temp == HEAD) // если элемент который надо удалить первый
        {
            HEAD = temp->Next;
        }
        else
        {
            helping->Next = temp->Next;
        }
        cout << "Удаляемый элемент: " << *temp;
        free(temp);
        size--; // уменьшаем размер списка
    }
}
 1
Author: Vlad from Moscow, 2015-11-18 09:42:07

Lists are worse than arrays in that you can't access an element immediately in lists: to do this, you need to go through the previous elements. Therefore, the deletion process looks like this:

  1. You reach the element whose link NEXT points to the element being deleted;
  2. Assign the link NEXT of the deleted element to the link of the previous element;
  3. Deleting an element;
  4. Profit!

So from such a picture:

           +------+    +------+    +------+  
           |данные|    |данные|    |данные|
    \/\/\->+------+    +------+    +------+
           |      |--->|      |--->|  0   |
           +------+    +------+    +------+

It turns out such a:

           +------+    +------+    +------+
           |данные|    |удален|    |данные|
    \/\/\->+------+    +------+    +------+
           |      |    |  0   | .->|  0   |
           +------+    +------+ |  +------+
                 \______________|

Your problem is that you first delete the element, and then try to find a link to the next one, that is, helping->Next->Next after deleting it no longer points to the 3rd element. Try to work with the pointers first, and then delete the element.

 7
Author: MichaelPak, 2015-11-18 07:07:35

2 Times to run along the chain is too much. It is better to remember the previous element as you move along the chain.

Mass *temp=HEAD,*prev=NULL;
int i=0;
while(temp && i<n)
 {
  i++;
  prev=temp; // Запоминаем предыдущий в цепочке
  temp=temp->next;
 }
if(!temp) // Элемент не найден
 {
  return;
 }
if(HEAD==temp)
 {
  HEAD=temp->next;
 } else
 {
  if(prev) prev->next=temp->next;
 }
cout << "Удаляемый элемент: " << *temp;
size--;
free(temp);
 5
Author: Mike, 2015-11-18 07:23:06