Двунаправленные списки - EcsFlash/DataTypes GitHub Wiki

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

DLList() {
	head = nullptr;
	tail = nullptr;
}

bool isEmpty() {
	return head == nullptr;
}

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

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

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

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

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

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

DLList(T arr[], int size) {
	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 print(bool reversed = false) {
	if (!reversed) {
		Node* temp = head;
		while (temp != nullptr) {
			cout << temp->data << " ";
			temp = temp->next;
		}
	}
	else {
		Node* temp = tail;
		while (temp != nullptr) {
			cout << temp->data << " ";
			temp = temp->prev;
		}
	}
}

~DLList() {
	clear();
}
void clear() {
	while (!isEmpty())
	{
		deleteNode(head);
	}
}