Удаление последнего элемента из однонаправленного линейного списка

@Jefe · Регистрация: 05.06.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте, удаляю значится элемент:
(x - порядковый номер удаляемого элемента, начиная с 1. records_cnt - количество элементов в списке, например 5)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    if (x > 0 && x <= records_cnt)
    {
        ListNode<Data>* node = _head;
        ListNode<Data>* temp = _head;
        
        for (int i = 1; i < x; i++)
        {
            node = temp; // предыдущее значение temp
            temp = temp->next;
        }
 
        if (temp == _head) // если элемент который надо удалить - первый
        {
            _head = temp->next;
        }
        else
        {
            node->next = temp->next;
        }
        
        free(temp);
        records_cnt--;
    }

Если удаляю первый элемент - всё ок, элемент удалён, в список спокойно добавляются новые элементы.
Если удаляю элементы с 2го по 4й - всё ок, элемент удалён, в список спокойно добавляются новые элементы.
Если удаляю последний элемент - элемент удаляется, но в список добавить новые элементы больше невозможно.

Как правильно удалить последний элемент списка, что бы не сломать список?

@nmcf · 31.10.2018, 13:37

Отладчиком смотри.

@Jefe · 31.10.2018, 14:55 **[ТС]**

nmcf, посмотрел, но ничего не увидел

@nmcf · 31.10.2018, 15:26

Ты же говоришь, что элементы после не добавить. Ну вот и смотри отладчиком, почему не добавляется.

@SuperKir · 31.10.2018, 16:08

Работа с односвязными кольцевыми списками
Вытащи то, что нужно тебе.

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

@Jefe · 31.10.2018, 16:32 **[ТС]**

Сообщение от SuperKir

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

Добавляю так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void List::Add()                                // Добавление нового элемента
{
    Data node;
    
    node.val1 = 1;
        node.val2 = 2;
    node.val3 = 3;
        ...
    
    ListNode<Data>* newNode = new ListNode<Data>;
    newNode->data = node;
    newNode->next = NULL;
    if (_tail)
        _tail->next = newNode;
    if (!_head)
        _head = newNode;
    _tail = newNode;
}

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

@SuperKir · 31.10.2018, 17:19

Jefe, ужасно, всё ужасно.
А что, когда 1 узел, он не хвостовой теперь уже, только головной? И хвост и голова должны быть по одному адресу тогда.
Ты добавляешь в конец, но при этом, когда элемент крайний удаляешь, хвосту адрес предпоследнего не передаешь, поэтому он станет мусорным и будет бЯда...

@Jefe · 31.10.2018, 17:28 **[ТС]**

SuperKir, знаю, что ужасно.
Пробовал так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
if (temp == _head)
        {
            _head = temp->next;
        }
        else if (x < records_cnt)
        {
            node->next = temp->next;
        }
        else
        {
            _tail = node;
        }
        
        free(temp);

Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.

@sty4ent · 31.10.2018, 19:03

Сообщение от Jefe

Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.

При удалении указатель _tail не пробовали обновлять?

@Jefe · 31.10.2018, 19:07 **[ТС]**

Сообщение от sty4ent

При удалении указатель _tail не пробовали обновлять?

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

Но видимо что-то не так.

@sty4ent · 31.10.2018, 19:18

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
 
template<typename T>
class List {
private:
    struct Node {
        Node(const T& value) {
            next = nullptr;
            data = value;
        }
 
        T data;
        Node* next{nullptr};
    };
 
public:
    class Iterator {
    public:
        Iterator(Node* node) : _node(node) {
        }
        
        bool operator!=(const Iterator& it) {
            return _node != it._node;
        }
        
        Iterator operator++(int) {
           Iterator result = *this;
           _node = _node->next;
           return result;
        }    
        
        T& operator*() {
            return _node->data;
        }
        
    private:
        Node* _node;
    };
 
public:
    void remove_by_index(int index) {
        if ((index <= 0) || (index > _size)) {
            return;
        }
        
        Node* prev = nullptr;
        Node* temp = _head;
        
        for (int x = 1; x != index; x++) {
            prev = temp;
            temp = temp->next;
        }
        
        if (temp == _tail) {
            _tail = prev;
        }
        
        if (temp == _head) {
            _head = _head->next;
        } else {
            prev->next = temp->next;
        }
 
        delete temp;
        _size--;
    }
 
