'Base' forward list / «Базовый» односвязный список

@Mournful Max · Регистрация: 15.12.2015

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

Сейчас активно изучаю структуры данных : что это такое, зачем нужно, с чем едят...
Для лучшего понимания, решил сам реализовать некоторые из них. Начал с ( имхо ) самой простой — односвязного списка. «Базовый» в заголовке как бы намекает, что в моей реализации есть только базовый функционал. Если это не так — пишите, я готов исправить.
Тему создаю для всеобщего блага : 1) если найдутся какие-то недоработки или семантические ошибки в коде, то, надеюсь, меня поправят ; 2) если всплывет тема с просьбой «памагити список на C++» — вы знаете что делать.
Кстати, по поводу кода : повторяюсь, — критика приветствуется, любая.

Реализация разбита на 3 файла :

forward_list.hpp

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
#ifndef MY_FORWARD_LIST_HPP
#define MY_FORWARD_LIST_HPP
 
#include <cstddef>
 
namespace my
{
 
using Data_t = int ;
 
 
class Forward_list
{
    struct Node ;
 
    Forward_list( const Forward_list& )            = delete ;
    Forward_list& operator=( const Forward_list& ) = delete ;
 
public:
    Forward_list() ;
          Data_t& front()       ;
    const Data_t& front() const ;
    bool empty() const ;
    void clear() ;
    void push_front( const Data_t& data ) ;
    void pop_front() ;
    void remove( const Data_t& data ) ;
    std::size_t find( const Data_t& data ) const ;
    ~Forward_list() ;
 
private:
    Node* head ;
};
 
struct Forward_list::Node
{
    Node( const Data_t& data_, Node* next_ = nullptr ) ;
 
    Data_t data ;
    Node*  next ;
};
 
}
 
#include "forward_list.inl"
 
#endif /* MY_FORWARD_LIST_HPP */

forward_list.inl

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
#ifndef MY_FORWARD_LIST_INL
#define MY_FORWARD_LIST_INL
 
#include "forward_list.hpp"
 
namespace my
{
 
inline Forward_list::Forward_list()
: head( nullptr )
{
}
 
inline Data_t& Forward_list::front()
{
    return head->data ;
}
 
inline const Data_t& Forward_list::front() const
{
    return head->data ;
}
 
inline bool Forward_list::empty() const
{
    return head == nullptr ;
}
 
inline Forward_list::~Forward_list()
{
    clear() ;
}
 
 
/* ---- Forward_list::Node's space ---- */
inline Forward_list::Node::Node( const Data_t& data_, Node* next_ )
: data( data_ ), next( next_ )
{
}
 
}
 
#endif /* MY_FORWARD_LIST_INL */

forward_list.cpp

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
#include "forward_list.hpp"
 
namespace my
{
 
void Forward_list::clear()
{
    auto expected = head ;
 
    while ( expected )
    {
        expected = expected->next ;
        delete head ;
        head = expected ;
    }
}
 
void Forward_list::push_front( const Data_t& data )
{
    auto new_head = new Node( data ) ;
 
    if ( head )
        new_head->next = head ;
 
    head = new_head ;
}
 
void Forward_list::pop_front()
{
    auto dead_head = head ;
    head = head->next ;
    delete dead_head ;
}
 
void Forward_list::remove( const Data_t& data )
{
    decltype ( head ) sought      = head,
                      prev_sought = nullptr ;
 
    while ( sought )
    {
        if ( sought->data == data )
        {
            if ( sought == head )
                head = sought->next ;
 
            if ( prev_sought )
                prev_sought->next = sought->next ;
 
            auto dead_sought = sought ;
            sought = sought->next ;
 
            delete dead_sought ;
            continue ;
        }
 
        prev_sought = sought ;
        sought = sought->next ;
    }
}
 
std::size_t Forward_list::find( const Data_t& data ) const
{
    std::size_t count  = 0 ;
    auto        sought = head ;
 
    while ( sought )
    {
        if ( sought->data == data )
            count += 1 ;
 
        sought = sought->next ;
    }
 
    return count ;
}
 
}

Короткая документация :
Класс Forward_list имеет 1 конструктор — конструктор по умолчанию. ( На самом деле — 2, но сделаем вид, что Forward_list( Forward_list&& ) не существует )
Метод front() — возвращает последний добавленный элемент в список. Результат не определен, если список пуст. ( Перегружена для const Forward_list )
Метод empty() — возвращает булево значение true, если список пуст или false, если есть хотя бы один элемент.
Метод clear() — очищает список ( удаляет все элементы ).
Метод push_front() — добавляет элемент в начало списка.
Метод pop_front() — извлекает последний добавленный элемент из списка. Результат не определен, если список пуст.
Метод remove() — удаляет все элементы со значением, которое было передано аргументом.
Метод find() — возвращает кол-во элементов в списке со значением, которое было передано аргументом.
Деструктор «очищает» список — удаляет все элементы со списка. ( По сути, вызывает clear() )

Пример использования :

test.cpp

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
#include "forward_list.hpp"
#include <iostream>
 
