Кольцевой двусвязный список - EcsFlash/DataTypes GitHub Wiki

Кто такое придумал, а главное зачем - хз. В некоторых моментах конечно удобнее чем с обычным исполнением, но всё же.

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

Суть

Прикол в том что у нас есть фиктивная голова, которую мы никак не трогаем. Она служит точкой входа в наш порочный круг. Если кроме башки в списке больше нету элементов, то next и prev этой самой башки указывают на неё саму. Если же элементы есть, то prev башки указывает на последний элемент списка, последний элемент списка указывает своим next на эту башку, и всё у всех хорошо.

Случай когда элементы есть

image

Случай когда элементов нету

image

Итак, приступим

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

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

Инициализация списка (создание первого элемента списка)

CDLList() {
	head = new Node(0);
	head->next = head;
	head->prev = head;
}

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

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

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

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

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

void addBefore(Node* whereTo, T element) {
	if (whereTo) {
		addAfter(whereTo->prev, element);
	}
}

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

void deleteAfter(Node* whereTo) {
	if (whereTo) {
		deleteNode(whereTo->next);
	}
}

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

void deleteBefore(Node* whereTo) {
	if (whereTo) {
		deleteNode(whereTo->prev);
	}
}

Удаление текущего элемента

void deleteNode(Node* node) {
	if (node && node != head) {
		node->next->prev = node->prev;
		node->prev->next = node->next;
		delete node;
		node = nullptr;
	}
}

Создание списка в прямом/обратном порядке

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

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

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

Печать списка в прямом и обратном направлении

void print(bool reversed = false) {
	if (!isEmpty()) {
		cout << "in ptint" << endl;
		Node* temp = head;
		if (reversed) {
			temp = temp->prev;
			while (temp != head)
			{
				cout << temp->data << " ";
				temp = temp->prev;
			}
		}
		else {
			temp = temp->next;
			while (temp != head)
			{
				cout << temp->data << " ";
				temp = temp->next;
			}
		}
	}
}

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

~CDLList() {
	clear();
	delete head;
	head = nullptr;
}
void clear() {
	while (!isEmpty()) {
		deleteNode(head->next);
	}
}

Упражнение закончили

обля

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