    void push_back(const T& value) {
        Node* new_node = new Node(value);
        if (_tail) {
            _tail->next = new_node;
        } else {
            _head = new_node;
        }
        _tail = new_node;
        _size++;
    }
    
    Iterator begin() {
        return Iterator(_head);
    }
    
    Iterator end() {
        return Iterator(nullptr);
    }
 
private:
    int _size{0};
    Node* _head{nullptr};
    Node* _tail{nullptr};
};
 
int main() {
    struct MyData {
        int id;
    } data;
    List<MyData> list;
    
    for (int x = 1; x <= 5; x++) {
        data.id = x;
        list.push_back(data);
    }
    
    MyData new_value{100};
    list.remove_by_index(5);
    list.push_back(new_value);
 
    for (auto i = list.begin(); i != list.end(); i++) {
        const MyData& d = *i;
        std::cout << d.id << " ";
    }
    std::cout << "\n";
    
    return 0;
}

Добавлено через 10 минут

Сообщение от Jefe

if (temp == _head)
* * * * {
* * * * * * _head = temp->next;
* * * * }
* * * * else if (x < records_cnt)
* * * * {
* * * * * * node->next = temp->next;
* * * * }
* * * * else
* * * * {
* * * * * * _tail = node;
* * * * }
free(temp);
Но при попытке отобразить то, что после этого получается ловлю исключение bad_alloc.
Пока не понимаю как правильно это исправить.

Здесь как минимум надо обновить ещё указатель на следующий элемент (_tail->next = nullptr).

@Jefe · 01.11.2018, 14:42 **[ТС]**

sty4ent, спасибо.
Окончательный рабочий вариант:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
if (x > 0 && x <= records_cnt)
    {
        ListNode<Data>* node = _head;
        ListNode<Data>* temp = _head;
        
        for (int i = 1; i < x; i++)
        {
            node = temp;
            temp = temp->next;
        }
 
        if (temp == _head)
        {
            _head = temp->next;
        }
        else if (x < records_cnt)
        {
            node->next = temp->next;
        }
        else
        {
            _tail = node;
            _tail->next = nullptr;
        }
        
        free(temp);
        records_cnt--;
    }

@sty4ent · 02.11.2018, 15:43

Сообщение от Jefe

Окончательный рабочий вариант:

Не уверен я в этом. Создайте список из 1 элемента. Потом удалите этот элемент. Затем попробуйте добавить ещё что-то. Предполагается, что для добавления элементов используется та функция, которая представлена выше.

@Jefe · 02.11.2018, 17:09 **[ТС]**

Сообщение от sty4ent

Не уверен я в этом.

Нет, и с одним элементом работает.

Новые блоги и статьи Все статьи Все блоги /
Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .	Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	31.10.2018, 13:37
	Отладчиком смотри. 0

@Jefe 311 / 271 / 118 Регистрация: 05.06.2013 Сообщений: 868
	31.10.2018, 14:55 [ТС]
	nmcf, посмотрел, но ничего не увидел 0

@nmcf 7804 / 6568 / 2988 Регистрация: 14.04.2014 Сообщений: 28,705
	31.10.2018, 15:26
	Ты же говоришь, что элементы после не добавить. Ну вот и смотри отладчиком, почему не добавляется. 0

@SuperKir 475 / 427 / 290 Регистрация: 10.03.2015 Сообщений: 1,782
	31.10.2018, 16:08
	Работа с односвязными кольцевыми списками Вытащи то, что нужно тебе. Не понятно, куда ты добавляешь элементы, и почему они не добавляются вдруг, если удалился последний элемент а присутствует только голова - значит добавляются в начало... 0

@SuperKir 475 / 427 / 290 Регистрация: 10.03.2015 Сообщений: 1,782
	31.10.2018, 17:19
	Jefe, ужасно, всё ужасно. А что, когда 1 узел, он не хвостовой теперь уже, только головной? И хвост и голова должны быть по одному адресу тогда. Ты добавляешь в конец, но при этом, когда элемент крайний удаляешь, хвосту адрес предпоследнего не передаешь, поэтому он станет мусорным и будет бЯда... 0

Удаление последнего элемента из однонаправленного линейного списка

Решение