Возможная реализация списка (листа) на C++

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

Представленный ниже код можно поместить в файл заголовка с именем CustomList.h и подключить к своей программе. Ниже мы посмотрим на варианты использования класса для создания нескольких тестовых списков.

Итак, перейдем к исходному коду предлагаемого готового решения:

/*
Copyright (c) 2022 Allineed.Ru ( http://allineed.ru )

Данная лицензия разрешает лицам, получившим копию данного программного обеспечения и сопутствующей документации (в дальнейшем именуемыми «Программное обеспечение»),
безвозмездно использовать Программное обеспечение без ограничений, включая неограниченное право на использование, копирование, изменение, слияние, публикацию,
распространение, сублицензирование и/или продажу копий Программного обеспечения, а также лицам, которым предоставляется данное Программное обеспечение,
при соблюдении следующих условий:

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

ДАННОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПРЕДОСТАВЛЯЕТСЯ «КАК ЕСТЬ», БЕЗ КАКИХ-ЛИБО ГАРАНТИЙ, ЯВНО ВЫРАЖЕННЫХ ИЛИ ПОДРАЗУМЕВАЕМЫХ, ВКЛЮЧАЯ ГАРАНТИИ ТОВАРНОЙ ПРИГОДНОСТИ,
СООТВЕТСТВИЯ ПО ЕГО КОНКРЕТНОМУ НАЗНАЧЕНИЮ И ОТСУТСТВИЯ НАРУШЕНИЙ, НО НЕ ОГРАНИЧИВАЯСЬ ИМИ. НИ В КАКОМ СЛУЧАЕ АВТОРЫ ИЛИ ПРАВООБЛАДАТЕЛИ НЕ НЕСУТ ОТВЕТСТВЕННОСТИ
ПО КАКИМ-ЛИБО ИСКАМ, ЗА УЩЕРБ ИЛИ ПО ИНЫМ ТРЕБОВАНИЯМ, В ТОМ ЧИСЛЕ, ПРИ ДЕЙСТВИИ КОНТРАКТА, ДЕЛИКТЕ ИЛИ ИНОЙ СИТУАЦИИ, ВОЗНИКШИМ ИЗ-ЗА ИСПОЛЬЗОВАНИЯ ПРОГРАММНОГО
ОБЕСПЕЧЕНИЯ ИЛИ ИНЫХ ДЕЙСТВИЙ С ПРОГРАММНЫМ ОБЕСПЕЧЕНИЕМ.

Copyright 2022 Allineed.Ru ( http://allineed.ru )

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), 
to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, 
and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#pragma once

template <class T> class CustomList
{
private:
	// Текущее количество элементов в списке
	int current_size;
	// Указатель на элементы списка
	T* elements;
protected:
	// Устанавливает новый размер списка, равный <new_size>
	void set_size(int new_size) {
		current_size = new_size;
	}
	// Увеличивает размер списка на 1
	void inc_size() {
		current_size++;
	}
public:
	// Конструктор
	CustomList();

	// Деструктор
	~CustomList();

	// Получает размер списка
	int size() const {
		return current_size;
	}

	// Заполняет список заданными элементами из массива <elements_array>
	// Параметр <number_to_copy> должен быть меньше или равен числу элементов массива <elements_array>
	// и должен быть больше 0
	void fill(T* elements_array, int number_to_copy);

	// Добавляет новый элемент <element> в конец списка
	void add(T const& element);

	// Удаляет последний элемент с конца списка
	void pop();

	// Получает элемент списка в заданной позиции (по заданному индексу <index>)
	T get(int index) const {
		T* elm = this->p_get(index);
		return *elm;
	}

	// Получает первый элемент из списка
	T first() const {
		T* first_elm = this->p_first();
		return *first_elm;
	}

	// Получает последний элемент из списка
	T last() const {
		T* last_elm = this->p_last();
		return *last_elm;
	}

	// Удаляет элемент в заданной позиции списка
	// Если <index> выходит за допустимые границы списка, метод не сделает ничего и вернёт false
	// Если производится попытка удалить элемент из пустого списка, метод ничего не сделает и вернёт false
	// Если элемент был успешно удалён в заданной позиции, метод вернёт true
	bool remove(int index);

	// Удаляет элементы в заданном диапазоне списка от <begin_index> включительно до <end_index>
	// Если <begin_index> или <end_index> выходят за допустимые границы списка, метод не сделает ничего и вернёт false
	// Если <begin_index> больше <end_index>, метод не сделает ничего и вернёт false
	// Если <begin_index> равен <end_index> действие метода равнозначно вызову обычного remove() с одним параметром <index>
	// Если <begin_index> меньше <end_index> метод удалит все элементы из списка, начиная с позиции <begin_index> и заканчивая позицией <end_index>
	// В случае успешного удаления элементов из списка метод возвращает true
	bool remove(int begin_index, int end_index);

	// Сокращает список до количества элементов, заданного параметром <remaining_elements_number>
	// Если список пуст, не делает ничего
	// Если <remaining_elements_number> больше или равен текущему размеру списка, не делает ничего
	// Если <remaining_elements_number> меньше 0, не делает ничего
	// Если <remaining_elements_number> равен 0, действие равнозначно вызову метода clear()
	void reduce(int remaining_elements_number);

	// Увеличивает список на количество элементов, заданное параметром <additional_elements_number>
	// Если список пуст, не делает ничего
	// Если <remaining_elements_number> меньше или равен 0, не делает ничего
	void extend(int additional_elements_number);

	// Получает указатель на элемент в заданной позиции (по заданному индексу <index>)
	T* p_get(int index) const;

	// Получает указатель на последний элемент списка
	T* p_last() const;

	// Получает указатель на первый элемент списка
	T* p_first() const;

	// Удаляет все элементы из списка, сокращая его размер до 0
	void clear();

	// Проверяет, является ли список пустым
	// Возвращает true, если список пуст.
	bool is_empty() const {
		return size() == 0;
	}
};

// Конструктор
template <class T> CustomList<T>::CustomList() {
	set_size(0);
	elements = nullptr;
}

// Деструктор
template <class T> CustomList<T>::~CustomList() {
	if (elements != nullptr && size() > 0) {
		delete[] elements;
		elements = nullptr;
	}
	set_size(0);
}

// Добавляет новый элемент <element> в конец списка
template <class T> void CustomList<T>::add(T const& element) {
	int old_size = size();
	inc_size();

	T* new_elements = new T[size()];
	if (old_size > 0) {
		for (int i = 0; i < old_size; i++) {
			new_elements[i] = elements[i];
		}
	}
	new_elements[current_size - 1] = element;

	if (old_size > 0) {
		delete[] elements;
	}
	elements = new_elements;
}

// Удаляет последний элемент с конца списка
template <class T> void CustomList<T>::pop() {
	if (size() == 0) {
		return;
	}

	int new_size = size() - 1;

	if (new_size == 0) {
		this->clear();
		return;
	}

	T* new_elements = new T[new_size];
	for (int i = 0; i < new_size; i++) {
		new_elements[i] = elements[i];
	}

	delete[] elements;

	elements = new_elements;
	set_size(new_size);
}

// Получает указатель на последний элемент в списке
template <class T> T* CustomList<T>::p_last() const {
	if (size() == 0) {
		return nullptr;
	}

	if (size() == 1) {
		return &elements[0];
	}

	return &elements[current_size - 1];
}

// Получает указатель на первый элемент в списке
template <class T> T* CustomList<T>::p_first() const {
	if (current_size == 0) {
		return nullptr;
	}

	return &elements[0];
}

// Очищает список, удаляя все элементы
template <class T> void CustomList<T>::clear() {
	if (current_size == 0) {
		return;
	}

	delete[] elements;
	elements = nullptr;
	current_size = 0;
}

// Заполняет список заданными элементами из массива <elements_array>
// Параметр <number_to_copy> должен быть меньше или равен числу элементов массива <elements_array>
// и должен быть больше 0
// Если <number_to_copy> больше размера массива <elements_array>, поведение метода непредсказуемо.
template <class T> void CustomList<T>::fill(T* elements_array, int number_to_copy) {
	if (elements_array == nullptr || number_to_copy <= 0) {
		return;
	}	
	for (int i = 0; i < number_to_copy; i++) {
		T temp = elements_array[i];
		this->add(temp);
	}
}


// Получает указатель на элемент в заданной позиции (по заданному индексу index)
template <class T> T* CustomList<T>::p_get(int index) const {
	if (current_size == 0 || index < 0 || index >= current_size) {
		return nullptr;
	}

	return &elements[index];
}

// Сокращает список до количества элементов, заданного параметром <remaining_elements_number>
// Если список пуст, не делает ничего
// Если <remaining_elements_number> больше или равен текущему размеру списка, не делает ничего
// Если <remaining_elements_number> меньше 0, не делает ничего
// Если <remaining_elements_number> равен 0, действие равнозначно вызову метода clear()
template <class T> void CustomList<T>::reduce(int remaining_elements_number) {
	if (current_size == 0 || current_size <= remaining_elements_number || remaining_elements_number < 0) {
		return;
	}
	if (remaining_elements_number == 0) {
		clear();
		return;
	}

	T* new_elements = new T[remaining_elements_number];
	for (int i = 0; i < remaining_elements_number; i++) {
		new_elements[i] = this->elements[i];
	}

	delete[] elements;

	elements = new_elements;
	current_size = remaining_elements_number;
}

// Увеличивает список на количество элементов, заданное параметром <additional_elements_number>
// Если список пуст, не делает ничего
// Если <remaining_elements_number> меньше или равен 0, не делает ничего
template <class T> void CustomList<T>::extend(int additional_elements_number) {
	if (size() == 0 || additional_elements_number <= 0) {
		return;
	}

	int new_size = this->size() + additional_elements_number;

	T* new_elements = new T[new_size];
	for (int i = 0; i < this->size(); i++) {
		new_elements[i] = elements[i];
	}
	int j = 0;
	for (int i = this->size(); i < new_size; i++) {
		new_elements[i] = elements[j++];
		if (j >= current_size) {
			j = 0;
		}
	}

	delete[] elements;

	elements = new_elements;
	current_size = new_size;
}

// Удаляет элемент в заданной позиции списка
// Если <index> выходит за допустимые границы списка, метод не сделает ничего и вернёт false
// Если производится попытка удалить элемент из пустого списка, метод ничего не сделает и вернёт false
// Если элемент был успешно удалён в заданной позиции, метод вернёт true
template <class T> bool CustomList<T>::remove(int index) {
	if (size() == 0) {
		return false;
	}

	if (index < 0 || index >= size()) {
		return false;
	}

	if (size() == 1 && index == 0) {
		this->clear();
		return true;
	}

	int new_size = size() - 1;
	T* new_elements = new T[new_size];
	int current_index = 0;
	while (current_index < index) {
		new_elements[current_index] = elements[current_index];
		current_index++;
	}
	for (int i = index + 1; i < size(); i++) {
		new_elements[current_index] = elements[i];
		current_index++;
	}

	delete[] elements;

	elements = new_elements;
	current_size = new_size;

	return true;
}

// Удаляет элементы в заданном диапазоне списка от <begin_index> включительно до <end_index>
// Если <begin_index> или <end_index> выходят за допустимые границы списка, метод не сделает ничего и вернёт false
// Если <begin_index> больше <end_index>, метод не сделает ничего и вернёт false
// Если <begin_index> равен <end_index> действие метода равнозначно вызову обычного remove() с одним параметром <index>
// Если <begin_index> меньше <end_index> метод удалит все элементы из списка, начиная с позиции <begin_index> и заканчивая позицией <end_index>
// В случае успешного удаления элементов из списка метод возвращает true
template <class T> bool CustomList<T>::remove(int begin_index, int end_index) {
	if (size() == 0 || end_index < begin_index) {
		return false;
	}

	if (begin_index == end_index) {
		return this->remove(begin_index);
	}

	if (begin_index < 0 || end_index < 0 || end_index >= size()) {
		return false;
	}

	if (begin_index == 0 && end_index == size() - 1) {
		this->clear();
		return true;
	}

	int new_size = size() - (end_index - begin_index) - 1;
	T* new_elements = new T[new_size];
	int current_index = 0;
	for (int i = 0; i < size(); i++) {
		if (i < begin_index || i > end_index) {
			new_elements[current_index] = elements[i];
			current_index++;
		}
	}

	delete[] elements;

	elements = new_elements;
	current_size = new_size;

	return true;
}

Сразу оговорюсь, что если Вы вдруг захотите использовать данный класс в своих программах на C++, то мы как авторы не несём ответственности за подобное решение и любые последствия его принятия (см. полный текст лицензии в комментарии перед определением класса). От нас просьба: если Вы всё же решитесь использовать класс в своём ПО, - оставить заголовок с лицензией.

Функциональность представленного класса CustomList не претендует на абсолютную точность и представлена исключительно для демонстративных целей и целей изучения возможностей языка C++.

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

Давайте теперь перейдем к рассмотрению возможностей класса. Подключим к нашей тестовой программе файл заголовка CustomList.h с текстом нашего шаблонного класса CustomList и попробуем определить пару списков типа int и double, а также попробовать в действии предоставляемые методы нашего списка:

#include <iostream>
#include "CustomList.h"

using namespace std;

template <class T> void print_list_size(const CustomList<T> *list) {
    cout << "Current List Size = " << list->size() << endl;
}

template <class T> void print_list_elements(char const *title, const CustomList<T>* list) {
    cout << title << endl;
    print_list_size(list);
    for (int i = 0; i < list->size(); i++) {
        cout << "i = " << i << ", list value: " << list->get(i) << endl;
    }
}

int main() {
    // Тестовый список из целых чисел
    CustomList<int> customIntList;

    // Добавление трёх элементов в список
    customIntList.add(1);
    customIntList.add(2);
    customIntList.add(3);

    cout << "Integer list size: " << customIntList.size() << endl;
    // Доступ к конкретным элементам списка по указателю и его разыменованию
    cout << "first = " << *customIntList.p_first() << ", last = " << *customIntList.p_last() << ", second = " << *customIntList.p_get(1) << endl;
    
    // Проверка на то, является ли список пустым
    cout << "Is list empty? (0 = false, 1 = true): " << customIntList.is_empty() << endl;

    // Тестовый список из чисел типа double
    CustomList<double> customDoubleList;

    // Входной тестовый массив чисел для наполнения списка
    double double_array[5] = { 2.6, 1.8, -10.3, 100.2, -17. };

    int double_array_size = sizeof(double_array) / sizeof(double);
    cout << "Double array 'double_array[5]' size: " << double_array_size << endl;

    // Метод fill() используется для заполнения списка
    customDoubleList.fill(double_array, double_array_size);

    cout << "Double list size: " << customDoubleList.size() << endl;
    for (int i = 0; i < customDoubleList.size(); i++) {
        // Демонстрация доступа к элементам списка по указателю
        cout << "i = " << i << ", list value: " << *customDoubleList.p_get(i) << endl;
    }

    for (int i = 0; i < customDoubleList.size(); i++) {
        // Демонстрация доступа к элементам списка без использования указателя
        cout << "i = " << i << ", list value: " << customDoubleList.get(i) << endl;
    }

    // Метод extend() расширяет список на +15 элементов, "циклично" дублируя элементы, которые
    // уже были в списке до его расширения
    customDoubleList.extend(15);    
    print_list_elements("After customDoubleList.extend(15):" , &customDoubleList);

    // Метод reduce() используется для урезания списка до заданного количества элементов    
    customDoubleList.reduce(7);
    print_list_elements("After customDoubleList.reduce(7):" , &customDoubleList);   

    // Метод remove() с одним параметром индекса используется для удаления конкретного элемента списка в заданной позиции
    customDoubleList.remove(0);
    print_list_elements("After customDoubleList.remove(0):", &customDoubleList);
    customDoubleList.remove(3);
    print_list_elements("After customDoubleList.remove(3):", &customDoubleList);

    // Метод remove() с двумя параметрами используется для удаления диапазона элементов списка
    customDoubleList.remove(2, 4);
    print_list_elements("After customDoubleList.remove(2, 4):", &customDoubleList);

    // Метод clear() используется для очистки списка
    customDoubleList.clear();
    print_list_elements("After customDoubleList.clear():", &customDoubleList);
}

При запуске этой тестовой программы Вы увидите следующий вывод в вашей консоли:

Integer list size: 3
first = 1, last = 3, second = 2
Is list empty? (0 = false, 1 = true): 0
Double array 'double_array[5]' size: 5
Double list size: 5
i = 0, list value: 2.6
i = 1, list value: 1.8
i = 2, list value: -10.3
i = 3, list value: 100.2
i = 4, list value: -17
i = 0, list value: 2.6
i = 1, list value: 1.8
i = 2, list value: -10.3
i = 3, list value: 100.2
i = 4, list value: -17
After customDoubleList.extend(15):
Current List Size = 20
i = 0, list value: 2.6
i = 1, list value: 1.8
i = 2, list value: -10.3
i = 3, list value: 100.2
i = 4, list value: -17
i = 5, list value: 2.6
i = 6, list value: 1.8
i = 7, list value: -10.3
i = 8, list value: 100.2
i = 9, list value: -17
i = 10, list value: 2.6
i = 11, list value: 1.8
i = 12, list value: -10.3
i = 13, list value: 100.2
i = 14, list value: -17
i = 15, list value: 2.6
i = 16, list value: 1.8
i = 17, list value: -10.3
i = 18, list value: 100.2
i = 19, list value: -17
After customDoubleList.reduce(7):
Current List Size = 7
i = 0, list value: 2.6
i = 1, list value: 1.8
i = 2, list value: -10.3
i = 3, list value: 100.2
i = 4, list value: -17
i = 5, list value: 2.6
i = 6, list value: 1.8
After customDoubleList.remove(0):
Current List Size = 6
i = 0, list value: 1.8
i = 1, list value: -10.3
i = 2, list value: 100.2
i = 3, list value: -17
i = 4, list value: 2.6
i = 5, list value: 1.8
After customDoubleList.remove(3):
Current List Size = 5
i = 0, list value: 1.8
i = 1, list value: -10.3
i = 2, list value: 100.2
i = 3, list value: 2.6
i = 4, list value: 1.8
After customDoubleList.remove(2, 4):
Current List Size = 2
i = 0, list value: 1.8
i = 1, list value: -10.3
After customDoubleList.clear():
Current List Size = 0

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

Кратко рассмотрим основные методы класса, предоставляемые для работы со список требуемого Вам типа. Более детальное описание работы каждого метода Вы найдете в комментариях к методу в самом классе. Итак, есть следующие методы в нашей кастомной реализации списка:

• int size() - метод возвращает текущий размер списка
• void fill(T* elements_array, int number_to_copy) - метод используется для заполнения списка значениями, например, из массива (посмотрите на то, как в примере выше мы заполнили список значениями массива double_array)
• void add(T const& element) - метод для добавления нового элемента в список. Наш список не проверяет уникальность элементов, поэтому можно добавить несколько элементов с одинаковыми значениями.
• void pop() - метод удаляет последний элемент с конца списка
• T get(int index) - метод возвращает заданный элемент по индексу
• T first() - метод возвращает первый элемент списка
• T last() - метод возвращает последний элемент списка
• bool remove(int index) - вариант метода с одним параметром удаляет заданный элемент из списка по его индексу. Если элемент был удалён вернёт true, иначе false
• bool remove(int begin_index, int end_index) - вариант метода с двумя параметрами удаляет заданный диапазон по начальному и конечному индексам. Если диапазон был удалён, метод вернёт true, иначе false
• void reduce(int remaining_elements_number) - сокращает количество элементов в списке до указанного во входном параметре.
• void extend(int additional_elements_number) - увеличивает количество элементов в списке на значение, переданное во входном параметре.
• T* p_get(int index) - получает указатель на элемент списка с индексом index
• T* p_first() - получает указатель на первый элемент списка
• T* p_last() - получает указатель на последний элемент списка
• void clear() - очищает список и удаляет все его элементы
• bool is_empty() - возвращает true, если список пустой, в противном случае возвращает false

Вы могли заметить, что список не обладает некоторыми возможностями, например, в нём нет метода replace(), который заменял бы элемент в заданной позиции. Предлагаю потренироваться в этом моим читателям и написать про возможную реализацию такого метода в качестве практики.

Вот и все публичные методы нашего класса CustomList. Попробуйте его в работе и напишите своё мнение в комментарии к этой статье. Спасибо и удачи в написании программ на C++!