Линейные однонаправленные списки С заглавным звеном - EcsFlash/DataTypes GitHub Wiki

Исходный код - тут

Суть

Почти ничем не отличается от обычного списка. Весь прикол состоит в том, что теперь есть башка, которую мы никак не трогаем. Вот и всё.

Структура узла

struct Node {
	T data;
	Node* next;
	Node(T data) {
		this->data = data;
		next = nullptr;
	}
};

Инициализация списка (создание пустого списка)

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

LListWH() {
	head = new Node(0);
}

По аналогии с обычным односвязным списком имеем право сделать следующие конструкторы(способы создания)

LListWH(T arr[], int size, bool reversed) {
	head = new Node(0);
	if (reversed) {
		for (int i = 0; i < size; i++) {
			addToHead(arr[i]);
		}
	}
	else {
		for (int i = size-1; i >= 0; i--) {
			addToHead(arr[i]);
		}
	}
}

Проверка на пустоту

bool isEmpty() 
{
	return head->next == nullptr;
}

Добавление элемента в список после заданного элемента (заданный элемент определяется указателем)

void addAfter(Node* whereTo, T element) 
{
	if (whereTo) {
		Node* newElement = new Node(element);
		newElement->next = whereTo->next;
		whereTo->next = newElement;
	}
}

Удаление элемента из списка после заданного элемента (заданный элемент определяется указателем)

void deleteAfter(Node* whereTo) 
{
	if (whereTo) {
		Node* temp = whereTo->next;
		if (temp) {
			whereTo->next = whereTo->next->next;
			delete temp;
		}
	}
}

Создание упорядоченного списка

опять же способ на сочка

LListWH(T arr[], int size) {
	head = new Node(0);
	T temp;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size - 1; j++) {
			if (arr[i] < arr[j]) {
				temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
	for (int i = 0; i < size; i++) {
		addToHead(arr[i]);
	}
}

Печать списка

void println() {
	Node* temp = head->next;
	while (temp != nullptr) {
		cout << temp->data << " ";
		temp = temp->next;
	}
}

Уничтожение списка

~LListWH() {
	clear();
	delete head;
	head = nullptr;
}
void clear() {
	while (!isEmpty())
	{
		deleteFirst();
	}
}

Рекурсивная печать

просто начинаем не с head а с head->next

void print(Node* node) {
	if (node) {
		cout << node->data << " ";
		print(node->next);
	}
}
public:
void print() 
{
	print(head->next);
}

Рекурсивная сумма

просто начинаем не с head а с head->next

T sum(Node* node, T currentSum) {
	if (node) {
		return sum(node->next, currentSum + node->data);
	}
	else {
		return currentSum;
	}
}
public:
T sum() 
{
	return sum(head->next, 0);
}

обля

⚠️ **GitHub.com Fallback** ⚠️