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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Рецензия / Мнение/ Перевод https:/ / **********/ gallery/ thinkpad-x220-tablet-porn-gzoEAjs . . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .

@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

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

Решение