#define CHECK( str, foo ) std::cout << str << " --> " << foo << std::endl
 
int main()
{
    my::Forward_list fl ;
 
    CHECK( ".empty()", fl.empty() ) ;
 
    fl.push_front( 42 ) ;
    fl.push_front( 42 ) ;
    fl.push_front( 42 ) ;
    fl.push_front( 45 ) ;
    fl.push_front( 46 ) ;
    fl.push_front( 47 ) ;
 
    CHECK( ".front()", fl.front() ) ;
 
    fl.pop_front() ;
    fl.pop_front() ;
 
    CHECK( ".front()", fl.front() ) ;
    CHECK( ".empty()", fl.empty() ) ;
    CHECK( ".find( 42 )", fl.find( 42 ) ) ;
 
    fl.remove( 45 ) ;
 
    CHECK( ".front()", fl.front() ) ;
    CHECK( ".empty()", fl.empty() ) ;
    CHECK( ".find( 45 )", fl.find( 45 ) ) ;
 
    fl.clear() ;
    CHECK( ".empty()", fl.empty() ) ;
 
    //std::cin.get() ;
}

Добавлено через 10 минут
Позже попробую внедрить в это дело итераторы. Тогда можно будет добавить полезных методов, которых, к сожалению, не хватает. Например, семантика метода find() совершенно противоречит моим словам :

Сообщение от Captain Maxee

в моей реализации есть только базовый функционал

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

Кстати, этот же метод заменится на привычный, который возвращает итератор на первый найденный элемент.

ValeryS · 04.09.2018, 06:19

Сообщение от Mournful Max

Метод front() — возвращает последний добавленный элемент в список. Результат не определен, если список пуст.

а лучше вернуть NULL
и не вижу метода типа find(поиск) а так же вставить(Add)
по списку методов похоже что реализован стек/очередь

@sourcerer · 04.09.2018, 06:21

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

а лучше вернуть NULL

Заканчивался 2018 год

nullptr же!

ValeryS · 04.09.2018, 06:24

пока я писал Mournful Max,сам заметил свои ошибки

Сообщение от Mournful Max

А то стек какой-то получался

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

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

nullptr же!

если человек сам реализует очередь, то скорее всего компилятор не поддерживает nullptr

@DrOffset · 04.09.2018, 09:21

Не по теме:

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

если человек сам реализует

Если человек сам реализует, то

Сообщение от Mournful Max

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

:)

@sourcerer · 04.09.2018, 09:30

Не по теме:

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

если человек сам реализует очередь, то скорее всего компилятор не поддерживает nullptr

Вовсе не обязательно. Вообще никак не связано же.

Croessmah · 04.09.2018, 10:23

Сообщение от Mournful Max

C++
1
2
3
4
5
6
7
void Forward_list::push_front( const Data_t& data )
{
    auto new_head = new Node( data ) ;
    if ( head )
        new_head->next = head ;
    head = new_head ;
}

Почему не использовать предназначенный для это конструктор Node?

C++
1
2
3
4
void Forward_list::push_front( const Data_t& data )
{
    head = new Node( data , head) ;
}

Для функций-членов empty, front можно добавить noexcept.

C++
1
decltype ( head ) sought = head

decltype ради decltype? Зачем это?

C++
1
2
3
4
5
6
7
if ( sought->data == data )
{
    //...
    continue ;
}
    prev_sought = sought ;
    sought = sought->next ;

Почему не

C++
1
2
3
4
5
6
7
8
9
if ( sought->data == data )
{
    //...
} 
else 
{
    prev_sought = sought ;
    sought = sought->next ;
}

???

@woldemas · 04.09.2018, 10:35

Сообщение от Mournful Max

Позже попробую внедрить в это дело итераторы.

С них надо начинать в данном случае, мне кажется. Иначе список бесполезен.

C++
1
2
3
4
5
6
7
8
9
10
void Forward_list::clear()
{
    auto expected = head ; 
    while ( expected )
    {
        expected = expected->next ;
        delete head ;
        head = expected ;
    }
}

Лучше:

C++
1
2
3
4
void Forward_list::clear()
{
    while (head) pop_front(); // или что-то в этом вроде
}

И в pop_front у вас нет проверки для пустого списка.
Ну и там много всего такого.
И самое главное: Foward_list как-то уродливо выглядит. Лучше или forward_list или ForwardList.

@Mournful Max · 05.09.2018, 06:25 **[ТС]**

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

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

а лучше вернуть NULL

Вы, видимо, не обратили внимания на тип возвращаемого значения метода — const_opt Data_t&. Вернуть nullptr не получится

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

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

и не вижу метода типа find(поиск) а так же вставить(Add)

Вот же он ( find() ) :

Сообщение от Mournful Max

C++
28
std::size_t find( const Data_t& data ) const ;

