linkedList.cpp

/*
Contents of this file were provided on Moodle, except:
- List::remove(Node *node)
- List::findMedian()
- List::findMiddleElement()

Modified source code to use 'nullptr'
*/

#include <iostream>
#include <algorithm>
#include <vector>

class Node {
public:
	int value;
	Node* next;
	Node* prev;
	Node(int val) {
		std::cout << "Node constructor!" << std::endl;
		this->value = val;
		this->next = nullptr;
		this->prev = nullptr;
	}
	~Node() {
		std::cout << "Node destructor" << std::endl;
		std::cout << "I had the value " << this->value << std::endl;
	}
};
class List {

public:
	Node* head;
	Node* tail;

	List() {
		std::cout << "List Constructor!" << std::endl;
		this->head = nullptr;
		this->tail = nullptr;
	}
	~List() {
		std::cout << "List destructor!" << std::endl;
		std::cout << "Todo: properly delete nodes..." << std::endl;
		while (this->head != nullptr) {
			remove(this->head);
		}
	}
	void insert(Node* n, Node* x) {
		if (n != nullptr) {
			x->next = n->next;
			n->next = x;
			x->prev = n;
			if (x->next != nullptr)
				x->next->prev = x;
		}
		if (this->head == nullptr) {
			this->head = x;
			this->tail = x;
			x->prev = nullptr;
			x->next = nullptr;
		}
		else if (this->tail == n) {
			this->tail = x;
		}
	}
	void display() {
		Node* i = this->head;
		std::cout << "List: ";
		while (i != nullptr) {
			std::cout << i->value;

			i = i->next;
			if (i != nullptr) {
				std::cout << ", ";
			}
		}
		std::cout << std::endl;
	}
	/*
	 *	takes a node pointer as parameter
	 *	removes the given node from the linked list
	 */
	void remove(Node *node) {
		// check if the given node is the head of the linked list
		if (node == this->head) {
			// if it is the head, check if it has any more elements
			if (this->head->next == nullptr) {
				// if it doesn't, make the head and tail point to null
				this->head = nullptr;
				this->tail = nullptr;
			} else {
				// if it does, make the next element the new head
				this->head = this->head->next;
				this->head->prev = nullptr;
			}
		// otherwise check if the given node is the tail of the linked list
		} else if (node == this->tail) {
			// if it is the tail, make the previous element the new tail
			this->tail = this->tail->prev;
			// make the new tail's 'next' point to null
			this->tail->next = nullptr;
		} else {
			// otherwise it must be an element in the middle
			// link the previous and the following elements with each other
			node->prev->next = node->next;
			node->next->prev = node->prev;
		}
		// delete the node (call destructor)
		delete(node);
	}
	/*
	 *	finds the middle element in the given linked list, and returns it
	 *	(does not sort the elements, just finds the one in the middle,
 	 *	or the one right before the middle in case
	 *	there are an even number of elements)
	 */
	int findMiddleElement() {
		// create vector elements will be stored in
		std::vector<int> elements;
		// create node pointer, point it to the linked list's head
		Node *node = this->head;
		// iterate through linked list
		while (node != nullptr) {
			// add current element to vector of elements
			elements.emplace_back(node->value);
			node = node->next;
		}
		// return the middle element
		return elements[(elements.size() + 1) / 2 - 1];
	}
	/*
	 *	finds the median of the elements of the linked list, and returns it as a double
	 */
	double findMedian() {
		// create vector elements will be stored in
		std::vector<int> elements;
		// create node pointer, point it to the linked list's head
		Node *node = this->head;
		// iterate through linked list
		while (node != nullptr) {
			// add current element to vector of elements
			elements.emplace_back(node->value);
			node = node->next;
		}
		// sort elements
		std::sort(elements.begin(), elements.end());
		// check whether there is an even or odd number of elements
		if (elements.size() % 2 == 0) {
			// in case there is an even number of elements
			// return the average of the two middle elements of the sorted list
			return static_cast<double>(elements[elements.size() / 2 - 1] + elements[elements.size() / 2]) / 2;
		} else {
			// in case there is an odd number of elements
			// return the middle element of the sorted list
			return static_cast<double>(elements[elements.size() / 2]);
		}
	}
};

int main(int argc, char *argv[]) {
	List *l = new List();
	l->insert(nullptr, new Node(4));
	l->insert(l->tail, new Node(8));
	l->insert(l->tail, new Node(5));
	l->insert(l->tail, new Node(6));
	l->display();
	l->remove(l->tail);
	l->display();
	std::cout << "Median: "<< l->findMedian() << std::endl
	 << "Middle element: " << l->findMiddleElement() << std::endl;
	delete l;
	return 0;
}