Только работает он пока что криво, ибо нет итераторов, с помощью которых можно было бы вернуть итератор на первый найденный такой элемент. Можно, конечно, вернуть ссылку на этот найденный элемент, но я уже лучше позже напишу привычную всем версию, которую я упомянул ранее. Причина, по которой нет метода «вставить(Add)», примерно такая же, как и почему нет нормального метода find() — нет итераторов. Объясняю : например, хочу вставить такой-то элемент после такого-то. А что если таких-то элементов в списке несколько ? После какого вставлять ? Можно добавить индекс, который будет соответствовать количеству пропущенных элементов и бла-бла-бла

А лучше подождать версию с итераторами

____

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

Почему не использовать предназначенный для это конструктор Node?

Да, действительно. Что-то я, как это говорится, пошел не самым легким путем... ) Исправил.

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

Для функций-членов empty, front можно добавить noexcept.

Сделано.

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

C++
1
decltype ( head ) sought = head

decltype ради decltype? Зачем это?

Полагаю, имеются в виду строчки :

C++
37
38
decltype ( head ) sought      = head,
                  prev_sought = nullptr ;

Да, действительно, здесь можно было обойтись и простым

C++
1
2
Node* sought      = head,
    * prev_sought = nullptr ;

, но я стараюсь избегать явной подстановки типов. Не знаю зачем. Если это плохая практика — ругайте. Я исправлюсь.

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

Почему не

Потому что намудрил

Исправил.
____

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

С них надо начинать в данном случае, мне кажется. Иначе список бесполезен.

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

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

Лучше:

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

Если я намудриваю, то исправлю.

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

И в pop_front у вас нет проверки для пустого списка.

А пусть пользователь проверяет ( .empty() ) перед тем, как изымать что-то

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

И самое главное: Foward_list как-то уродливо выглядит. Лучше или forward_list или ForwardList.

Самое главное

____

Вот исправленный вариант :

forward_list.hpp

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
#ifndef MY_FORWARD_LIST_HPP
#define MY_FORWARD_LIST_HPP
 
#include <cstddef>
 
namespace my
{
 
using Data_t = int ;
 
 
class Forward_list
{
    struct Node ;
 
    Forward_list( const Forward_list& )            = delete ;
    Forward_list& operator=( const Forward_list& ) = delete ;
 
public:
    Forward_list() ;
          Data_t& front()       noexcept ;
    const Data_t& front() const noexcept ;
    bool empty() const noexcept ;
    void clear() ;
    void push_front( const Data_t& data ) ;
    void pop_front() ;
    void remove( const Data_t& data ) ;
    std::size_t find( const Data_t& data ) const ;
    ~Forward_list() ;
 
private:
    Node* head ;
};
 
struct Forward_list::Node
{
    Node( const Data_t& data_, Node* next_ = nullptr ) ;
 
    Data_t data ;
    Node*  next ;
};
 
}
 
#include "forward_list.inl"
 
#endif /* MY_FORWARD_LIST_HPP */

forward_list.inl

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
#ifndef MY_FORWARD_LIST_INL
#define MY_FORWARD_LIST_INL
 
#include "forward_list.hpp"
 
namespace my
{
 
inline Forward_list::Forward_list()
: head( nullptr )
{
}
 
inline Data_t& Forward_list::front() noexcept
{
    return head->data ;
}
 
inline const Data_t& Forward_list::front() const noexcept
{
    return head->data ;
}
 
inline bool Forward_list::empty() const noexcept
{
    return head == nullptr ;
}
 
inline void Forward_list::push_front( const Data_t& data )
{
    head = new Node( data, head ) ;
}
 
inline Forward_list::~Forward_list()
{
    clear() ;
}
 
 
/* ---- Forward_list::Node's space ---- */
inline Forward_list::Node::Node( const Data_t& data_, Node* next_ )
: data( data_ ), next( next_ )
{
}
 
}
 
#endif /* MY_FORWARD_LIST_INL */

forward_list.cpp

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
#include "forward_list.hpp"
 
namespace my
{
 
void Forward_list::clear()
{
    auto expected = head ;
 
    while ( expected )
    {
        expected = expected->next ;
        delete head ;
        head = expected ;
    }
}
 
void Forward_list::pop_front()
{
    auto dead_head = head ;
    head = head->next ;
    delete dead_head ;
}
 
void Forward_list::remove( const Data_t& data )
{
    decltype ( head ) sought      = head,
                      prev_sought = nullptr ;
 
    while ( sought )
    {
        if ( sought->data == data )
        {
            if ( sought == head )
                head = sought->next ;
 
            if ( prev_sought )
                prev_sought->next = sought->next ;
 
            auto dead_sought = sought ;
            sought = sought->next ;
 
            delete dead_sought ;
        }
        else
        {
            prev_sought = sought ;
            sought = sought->next ;
        }
    }
}
 
std::size_t Forward_list::find( const Data_t& data ) const
{
    std::size_t count  = 0 ;
    auto        sought = head ;
 
    while ( sought )
    {
        if ( sought->data == data )
            count += 1 ;
 
        sought = sought->next ;
    }
 
    return count ;
}
 
}

Итераторы добавлю немного позже.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

'Base' forward list / «Базовый» односвязный список

Решение